A *算法如何应用于旅行商问题？

我最近了解到 * 算法可以应用于旅行商问题。Bot我们如何在此处准确定义起点和目标，以及如何将权重应用于节点（启发式）？

有人可以告诉我如何在这里应用A *吗？

*是Dijsktra的派生词，我认为不能以这种方式使用。首先，TSP通常从任何节点开始。但是，更重要的是，这些算法试图找到两点之间的最短路径，而与访问的节点数量无关。实际上，它们取决于以下事实：从S到T通过某个节点A的最短路径，如果成本相同，则从S到A的路径就无关紧要。

我看到此功能的唯一方法是，如果您生成了一个表示访问的节点的新图。例如，在优先级队列中，您将放置访问的节点集和当前节点。这将可能导致检查$ n2 ^ n

$个节点（这并不是TSP动态编程解决方案的运行时间，http:

//www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/ BOOK2 /

NODE49.HTM）。到目前为止，这并不好，但是通过使用A

*代替Dijsktra，您可能能够找到在合理的时间内运行的启发式方法。

为此，您的起始节点将为（1，{}），而您的结束节点将为（1，{1..n}）。您将模仿原始图形的边缘权重。至于启发式的建议，则由您自己决定。