用A*来解决旅行推销员

Question

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

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

您可以通过始终最接近的方式派生一个图形,通过该图形永远不会到达某些节点.

我真的不知道A*如何适用于TSP.我的意思是,找到从A到B的路线,当然,我明白了.但TSP？我没有看到连接.

Answer 1

我在这里找到了解决方案

使用最小生成树作为启发式.

在初始城市设置初始状态:代理,但未访问任何其他城市

目标状态:代理已经访问了所有城市并再次到达了起始城市

后继功能:生成所有尚未访问过的城市

边缘成本:节点所代表的城市之间的距离,使用此成本来计算g(n).

h(n):距离当前城市最近的未访问城市的距离+所有未访问城市的估计距离(此处使用的MST启发式)+距离未访问城市到起始城市的最近距离.请注意,这是一个可接受的启发式功能.您可以考虑维护一个访问过的城市列表和一个未访问的城市列表,以便于计算.

Answer 2

回答你的问题之一...

要将图形作为函数参数传递，您有多种选择。您可以将指针传递给包含所有节点的数组。如果它是一个完全连接的图，您可以仅传递一个起始节点并从那里开始工作。最后，您可以编写一个图形类，其中包含您需要的任何数据结构，并传递对该类实例的引用。

至于您关于最近节点的其他问题，A* 搜索不是会根据需要回溯的一部分吗？或者您可以实施自己的回溯来处理这种情况。