電纜鋪設(shè)問題

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

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

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

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