電纜鋪設(shè)問(wèn)題

1、1電纜鋪設(shè)問(wèn)題摘要本文解決的是軍營(yíng)電纜鋪設(shè)最優(yōu)策略的圖論問(wèn)題。首先，根據(jù)題意分析12個(gè)營(yíng)之間邊的權(quán)值特點(diǎn)，然后，確定采用算法和標(biāo)號(hào)算法解決問(wèn)primDijkstra題，最后，自定義函數(shù)，建立以最小權(quán)值和為目標(biāo)函數(shù)的最優(yōu)路徑問(wèn)題。ijd對(duì)于問(wèn)題一：假設(shè)各個(gè)營(yíng)點(diǎn)為頂點(diǎn)，各營(yíng)點(diǎn)間的路線(xiàn)為邊，通過(guò)采用算法求得原圖的最小生成樹(shù)進(jìn)而求出最短鋪設(shè)路線(xiàn)。采用類(lèi)比推理的思想，prim由易到難推出目標(biāo)函數(shù)為最小權(quán)值和，用軟件編程求解出最短電纜鋪設(shè)matla

2、b長(zhǎng)度為206千米。通過(guò)將結(jié)果圖與原題圖進(jìn)行對(duì)比，可以判斷出結(jié)果的合理性。下表為問(wèn)題一中電纜鋪設(shè)具體路線(xiàn)：（單位：千米）邊13111188482212129126125510107總長(zhǎng)354518155231514171613216對(duì)于問(wèn)題二：同問(wèn)題一，將各個(gè)營(yíng)點(diǎn)假設(shè)為頂點(diǎn)，各營(yíng)點(diǎn)間的路線(xiàn)假設(shè)為邊，目標(biāo)函數(shù)依然為最小權(quán)值和。通過(guò)標(biāo)號(hào)算法運(yùn)用軟件編程Dijkstramatlab求解出在問(wèn)題二條件下的最短電纜鋪設(shè)長(zhǎng)度為308千米。通過(guò)將結(jié)果

3、圖與原題圖進(jìn)行對(duì)比，可以判斷出結(jié)果的合理性。下表為問(wèn)題二中電纜鋪設(shè)具體路線(xiàn)：（單位：千米）邊131111415171849710長(zhǎng)3545202729182613邊1068221212912612582107長(zhǎng)21523151417513總長(zhǎng)308由于各邊所選用電纜線(xiàn)的截面以及線(xiàn)損（權(quán)值）在規(guī)劃方案確定之前是無(wú)法知道的，所以在模型改進(jìn)中提出算法的改進(jìn)。本模型還適用于單向最短prim路線(xiàn)問(wèn)題。關(guān)鍵詞：類(lèi)比推理無(wú)向圖算法算法最小生成樹(shù)pri

4、mDijkstra3假設(shè)三：不考慮其它電纜的故障對(duì)所求線(xiàn)路電纜的影響；假設(shè)四：不考慮各營(yíng)的大小和體積，各營(yíng)可視為一個(gè)個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間的線(xiàn)路可以視為無(wú)向圖的直線(xiàn)邊。3.符號(hào)說(shuō)明符號(hào)符號(hào)意義e無(wú)向圖中各點(diǎn)所對(duì)應(yīng)的邊()ew無(wú)向圖中各點(diǎn)所對(duì)應(yīng)的邊的權(quán)值V無(wú)向圖中節(jié)點(diǎn)的點(diǎn)集ijD無(wú)向圖中任意兩點(diǎn)的距離v無(wú)向圖中節(jié)點(diǎn)ijd無(wú)向圖中任意兩點(diǎn)的連接狀態(tài)0ijd????，（不連接）1，（連接）3.數(shù)據(jù)分析根據(jù)原題所給圖一，做出如下權(quán)值表：表一：各營(yíng)點(diǎn)間