必經(jīng)節(jié)點的最短路徑算法研究.pdf

1、目前，最短路徑問題基本上是一個在各個領(lǐng)域中的基本問題，包括應(yīng)用數(shù)學(xué)、計算機(jī)科學(xué)、工程、管理、和運算，是國內(nèi)外大量學(xué)者關(guān)注的研究熱點問題。網(wǎng)絡(luò)模型是一種有效地方法，它模擬現(xiàn)實世界中的問題，同時被廣泛應(yīng)用在許多不同類型的系統(tǒng)：信息通訊、機(jī)械、電子、制造業(yè)和物流業(yè)等。傳統(tǒng)的最短路徑問題針對的是兩點之間的最短路徑，完全可以用簡單算法求出，例如Dijkstra算法、Floyd算法,Bellman_Ford算法等。然而，在實際應(yīng)用中，存在著更復(fù)雜的

2、問題，如復(fù)雜的結(jié)構(gòu)，復(fù)雜的約束，和多個目標(biāo)同時處理，傳統(tǒng)求解最短路徑問題根本不能滿足人們的需要。如果模型較大、或是中間有許多點必須經(jīng)過，并且要求在短時間內(nèi)找到這么一條最短路徑，那么問題就變得復(fù)雜了。
　　本文主要研究了針對不同規(guī)模與必經(jīng)點多少的最短路徑問題，并針對不同問題設(shè)計了不同的求解最短路徑算法，同時給出算法的流程；最后針對不同的算法給出相應(yīng)的實例進(jìn)行計算和分析，驗證出模型與算法的適用性。其主要工作如下：
　　1.針對小

3、型規(guī)模的圖的最短路徑問題進(jìn)行研究與分析，提出了深度遍歷窮盡算法，并比較其他傳統(tǒng)算法的優(yōu)劣，利用相應(yīng)的實例進(jìn)行計算與比較；
　　2.針對中型規(guī)模的圖的最短路徑問題進(jìn)行研究與分析，提出了縮圖后再深度遍歷的算法，并比較全局深度遍歷算法的優(yōu)劣，利用相應(yīng)的實例進(jìn)行計算與比較；
　　3.針對大型規(guī)模的圖的最短路徑問題進(jìn)行研究與分析，提出了改進(jìn)的遺傳算法，并比較其他算法的優(yōu)劣，利用相應(yīng)的實例進(jìn)行計算與比較。
　　在所閱讀的文章中，大