这个是图论里的哪个问题？

[realfun]

记得以前遇到一个问题，没有细想，前两天想起来感觉是个图论里面的问题，但是查了半天都不象。当然，可以把每两个点之间的哈密顿路径计算出来然后求最小值，这样也太慢了。跟Travelling Salesman Problem也很象，就是不用走回来了（ http://en.wikipedia.org/wiki/Travelling_salesman_problem ）

简化版的问题是：平面上有很多点，画一条最短的线连通所有的点

原问题是：有个纺织机，需要在布上织出许多个多边形的图案，纺织机在多边形图案之间移动的时候很耗时，而且跟移动距离成正比，请设计算法尽量减少移动时间。

我把多边形抽象成一个个点。实际上原问题更加复杂，因为如果一个多边形A是长条形，两头各有两个多边形（B,C)，是可以从B画完然后画A的一半，跳到C画完再回到A把A画完。

btw，当初这是个面试题，让我写程序来着。。。

[tangl_99]

Minimum Spanning Tree?

[大笑之]

1.简化图案为点
2.连通所有的点
3.求最小生成树
4.求欧拉环路（此时该问题已和中国邮递员问题类似）

On 5月22日, 上午2时20分, realfun <real...@gmail.com> wrote:
> 记得以前遇到一个问题，没有细想，前两天想起来感觉是个图论里面的问题，但是查了半天都不象。当然，可以把每两个点之间的哈密顿路径计算出来然后求最小值，这样 也太慢了。跟Travelling

[realfun]

最小生成树不一定有欧拉环路啊，三岔口的怎么办？

2012/5/21 大笑之 <daxi...@gmail.com>

[Devymex Wang]

不就是tsp么？任意两点之间呢距离是给定的

[realfun]

http://en.wikipedia.org/wiki/Travelling_salesman_problem

是很像TSP，区别是：

1. 不用回到原点了

2. 每两点之间都有一条线，TSP没有这样规定，而是要求只能路过每个点一次

本来还想这个特殊化的问题有没有更好的解决方案的。

2012/5/22 Devymex Wang <dev...@gmail.com>

[Devymex Wang]

这个问题的解集与TSP相同，就是全部节点的一种排列。而TSP是经典的NPC问题，这个直觉上也是，但还没想到归约证明的方法。如果确为NPC那就优化吧，蚁群、进化、煺火都适用。

[石奇偲]

这个是ESMT（欧氏最小Steiner 树）。
你手头要是方便的话可以查  马良主编《高级运筹学》P134
或者google吧。

[石奇偲]

嗯，不一样。
你的问题边可能会重复走，Steiner树不是走过来又走过去。

这道题要是描述成：给纺织机普一个移动的轨道，怎么样让轨道总长度最短，才是Steiner树。

[石奇偲]

应该是最小哈密顿路吧。
先解决一个问题：任给两个多边形，两多边形上分别有动点P，Q。求线段PQ长度的最小值。

这个最小值作为建图时两点间的距离。然后就是最小哈密顿路问题了。