我目前的想法是: 从点 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 。有人对如何解决这个问题有任何建议吗?
最佳答案
您是否考虑过使用有向图然后实现 dijkstra 算法。在有向图中,dijkstra 算法将为您提供从起始节点到图中所有其他节点的最短路径,而不仅仅是您想要的几个节点。
关于c++ - 旅行商启发式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40924294/