電纜鋪設問題

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

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

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

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