求一个最短行程的算法或思路

[elfive]

现在有一个存放了 n 个线段（起点和终点坐标）的数组，结构如下：
[
[(sx_1,sy_1),(ex_1,ey_1)],
[(sx_2,sy_2),(ex_2,ey_2)],
......
[(sx_n,sy_n),(ex_n,ey_n)]
]

有没有这样一个，以其中某个点为起点，走过所有线段，并且使得总的行程最短的算法？

这里的距离不仅包含线段的长度，还包含线段之间的跳转距离。

要求就是：走线段的时候，必须从线段一端进入，从另一端退出，且不能有重复走某条线段。

[zjp]

可以转化为图的问题。并不能保证某个点可以到达所有边（不连通），也不能保证不重复走（有死端）

[hinate]

这是类似走迷宫吗？

[ynyounuo]

这不是 MST ？

[ynyounuo]

好吧，并不一样。

[zj299792458]

听起来是遍历所有点，直接深度优先搜索

[ynyounuo]

感觉比较类似 TSP 问题，可以去参考一下

[aheadlead]

我觉得以后提问的时候最好多画几张图
也便于别人看懂意思

[ladeo]

ospf

[elfive]

@aheadlead
@hinate
简单补了个图，看看能不能稍微清楚点

[geelaw]

什么是“线段之间的跳转距离”？

[xinhangliu]

模拟退火

[Bryan0Z]

MST 的算法改一下？

[aheadlead]

@elfive 补的图很棒，有数据范围吗？

N < 20，N<100 和 N<10000 的思路完全不一样了…

[luoshuangfw]

需要明确一下：从一条边的 end 出来，是否可以进入剩下所有边中任意一条边的 start，只要没走过？

[elfive]

@aheadlead 数据范围其实没啥限制，但是绝大多数情况应该是 N < 500

[elfive]

@geelaw 就是 线段某个端点 到 另一条线段某个端点 之间的最短距离；

[elfive]

@luoshuangfw 只要保证：1、走过所有线段； 2、不重复走任何一条线段； 3、线段不能拆分，这 3 个条件就 OK 了

[Bryan0Z]

找一个线段当起点
依次判断其他线段端点到它的端点的距离，找到一个最小的加入
重复步骤二

反正就那个意思，把 prim 或者 d 算法改一下就好了

[Bryan0Z]

哦，不太一样

[luoshuangfw]

@Bryan0Z 这是不行的，不是 MST ；确切的说要求的不是一棵树，而是一个回路