我显然错过了树林中的森林......
我知道旅行推销员问题，但是还有其他算法/问题更适合我的需求/描述吗？我需要借助这样的数学描述来描述我的问题。
我有多达五个已知起点和终点的点。所以我只需要计算访问这两个点之间所有三个点的最短路径。Dijkstra 和类似的算法试图找到两点之间的最短路径，所以在这里他们可能不会访问之间的所有点。或者是否有一种算法可以找到最短路径并访问两点之间的所有点？
问问题
205 次
1 回答
7
你想多了。只有六个 (3*2*1) 可能的路径通过三个中间节点。只需检查它们。
对于较大的实例，您可以将问题减少到TSP，如下所示：
如果s是起始节点并且t是最终节点，则在 和 之间添加一条零权重边，并在和每个其他节点之间以及在s和每个其他节点之间添加一条t无限重边。 st
这个问题是 NP 难的，但经过了非常深入的研究。您可以探索大量精确和近似的算法。
于 2013-09-24T19:23:18.733 回答