怎麼用蟻群演算法從兩地之間的路徑網中選擇最短路徑？

1樓：KevinLiu

利用蟻群優化演算法，從兩地之間的路徑網中找到最短路徑和TSP問題，本質是一樣的。

1、兩點之間的最短路徑與TSP中的最短路徑本質都是找到最優路徑，不同的是約束不同，前者只有起點和終點的約束（當然也可能加上每條子路徑最多經過1次的人工限制，避免轉圈），後者的約束是每個點隻且必須經過一次；

2、從處理邏輯上來說，前者有較為成熟的方式，比如Dijkstra， A*等演算法，在針對小規模的網路時效率是已經是很好的，使用蟻群優化演算法的必要性較低；後者因為有組合優化，其解空間更為龐大複雜，常規的精確數學的演算法一般較難處理；蟻群優化演算法的第1個應用即為TSP。

3、蟻群優化演算法的原理就是兩點間的最短路徑，所以兩點間的最優路徑是完全可以使用蟻群優化演算法來求解的，但其求解效率和求解精度在中小規模上比不上目前主流的演算法（Dijkstra, A*)等，所以應用較少，但如果是乙個超大規模的兩點間最短路徑的話，蟻群優化演算法則能充分發揮其優勢。

蟻群優化演算法本質上也是乙個強化學習演算法（即智慧型體在乙個環境中不斷試錯來找到最優獎勵），結合目前較熱的強化學習研究，這也是目前蟻群優化演算法的乙個新的研究方向吧。