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

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

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

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