2016課程設(shè)計(jì).等多個(gè)文件

第1章需求分 第2章動(dòng)態(tài)規(guī)劃方法的介 第3章基本理論知識(shí)和方 第4章實(shí)驗(yàn)分 參考文 附錄設(shè)計(jì)系統(tǒng)部分源代 1求分在的實(shí)際生活中常常會(huì)出現(xiàn)這樣的問題：倆個(gè)城市之間，是否有道路可通,在有多條通路的情況下，哪一條總程最短；在公路中，即從某一城市出發(fā)，途中必須經(jīng)過哪幾個(gè)城市才會(huì)使花費(fèi)的總代價(jià)最少。通常近距離時(shí)可以憑經(jīng)驗(yàn)或者作出判斷，但若倆個(gè)城市相距較遠(yuǎn)且中間又有多條通路，又如何作出判斷呢？這時(shí)可以一個(gè)簡(jiǎn)單的程序建立一個(gè)交通咨詢系統(tǒng)，作出最優(yōu)決策。在這個(gè)系統(tǒng)中，可以把地圖模型化為一個(gè)圖，結(jié)點(diǎn)表示一段公路的起點(diǎn)和終點(diǎn)，邊的權(quán)值表示公路的長(zhǎng)度，的目標(biāo)是從起點(diǎn)出發(fā)找到一條到達(dá)2態(tài)規(guī)劃方法的介將交通網(wǎng)絡(luò)圖視為帶權(quán)有向本文中只對(duì)倆個(gè)城市之間的距離進(jìn)行）有向圖G，然后將這個(gè)賦權(quán)網(wǎng)絡(luò)圖輸入到計(jì)算機(jī)組中（n表示城市的個(gè)數(shù)。定義帶權(quán)有向定義①若圖G=G(V,E)中各邊e都賦有一個(gè)實(shí)數(shù)W(e),稱為邊e的權(quán),則稱這種圖為賦權(quán)圖,G=G(V,E,W)G=G(V,E)

We

,eEG,u是vi到vj1Wu的權(quán)則稱Wu為u的長(zhǎng)長(zhǎng)最小的i到vj的路Wu稱為最短路徑。nui到vn的通路u使全長(zhǎng)最短即 We迪杰斯特拉算法流城市之間最短路徑（城市之間最短路徑（dijkstra算法2-1dijkstra算法計(jì)算最短路弗洛伊德算法流n次，這樣便可求得由用戶由用戶城市之間最短路徑（floyd算法最后求的從起點(diǎn)城市到最后求的從起點(diǎn)城市到終點(diǎn)城市的最短路徑的間經(jīng)過的城市和從起點(diǎn)城市到途經(jīng)2-4-1floyd3本理論知識(shí)和方最短路基本介60年代以前就卓有成效了其中對(duì)賦權(quán)圖j0有效算法是由荷蘭著名計(jì)算機(jī)Dijsta在1959年首次該算法能夠解決兩指點(diǎn)間的最短路G中一特定點(diǎn)到其它各頂點(diǎn)的最短路徑。DijkstraFordFord算法,但在現(xiàn)實(shí)生活中 在wijDijkstra基本定

定義①若圖G=G(V,E)eW(e),e的權(quán),則稱這種圖為賦權(quán)圖,G=G(V,E)

We

