使用Neo4j解決TSP問題

Question

使用Neo4j解決旅行商問題或Multi-TSP問題是否可行？

我必須找到覆蓋所有節點的最佳路徑。我試圖找到所有可能的路徑，然後找到最小距離。隨着節點數量的增加，執行時間呈指數增長。

Answer 1

旅行推銷員問題是quintessential example of an NP-hard problem。所以執行時間不會成倍增加，如果是的話，它會是多項式。實際上可能比這更糟糕。 :)

這些算法默認情況下不在neo4j中。你可以用java和cypher做它們嗎？是的，當然。你應該這樣做嗎？我看到的實際建議是，一旦你到達大約100個城市，開始做這件事變得不切實際。具有最佳算法的研究系統現在正在爲3萬-5萬個城市解決TSP問題。就我個人而言，我不建議現在在兩個數量級的研究系統內嘗試嘗試它，除非你有很多硬件和計算可以投入它（例如，通過諸如租用的EC2計算之類的東西）。

就算法而言，有Held-Karp algorithm這是O（n^2 * 2^n）。哎喲。 Wikipedia has other suggestions as well。因此，我認爲從理論計算機科學的角度來看，這是可行的，你必須親自編寫它，算法非常複雜（從執行和增長需要很長時間）。從實際的工程學角度來看，對於不到100個城市完全可行，而在n> = 10,000左右的情況下嘗試它會非常困難和昂貴。請參閱this related stack overflow question。