蟻群算法的優(yōu)勢在哪里？

圖論中很多問題都是求某個規(guī)則下的最短路徑，但因?yàn)橐?guī)則不同，這些問題也有著本質(zhì)上的不同，不能簡單地都?xì)w于“最短路徑”問題，某些問題已有有效算法，有些問題至今沒有有效算法。

Prime 算法和 Kruskal 算法都是用來求加權(quán)連通簡單圖中權(quán)和最小的支撐樹（即最小樹）的，Prime算法的時間復(fù)雜度為O（n^2） （n 為頂點(diǎn)數(shù)），Kruskal 算法的時間復(fù)雜度為 O（eln（e）） （e為邊數(shù)），這兩種算法都是多項(xiàng)式時間算法，也就是說，最小樹問題已經(jīng)有了有效算法去求解，屬于P問題。

Dijkstra 算法求解的是加權(quán)連通簡單圖中一個頂點(diǎn)到其它每個頂點(diǎn)的具有最小權(quán)和的有向路，最簡單版本的時間復(fù)雜度是O（n^2），也是多項(xiàng)式時間算法。

而蟻群算法是一種近似算法，它不是用來解決已存在精確有效算法的問題的，而是用來解決至今沒有找到精確的有效算法的問題的，比如旅行商問題（TSP）。

旅行商問題也可以說是求“最短路徑”，但它是求一個完全圖的最小哈密頓圈，這個問題至今未找到多項(xiàng)式時間算法，屬于NPC問題，也就是說，當(dāng)問題規(guī)模稍大一點(diǎn)，現(xiàn)有的精確算法的運(yùn)算量就會急劇增加。

?

在上圖中，可以看到，當(dāng)問題規(guī)模為10時，復(fù)雜度為O（3.4n^3） 的算法運(yùn)行時間要0.0034s，復(fù)雜度為O（2^n） 的算法運(yùn)行時間要0.001s，此時相差還不大，但當(dāng)問題規(guī)模增加到100時，前者的運(yùn)行時間只是增加到了3.4s，而后者的運(yùn)行時間則增加到了4×10^16年！

因?yàn)閷?shí)際問題的規(guī)模都比較大，100還是小數(shù)字，所以對一個問題，都努力尋求多項(xiàng)式算法。但也有問題目前還沒有找到多項(xiàng)式時間的精確算法，比如旅行商問題，因此就產(chǎn)生了各種近似算法，以解的質(zhì)量來換取效率，尋求滿意解而不是最優(yōu)解，蟻群算法就是其中一種。

所以，針對本問題的提法，蟻群算法和Prime 算法或Kruskal 算法等是兩個不同層面上的算法，基本沒有比較的必要，但可以做辨析：

1、Prime 算法，Kruskal 算法，Dijkstra 算法都只是解決某一種問題的，這些問題有了這些算法，就沒有必要使用蟻群算法。

2、蟻群算法可以用來解決一些尚未找到有效算法的問題，而且蟻群算法還是元啟發(fā)式算法（Metaheuristic），是一種算法框架，可以在其基本思想上針對不同問題做改進(jìn)從而應(yīng)用到不同問題上去。

3、蟻群算法可以和其它近似算法相比較，而這些算法本身也根據(jù)問題的不同有較大的改進(jìn)彈性。

*圖片來源：Sara Baase， Allen Van Gelder，Computer Algorithms： Introduction to Design and Analysis，影印版第三版，高等教育出版社，2001 （第49頁 圖1.5）