Python，圓形最短路徑

Question

我正在嘗試使奇怪的最短路徑查找方法。但我不知道我能做什麼。

我需要一個算法。我做了一些研究，發現了一些尋找最短路徑的算法，比如Dijkstra算法，Floyd-Warshall算法，Johnson算法。但我認爲他們不符合我的期望。

我想的是：如果在紅點開始，應該通過所有藍點走在紅點結束。

有沒有算法呢？

（我的英語水平實在對不起，我希望你能理解我。）

Answer 1

你的問題是一個Hamiltonian Cycle Problem的變體，這是NP-Complete，所以沒有已知有效的解決方案，以它（最相信一個解決方案不存在，但它還沒有被證實）

哈密爾頓週期問題說：給定一個圖G=(V,E)，找到是否有一個簡單的循環（每個頂點遍歷最多一次）通過所有頂點，並且是一個經典的NP完全問題。

減少非常簡單，給定一個哈密爾頓週期問題，用紅色給一個隨機點着色，剩下的點用藍色表示。當且僅當您的問題的解決方案是新圖上「已修改」問題的簡單路徑時，纔有哈密爾頓週期問題的解決方案。

---

由於問題是NP完全的，這意味着沒有已知的最優有效解決方案。您可以嘗試使用一些對於小圖可能可行的強力技術，或者對近似/啓發式解決方案使用sattle。