使用 A* 解决旅行商 [英] Using A* to solve Travelling Salesman

问题描述

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

I've been tasked to write an implementation of the A* algorithm (heuristics provided) that will solve the travelling salesman problem. I understand the algorithm, it's simple enough, but I just can't see the code that implements it. I mean, I get it. Priority queue for the nodes, sorted by distance + heuristic(node), add the closest node on to the path. The question is, like, what happens if the closest node can't be reached from the previous closest node? How does one actually take a "graph" as a function argument? I just can't see how the algorithm actually functions, as code.

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

I read the Wikipedia page before posting the question. Repeatedly. It doesn't really answer the question- searching the graph is way, way different to solving the TSP. For example, you could construct a graph where the shortest node at any given time always results in a backtrack, since two paths of the same length aren't equal, whereas if you're just trying to go from A to B then two paths of the same length are equal.

您可以通过始终首先到达最近的方式来推导出某些节点永远无法到达的图.

You could derive a graph by which some nodes are never reached by always going closest first.

我真的不明白 A* 如何适用于 TSP.我的意思是，找到一条从 A 到 B 的路线，当然，我明白了.但是 TSP 呢?我看不到连接.

I don't really see how A* applies to the TSP. I mean, finding a route from A to B, sure, I get that. But the TSP? I don't see the connection.

推荐答案

我找到了解决方案 这里

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

Use minimum spanning tree as a heuristic.

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

Set Initial State: Agent in the start city and has not visited any other city

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

Goal State: Agent has visited all the cities and reached the start city again

后继函数:生成所有尚未访问的城市

Successor Function: Generates all cities that have not yet visited

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

Edge-cost: distance between the cities represented by the nodes, use this cost to calculate g(n).

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

h(n): distance to the nearest unvisited city from the current city + estimated distance to travel all the unvisited cities (MST heuristic used here) + nearest distance from an unvisited city to the start city. Note that this is an admissible heuristic function.   You may consider maintaining a list of visited cities and a list of unvisited cities to facilitate computations.

这篇关于使用 A* 解决旅行商的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！