algorithm - 使用 A* 解决旅行商问题

Question

我的任务是编写 A* 算法(提供启发式算法)的实现，以解决旅行商问题。算法我懂，够简单了，就是看不到实现它的代码。我的意思是，我明白了。节点的优先级队列，按距离 + 启发式(节点)排序，将最近的节点添加到路径中。问题是，如果不能从前一个最近的节点到达最近的节点会发生什么？实际上如何将“图形”作为函数参数？我只是看不出算法实际上是如何作为代码运行的。

我在发布问题之前阅读了维基百科页面。反复。它并没有真正回答问题——搜索图表与解决 TSP 有很大不同。例如，您可以构建一个图，其中任何给定时间的最短节点总是导致回溯，因为两条相同长度的路径不相等，而如果您只是想从 A 到 B，那么两条路径相同长度的是相等的。

您可以推导出一个图，其中某些节点永远不会通过始终最接近的第一个到达。

我真的不明白 A* 如何应用于 TSP。我的意思是，找到一条从 A 到 B 的路线，当然，我明白了。但是 TSP？我没有看到连接。

Answer 1

我找到了解决方案 here

使用最小生成树作为启发式算法。

设置初始状态:agent在起始城市，没有访问过任何其他城市

目标状态:agent已访问所有城市并再次到达起始城市

后继函数:生成所有还没有访问过的城市

Edge-cost:节点代表的城市之间的距离，用这个cost来计算g(n)。

h(n):从当前城市到最近的未访问过的城市的距离 + 旅行所有未访问过的城市的估计距离(此处使用 MST 启发式算法)+ 从未访问过的城市到起始城市的最近距离。请注意，这是一个可接受的启发式函数。您可以考虑维护一个访问过的城市列表和一个未访问过的城市列表以方便计算。