算法找出爲了訪問圖形

Question

我有與具有成本每個邊緣的起始節點圖的節點......我需要一個算法來找出其中我有次序地訪問所有這些節點，以便我走過的總距離最少...請爲此建議一個算法...

Answer 1

聽起來像travelling salesman problem，或者是一個近似的變體，儘管如果圖形不完整，它會受到限制。

Answer 2

除非你瞭解一下圖形結構，你是在處理所謂的NP完全問題。對於一般問題（沒有限制），找到近似解決方案並沒有令人滿意的啓發式方法。

的問題確實是旅行商問題，到目前爲止，只有蠻力嘗試所有的路徑是保證找到最佳路徑的算法，但它是不切實際的大圖。

Answer 3

也許你可以使用修改A* Algorithm。通常情況下，您將從X開始，到達Y時結束。在修改版本中，當到達某個節點Y但您訪問完所有節點時，不會停止。還要注意的是，如果訪問了某個節點，則從另一個節點前往它是沒有意義的，那就應該這樣做。