imsz5460
通信網(wǎng)絡(luò)規(guī)劃的最短路徑（最小生成樹(shù)的2種算法介紹）
《大話數(shù)據(jù)結(jié)構(gòu)》中在“圖”的那一章節(jié)有這樣一個(gè)實(shí)例：假設(shè)你是電信實(shí)施工程師，需要為一個(gè)鎮(zhèn)的九個(gè)村莊架設(shè)通信網(wǎng)絡(luò)做設(shè)計(jì)。村莊位置大致如下圖，之間連線的數(shù)字表示村與村間的可通達(dá)直線距離（個(gè)別如v0與v6，v6與v8，v5與v7未測(cè)算距離是因?yàn)橛懈呱交蚝矗挥杩紤]）。你們領(lǐng)導(dǎo)要求你必須用最小的成本完成這次任務(wù)。你說(shuō)怎么辦？
我之前在某家設(shè)計(jì)院也是做網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)的，而且覺(jué)得很有實(shí)際意義，所以拿出來(lái)給大家分享一下。其實(shí)這個(gè)案例就是查找連通網(wǎng)的最小生成樹(shù)。這術(shù)語(yǔ)不懂也沒(méi)關(guān)系，我們不管它叫什么。
有人說(shuō)，這還不簡(jiǎn)單嘛，我憑著直覺(jué)就能做出來(lái)。不排除你有這種能力，有時(shí)候人類的“直覺(jué)”真的是強(qiáng)大，也不知道人類是如何進(jìn)化到這么聰慧的。
有人說(shuō)，把所有可能的方案羅列出來(lái)，再一一比對(duì)，找到最短路徑的那個(gè)方案，就行了。這確實(shí)是個(gè)好辦法，實(shí)際上我們也是這樣做的。那么怎么去羅列所有的方案呢？。
為了便于描述上面的圖，我們構(gòu)造圖的鄰接矩陣。如下圖所示：
在單純的計(jì)算或者有規(guī)律的運(yùn)算方面，我們很容易想到借助計(jì)算機(jī)來(lái)幫忙解決。 剛剛我提到人類的直覺(jué)是很強(qiáng)大的，比如有的人答題的時(shí)候直接省略了步驟得出了結(jié)果，而要他寫詳細(xì)的步驟可能他也說(shuō)不太清。計(jì)算機(jī)是沒(méi)有直覺(jué)的，某些我們認(rèn)為很簡(jiǎn)單的東西她可能要運(yùn)算很多次，而且你還得教她怎樣按照她自己“有限的能力”去執(zhí)行，可是往往我們不知道怎么去教計(jì)算機(jī)，也就是具體的怎樣寫代碼。
這里介紹兩種思路，也就是兩個(gè)算法：
一、一種思路是這樣的：
從v0（可以任意選定一點(diǎn)，這里選v0）開(kāi)始，找到與其相連的最短的路徑，定義兩個(gè)一維數(shù)組a，b。a存儲(chǔ)相關(guān)頂點(diǎn)的權(quán)值（邊長(zhǎng)度），b存儲(chǔ)對(duì)應(yīng)的頂點(diǎn)。路徑(b[i],i)的權(quán)值為a[i].i為0至8的整數(shù)，v0為起點(diǎn)至各點(diǎn)的權(quán)值如下所示（實(shí)際中我們用65535來(lái)代表無(wú)窮大）。
求a數(shù)組中的最小值，為10，對(duì)應(yīng)的i為1，標(biāo)記邊（v0，v1）并讓ai置為0，代表vi已經(jīng)納入生成路徑了（此時(shí)i為1）。
然后從v1開(kāi)始，排除a[i]=0對(duì)應(yīng)的頂點(diǎn)vi，當(dāng)（v1，vi）的權(quán)值小于此時(shí)a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
求a數(shù)組中的最小值，為11，對(duì)應(yīng)的i為5，標(biāo)記邊（v0，v5）并讓a5置為0，代表v5已經(jīng)納入生成路徑了。
然后從v5開(kāi)始，排除a[i]=0對(duì)應(yīng)的頂點(diǎn)vi，當(dāng)（v5，vi）的權(quán)值小于此時(shí)a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式