c++ - 旅行商启发式

Question

我目前的想法是:从点 0 开始，将它与最近的点连接起来。对于所有剩余的节点，将其插入到所有可能的位置，并保留成本最低的配置。

所以我从点 0 开始。离点 0 最近的节点是点 1。

所以我现在有 0->1 -> 0

对于第 2 点(以及所有剩余的节点)，我将检查新节点可能位于何处的所有可能性:

2 -> 0 -> 1 -> 2

0 -> 2 -> 1 -> 0

0 -> 1-> 2 -> 0

从这里我发现

0 -> 1 -> 2 -> 0 的总欧几里得距离最小，因此这是我将保留的配置。

我将继续为我的其余节点使用此逻辑。

有没有一种简单的方法可以在 C++ 中实现它？我目前的想法是链表可能是个好主意，但如果可能的话，我希望能够使用 vector 。有人对如何解决这个问题有任何建议吗？

Answer 1

您是否考虑过使用有向图然后实现 dijkstra 算法。在有向图中，dijkstra 算法将为您提供从起始节点到图中所有其他节点的最短路径，而不仅仅是您想要的几个节点。