0

可能重复：
在 Java 中实现 A 星 (A*) 算法

对于一项任务，我必须实现一些搜索算法来解决旅行商问题，我理解这个问题并且我理解算法是如何工作的，我只是不知道如何实现它（我的 Java 不是很好）但是这应该是很容易的部分，但不幸的是，我对 Java 的了解还不足以应用我对算法的了解。

因此，我想知道是否有人可以提供一些关于如何开始使用此功能的提示或技巧，或者甚至可以提供一些好的链接来阅读，如果有一个更容易开始的算法，我还必须实现一些其他算法 id be happy和那个一起去！我已经看过这里但似乎找不到任何相关的内容：/

任何帮助深表感谢！谢谢

4

1 回答 1

0

我不是专家，但我不认为 A* 可以用来解决旅行商问题。我确定您知道 TSP 是 NP 难的，因此确切的解决方案非常复杂，并且并非在每种情况下都存在。我知道（并且已经使用）近似解决方案的最简单方法是所谓的“模拟退火”，这是一种随机方法（即随机！）。

这个想法很简单。您将这些点组织成一个列表，该列表表示所有节点之间的路径（这称为“巡回”）。计算游览时间并保存长度。然后，您选择一个随机子列表并简单地反转它。计算新的长度。如果新列表较短，则保留它，否则丢弃它。只需重复这些步骤 100/1,000/10,000,000 次（取决于点数），您就会得到一个合理的近似值。

例如，假设有 5 个点（伪代码）...

List tour = [e, b, a, d, c]
int len = tourLength(tour)
List newTour = [e, b] + [d, a] + [c] // a and d have been reversed
int newLen = tourLength(newTour)
if(newLen < len) {
    tour = newTour
}

对于 10 个点，100 次迭代应该会产生一个好的结果。

于 2012-12-07T17:13:33.040 回答