Python，圆形最短路径

Question

我正在尝试使奇怪的最短路径查找方法。但我不知道我能做什么。

我需要一个算法。我做了一些研究，发现了一些寻找最短路径的算法，比如Dijkstra算法，Floyd-Warshall算法，Johnson算法。但我认为他们不符合我的期望。

我想的是：如果在红点开始，应该通过所有蓝点走在红点结束。

有没有算法呢？

（我的英语水平实在对不起，我希望你能理解我。）

Answer 1

你的问题是一个Hamiltonian Cycle Problem的变体，这是NP-Complete，所以没有已知有效的解决方案，以它（最相信一个解决方案不存在，但它还没有被证实）

哈密尔顿周期问题说：给定一个图G=(V,E)，找到是否有一个简单的循环（每个顶点遍历最多一次）通过所有顶点，并且是一个经典的NP完全问题。

减少非常简单，给定一个哈密尔顿周期问题，用红色给一个随机点着色，剩下的点用蓝色表示。当且仅当您的问题的解决方案是新图上“已修改”问题的简单路径时，才有哈密尔顿周期问题的解决方案。

---

由于问题是NP完全的，这意味着没有已知的最优有效解决方案。您可以尝试使用一些对于小图可能可行的强力技术，或者对近似/启发式解决方案使用sattle。