subject_14674.htm

一些关于vc的问答

<p>
序号：14674 发表者：易波 发表日期：2002-09-10 12:50:17
<br>主题：谁能告诉我？
<br>内容：有一队点Pn(int x,int y)( 3 &lt;= n &lt; 10000)需要排序使得经过所有点的路径之和最小。<BR>点保存在数组中，且没有重复点。我苦思数年无果，万望各位能指教。<BR>
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：史列因 回复日期：2002-09-10 14:54:26
<br>内容：&nbsp;&nbsp;&nbsp;&nbsp;这个问题全世界的科学家苦思数十年无果。不要说10000，就连100都没法解。如果谁能解出来，或证明它解不出来，那么谁就成了一代伟人。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：衣钵 回复日期：2002-09-11 16:58:04
<br>内容：真的没有办法了。太遗憾了，我目前的折衷算法是：以n1为起点,与之相近的点作为n2,<BR>再以n2为起点...依此类推.不过确实没有看到理想的解决方法.谢谢你!
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：xiongli 回复日期：2002-10-16 11:12:45
<br>内容：这是带权连通无向图的最小代价生成树问题，你不过需要算出任意两点的权，然后就是每个点都连通的图<BR>可以用prim/kruskal<BR>o(mlog2m)<BR>解决<BR>可以在任何一本数据结构课本上发现
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：赵万 回复日期：2002-10-16 14:08:42
<br>内容：本着学习的目的我想请大家探讨一下下面的情况:<BR>假如一个正方形 2*2 <BR>顺序访问四个顶点,路径最短长度应该是3*2=6<BR>联结四个顶点最短路径的长度是4*2^(1/2)=5.6..,就是2条对角线<BR><BR><BR><BR>我不太懂最小生成树,不过学过运筹学,也忘得差不多了.
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：xiongli 回复日期：2002-10-17 10:19:20
<br>内容：应该是2＋1。414＝3。414最短吧？
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：衣钵 回复日期：2002-10-18 14:12:21
<br>内容：你是说图论吧，我去查查。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>