我知道旅行推销员问题，但是还有其他算法/问题更适合我的需求/描述吗？我需要借助这样的数学描述来描述我的问题。
我有一组具有已知起点和终点的节点。所以我只需要计算访问这两个点之间所有三个点的最短路径。Dijkstra 和类似的算法试图找到两点之间的最短路径，所以在这里他们可能不会访问之间的所有点。或者是否有一种算法可以找到最短路径并访问两点之间的所有点？
问问题
1524 次
2 回答
2
您可以使用蚁群优化算法来实现它。请参阅蚁群优化算法。
于 2013-10-23T08:13:41.050 回答
1
您的问题的一般情况的复杂性至少与旅行商问题一样高。试想一下，如果你的两个端点基本在同一位置，那么你的问题就相当于旅行推销员。
但是，如果您从不期望图表中的点超过 5 个，那么您真的需要为花哨的算法而烦恼吗？您可以进行详尽的搜索以找到最佳解决方案。由于唯一的决定是您访问中间三个点的顺序，因此您只需测试 3 个！= 6 条不同的路径。即使我误解了您并且您想要访问所有节点的整体最短开放路径，那仍然只有 5！= 120 条不同的测试路径（如果两个方向的距离相同，则为 60 条）。
于 2013-10-23T08:30:11.157 回答