將航點添加到A *圖搜索

Question

我有能力使用A *計算起點和終點之間的最佳路線。現在，我在我的起點和終點之間加入了一個航點，通過將A *應用於我所有點的排列中。

實施例：

我想從點1至點4中。另外，我要通過點2和3

餘計算的（1，2，3，4的排列）：

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

然後，對於每個排列，我計算A *路徑從第一到第二，然後將其附加到路徑從第二到第三，那麼第三到第四。

當我對每個排列進行計算時，我按距離排序路線並返回最短路線。

顯然，這工作，但涉及到很多計算的，當我有6個航點完全倒塌（8項排列爲40320 :-)）

有沒有更好的方式來做到這一點？

Answer 1

首先，你應該存儲所有的中間計算。一旦你計算出從1到2的路線，你不應該重新計算它，只需在表格中查找即可。 其次，如果圖形是無向的，則從2到1的路徑與從1到2的路徑具有完全相同的距離，因此您不應該重新計算它。

最後，無論如何，你將有一個算法，指數的點數你需要通過。這與旅行商問題非常相似，如果包含所有可用點，則會出現這個問題。問題是NP完全的，即它具有複雜性，指向航點的數量。

所以，如果你有很多點你必須通過，指數崩潰是不可避免的。

Answer 2

作爲前面提到的答案，這個問題是NP完全旅行銷售人員問題。

有一個比你使用的更好的方法。最先進的TSP解算器是由於Georgia Tech's Concorde solver。如果你不能簡單地使用他們自己的免費程序或使用他們的API，我可以描述他們使用的基本技術。

爲了解決TSP問題，他們從一個叫做Lin-Kernighan啓發式的貪心啓發式開始，生成一個上界。然後他們在TSP的混合整數規劃公式中使用分支和剪切。這意味着他們編寫了一系列線性和整數約束條件，這些約束條件在求解時爲您提供了TSP的最佳路徑。他們的內部循環調用線性規劃解算器，如Qsopt或Cplex來獲得下限。

正如我所說，這是最先進的，所以如果你正在尋找一種更好的解決TSP問題的方法，那麼這裏是最好的。他們可以在幾秒鐘內處理超過10,000個城市，特別是在對稱的平面TSP上（我懷疑這是您正在開發的變體）。

如果您最終需要處理的航點的數量很少（例如10至15的數量級），那麼您可以使用minimum spanning tree heuristic進行分支定界搜索。這是許多介紹性AI課程的教科書練習。更多的路點可能會超過該算法的實際運行時間，您將不得不使用Concorde。