算法 – 使用A *来解决旅行推销员

我的任务是编写一个解决旅行推销员问题的A *算法(提供启发式)的实现.我理解算法,这很简单,但是我看不到实现它的代码.我的意思是我得到它.通过距离启发式(节点)排序的节点的优先级队列,将最靠近的节点添加到路径上.问题是,如果最近的节点不能从前一个最接近的节点到达,会发生什么?实际上如何将“图形”作为函数参数?我只是看不到算法如何实际运作,作为代码.

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

您可以导出一个图,通过始终最接近第一个节点永远不会达到一些节点.

我真的不明白A *如何适用于TSP.我的意思是找到一条从A到B的路线,肯定是这样.但TSP?我看不到连接.

我找到了一个解决方案 here

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


初始状态:启动城市的代理人,并未访问任何其他城市

目标国家:代理人已经访问了所有的城市,再次到达了起始城市

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

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

h(n):距离当前城市距离最近的未访问城市的距离估计距离所有未访问城市(MST启发式使用)距离未访问城市到起始城市的距离.请注意,这是一个可接受的启发式函数.

您可以考虑维护受访城市的列表和一个未访问城市的列表,以便于计算.

相关文章
相关标签/搜索