A之间路由和B

Question

i'm站之间缺少明显透过树木森林...

我知道旅行商问题，但没有任何其他算法/问题哪个好适合我的需求/描述？我需要借助这种数学描述来描述我的问题。

我有多达五点已知的起点和终点。所以我只需要计算最短的方式来访问这两者之间的所有三点。 Dijkstra和类似的算法试图找到两点之间的最短路径，所以在这里他们可能不会访问所有点之间的所有点。还是有一种算法找到最短路线并访问两点之间的所有点？

Answer 1

你正在超越它。通过三个中间节点只有六条（3 * 2 * 1）可能的路径。只是检查他们。

对于较大的情况下，你可以减少你的问题的TSP如下：

如果s的出发点和t是最后一个节点，添加s和t和无限之间的零重量边缘 - s与其他节点之间以及t与其他每个节点之间的重要边缘。

这个问题是NP-hard，但是研究得非常好。有许多精确和近似的算法可供您探索。