找到所有城市的路径的算法

Question

我希望已经有一个直接的算法作为解决方案，但不确定这种类型的问题被调用，因此在哪里寻找解决方案。 它在某些方面类似于旅行商问题，但我认为它应该更简单。 问题的主要区别在于城市之间有有限的连接（每个城市3到6个）。 路径不需要返回到起始，只是它只访问一个城市。此外，连接的长度都是相同的，所以完整路径长度将始终相同（不是最短距离问题）。有84个引用，因此最后的路径总是87个单位长。 基本上我正在寻找任何可以从随机开始的解决方案，只需要一次到所有的城市。我希望有一个“随机”的解决方案，看起来不会有序。 有关此类问题的调用以及我可能在哪里找到算法的任何建议。 谢谢。

Answer 1

您正在查找Hamiltonian Path。不幸的是，这个问题是NP完全的，尽管图中的顶点有助于其易处理性有限。您可以在链接的维基百科页面或this answer中找到有关解决此问题的更多信息。