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

问题描述

我一直在负责编写的A *算法（提供启发式），将解决旅行商问题的实现。我理解的算法，这是很简单的，但我就是不能看到code实现它。我的意思是，我明白了。优先级队列中的节点，按距离排序+启发式（点），加上最近的节点的路径。现在的问题是一样，如果最近​​的节点无法从previous最近节点达到了会发生什么？怎样才能真正采取了曲线作为函数参数？我看不出实际的算法功能，code。

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

边缘费用：城市之间的距离再由节点psented $ P $，用这笔费用来计算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屋！