,eEG,u是vi到vj的路Wu的權(quán),Wu為u的長(zhǎng),長(zhǎng)最小的vi到vj的路Wu若要找出從vi到vn的通路u,使全長(zhǎng)最短,即minWuWe 迪杰斯特拉算基本定一般的表述通常有兩種方式，一種用和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN,CLOSE表的方式，這里均采用和臨時(shí)標(biāo)號(hào)的方式?；驹璂DvD[3]=2v32。這里強(qiáng)調(diào)相對(duì)就是說在算法過程中D的值是在不斷近最終結(jié)果但在過程中不一定就等于最短路徑長(zhǎng)度。vviDD為∞。顯然，長(zhǎng)度為D[j]=Min{D|vi∈V}v(v,vj)。那么，vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)vvkD[j]和從vjvkS為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（X）或者是弧(v,x)S中的頂點(diǎn)而最后XD[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。迪杰斯特拉算MAXCOSTSvv出發(fā)到圖上其viD=arcs[LocateVex(G,v),i]vi∈V2）vj，D[j]=Min{D|vi∈V-S3）vV-Svk可達(dá)的最短路徑長(zhǎng)度。G=(V,E)EwV0到其余各點(diǎn)的最短思想內(nèi)V0SV0T中任何頂點(diǎn)的最短路SV0TV0SV0到TVkV0Vk的直接路徑的權(quán)值；或是V0SVk的路徑權(quán)值之和（反證法可證弗洛伊德算基本定n次，這樣便可求得基本原costvivjvivj存cost[i][j]n次試探。首先考慮vivj1v2,即如果（vi,…,v2）和（v2,…,vj）1vi,..,v2,…,vjvivj2的最短路徑。vivj12v3,n次比較，vivj的最短路徑。按此方法，可以同時(shí)求得各對(duì)頂點(diǎn)間的最短路徑。n階方陣序列：A(0),A(1),…,A(n)從上述計(jì)算公式可見，A(1)[i][j]vivj1A(n)[i][j]vivj倆種算法的比從算法的基本思想而言，Dijkstra算法的基本思想是以Vs為起點(diǎn),從圖中找出與其距離最短的頂點(diǎn)。假設(shè)該點(diǎn)為Vi,然后再以Vi作為參照點(diǎn),從余下的頂點(diǎn)中找出與其距離最短的頂點(diǎn),依次類推直到所有的頂點(diǎn)都對(duì)比完為止至止,Vs到各頂點(diǎn)的最短距離就已經(jīng)求出來了。至于具體的最短路徑,常用的方法是“反向追蹤法。即從終點(diǎn)出發(fā),“順藤摸瓜”找到最短距離上的各個(gè)點(diǎn),按照有向圖的方向,就可以得到最短路徑。Floyd算法的基本思想是:從Vs到Vt的最短路徑是以下各種可能路徑中的長(zhǎng)度最小的那條。若<Vs,Vt>存在,則存在路徑{Vs,Vt}。(路徑中不含有其它頂點(diǎn)) 若<Vs,V1>,<V1,Vt>存在,則存在路徑{Vs,V1,Vt}。(路徑中所含頂點(diǎn)序號(hào)不大于1) 若<Vs,V2>,<V2，Vt>存在,則存在一條最短路徑{Vs,?V2?Vj}(路徑中所含頂點(diǎn)序號(hào)不大于2)依次類推,則Vs到Vt的最短路徑應(yīng)是上述這些路徑中路徑長(zhǎng)度最小者。兩種算法的基本思想不同,導(dǎo)致了兩種算法結(jié)果的不同對(duì)于Dijkstra算法而言,其結(jié)果是可求出從某一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑。而Floyd算法的結(jié)果是可以得出圖中任意兩對(duì)頂點(diǎn)之間的最短路徑。而從算法步驟而言，F(xiàn)loyd算法是從鄰接矩陣出發(fā),而且最短路徑可以從序號(hào)矩陣中找出來。最短路徑的權(quán)值從距離矩陣中得出。在許多情況下,圖中的權(quán)重可能是負(fù)值。Dijkstra算法要求每一個(gè)權(quán)重必須大于或等于零,這是該算法Floyd算法計(jì)算最短路徑時(shí)間4驗(yàn)分4.1結(jié)隨機(jī)選擇6個(gè)城市作為一個(gè)交通系統(tǒng)，這6個(gè)城市分別為：長(zhǎng)春，哈爾濱，，G4-14-2在c語言中，把這些城市的信息用一個(gè)c結(jié)構(gòu)體數(shù)組（city[][]）來保存typedef{charname[99];charnum;intn*n2（n表示城市的個(gè)數(shù)2G(INF表示無窮，即倆個(gè)城市之間沒有通路4-3g[6][6]2city4-4程序運(yùn)行圖迪杰斯特拉算法案算法步S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值TWSTWV0Vi的距離值縮短，2、3SW=Vi流程out函數(shù)，獲取dis[][]4-5dijkstra算法流分析，調(diào)4-6程序運(yùn)行圖305060注：此處的最短距離是指從起點(diǎn)城春到各個(gè)頂點(diǎn)城市的最短距離；弗洛伊德算法案算法步uvwuwv比已知的GViVjG[i,j]=d，d表示該路的長(zhǎng)度；否則G[i,j]=無窮大。定義一個(gè)矩陣D用來記錄所點(diǎn)的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化D[i,j]=j。把各個(gè)頂點(diǎn)圖中，比較插點(diǎn)后的距離與原來的距離，G[i,j]=D中則包含了最短通路徑的信息。V5V1DD(5,1)=3V5V1V3，路徑為{V5,V3,V1}D(5,3)=3V5V3D(3,1)=1V3V1流程4-7floyd分析，調(diào)4-8程序運(yùn)行圖305060注：此處的最短距離是指從起點(diǎn)城春到各個(gè)頂點(diǎn)城市的最短距離；結(jié)花費(fèi)變得最少。對(duì)于實(shí)際的交通網(wǎng)絡(luò)圖，可以把城市之間的信息于數(shù)據(jù)庫中，通過對(duì)于對(duì)于最短路徑算法，不僅可以用于出行的計(jì)算，還可以用 地圖等網(wǎng)絡(luò)地圖的應(yīng)搶修、交通指揮、GPS導(dǎo)航等行業(yè)應(yīng)用中使用的非常廣泛，同時(shí)最短路徑也是圖論研究中的題可以通過圖的相關(guān)知識(shí)來解決，特別是在解決最短路徑問題中，顯得尤為重要。參考文1刁在筠，，宿潔，[M].：高等教育2譚浩強(qiáng).C語言程序設(shè)計(jì)[M].：3謝金星，邢文訓(xùn).網(wǎng)絡(luò)優(yōu)化[M].：4嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版）[M].：5、主編《圖論及其算法，中國(guó)科學(xué)技術(shù)大學(xué)，2005年6熊偉，運(yùn)籌學(xué)，第二版，：機(jī)械工業(yè)，20117，數(shù)學(xué)建?；A(chǔ)，第二版，：科學(xué)，20118韓中庚宋明武邵廣紀(jì)，數(shù)學(xué)建模競(jìng)賽獲獎(jiǎng)精選與點(diǎn)評(píng)，：科學(xué)，2007計(jì)系統(tǒng)部分源代C語言（1）intd[100],path[100],final[100];inttypedef{charname[99];charnum;intvoiddijkstra(ints,intn)//{inti,j,k,mi;{}{intmin=999;{}{}}}voidout(ints,intn)//{intb[100];//bs到某頂點(diǎn)的最短路徑上的各個(gè)頂點(diǎn)的編點(diǎn)，從后向前inti,j,p,m;{printf("從起點(diǎn)城市%d到頂點(diǎn)城市%d不存在路徑{//printf("從源點(diǎn)%d到頂點(diǎn)%d的最短路徑長(zhǎng)度為：%d\n",s,i,d[i]);{}for(j=m;j>=0;j--{}}}}{ints,n=6;inti,j;charfrist;charcityc[100];strcpy(c[1].name,"哈爾濱strcpy(c[2].name,"strcpy(c[3].name,"沈陽strcpy(c[4].name,"石家莊printf("請(qǐng)選擇起點(diǎn)城市和終點(diǎn)城春（A，哈爾濱(B),（C，沈陽(D)，石家(E)，太原scanf("%c%c",&frist,&last);{{printf("您選擇的起點(diǎn)城市是%s，終點(diǎn)城市是}}for(intx=0;x<n;x++)for(inti=0;i<n;i++)printf(":%d,:%s}2：#defineINF99999typedef{charname[99];charnum;intint{intintn,i,j,k;intintdis[10][10];charfrist;charlast;cityc[100];strcpy(c[0].name,"長(zhǎng)春strcpy(c[1].name,"哈爾濱strcpy(c[2].name,"strcpy(c[3].name,"沈陽strcpy(c[4].name,"石家莊printf("請(qǐng)選擇起點(diǎn)城市和終點(diǎn)城春（A，哈爾濱(B),（C，沈陽(D)，石家