西安市經(jīng)開區(qū)公共自行車服務系統(tǒng)優(yōu)化方案設計

年4月19日西安市經(jīng)開區(qū)公共自行車服務系統(tǒng)優(yōu)化方案設計文檔僅供參考，不當之處，請聯(lián)系改正。摘要本文研究的是西安市經(jīng)開區(qū)公共自行車的分配和調(diào)度優(yōu)化問題，經(jīng)過合理的分配方案和調(diào)度方案，以滿足所有租賃點對自行車的數(shù)量需求及調(diào)度花費時間最少的要求。建立0—1規(guī)劃模型，自行車分配調(diào)度模型，以及租賃網(wǎng)點設置模型，經(jīng)過最小生成樹算法和啟發(fā)式搜索等求解，較好的實現(xiàn)了自行車服務系統(tǒng)的優(yōu)化。對于第一問，依據(jù)租賃點的需求和約束條件分配自行車；根據(jù)經(jīng)緯度和Floyd算法求出各租賃點之間的距離，引入0—1變量表示租賃點間是否發(fā)生調(diào)度，采用最小生成樹算法，經(jīng)過租賃點的時間及裝卸自行車的時間為權重，經(jīng)過Matlab編程用避圈法求解最小生成樹，求得的路徑就是最佳行車路線，每輛車調(diào)度一次平均用時135分鐘，完成一天的調(diào)度總時間為806分鐘。對于第二問，約束為投入經(jīng)費總數(shù)和租賃點自行車需求，目標是設置的租賃點能夠覆蓋更大的面積，而且整個調(diào)度花費時間較少，用excel將備選租賃點需求量由大到小排序，選取自行車需求較多且三個時間段需求相差小的網(wǎng)點，應用動態(tài)規(guī)劃算法，設新增租賃點數(shù)為k,代入經(jīng)費約束即可得到k值不大于28，經(jīng)過調(diào)整新增租賃點采用啟發(fā)式搜索求新增網(wǎng)點和車輛的合適分配方案，編程得出新增網(wǎng)點為26個，自行車總數(shù)697輛。對于第三問，經(jīng)過增加調(diào)度車來減少調(diào)度時間，采用租賃點分區(qū)的思想，每輛調(diào)度車只在一個分區(qū)內(nèi)調(diào)度，提高調(diào)度的效率。設新增調(diào)度車p輛，根據(jù)問題二的分配結果用問題一的模型計算調(diào)度花費的時間，各分區(qū)內(nèi)都采用最小生成樹算法求解最優(yōu)調(diào)度路線，改變p值和分區(qū)，直到所有分區(qū)都能滿足150分鐘內(nèi)調(diào)度完畢，即為新增調(diào)度車數(shù)。關鍵詞：Floyd算法最小生成樹啟發(fā)式搜索0-1變量Matlab編程西安市經(jīng)開區(qū)公共自行車服務系統(tǒng)優(yōu)化方案設計目錄一、問題的背景與重述 21.1問題背景 21.2問題重述 2二、問題分析 32.1問題一分析 32.2問題二分析 32.3問題三分析 3三、問題的基本假設 4四、符號規(guī)定 4五、模型的建立與求解 5問題一的模型： 5問題二的模型 7問題三的模型： 10六、模型的分析和檢驗： 136.1.模型的檢驗 136.2.模型的優(yōu)點 146.3.模型的缺點 14七、模型的推廣 15八、參考文獻 15九、附錄： 15一、問題的背景與重述1.1問題背景近年來，中國各級城市的機動車數(shù)持續(xù)增長引發(fā)了道路擁堵、空氣污染等問題，而租借公共自行車服務系統(tǒng)能夠從一定程度上緩解這一現(xiàn)象。然而，居民居住地和交通站點一般都有一段距離，這段不遠的距離以及現(xiàn)實存在的公共交通擁擠現(xiàn)象則使居民乘坐公共交通的意愿降低，公共自行車服務系統(tǒng)已被證明能夠從一定程度上解決這一問題。將租賃點設置在合適的位置，能夠覆蓋更多的面積提高效率，避免資源浪費，根據(jù)租賃點自行車的需求量和使用頻率，合理的分配自行車，并經(jīng)過調(diào)度專用車在使用高峰期階段進行合理調(diào)度，盡量使調(diào)度過程花費短的時間，且不能影響自行車的租用，最大程度地滿足居民對車輛的需求，提高車輛利用率。1.2問題重述西安市經(jīng)開區(qū)公共自行車服務系統(tǒng)已建成租賃點30個，自行車總量達到850輛?，F(xiàn)已知前期的30個租賃點位置，每個租賃點能夠放置的車輛數(shù)目不能超過40輛，且一般車輛總數(shù)至少應超出需求量的10%。將實時觀測到的數(shù)據(jù)歸結到3個車輛使用需求最多的時間段（可認為每天的需求量不變）居民可在任意一個租賃點還車，在某個租賃點還車的概率與租車點和還車點的距離成反比，且假設居民的騎行距離不超過2km；假設車輛調(diào)度只在車輛需要最多的時間段進行，當前西安經(jīng)開區(qū)用于運送公共自行車的調(diào)度車有2輛，每輛每次可運50輛自行車，調(diào)度車平均時速30km/h，每輛自行車裝（或卸）平均耗時1min；假設建設一個租賃服務網(wǎng)點需要50000元，在使用周期內(nèi)，購買、養(yǎng)護一輛自行車需要1000元。（1）根據(jù)當前經(jīng)開區(qū)網(wǎng)點自行車需求情況等信息，若要求調(diào)度平均耗時盡量少，針對已有的30個租賃點來決定最優(yōu)車輛分配方案、調(diào)度方案，并給出完成調(diào)度所耗費的時間。（2）假設經(jīng)開區(qū)公共自行車服務系統(tǒng)三期建設準備投入建設經(jīng)費200萬元，據(jù)此建立數(shù)學模型，確定新增租賃點數(shù)目、位置以及合適的放置車輛數(shù)目。（3）針對問題（2），進一步研究，如果要求在150min內(nèi)完成調(diào)度，是否需要增加調(diào)度車輛（購置調(diào)度車輛費用由其它項目經(jīng)費解決，不包含在三期建設提供的200萬元經(jīng)費中間）？并寫出該情形下的自行車調(diào)度方案。二、問題分析2.1問題一分析經(jīng)過對本問題的分析，根據(jù)結論要保證調(diào)度平均耗時最少，則在每個時間段內(nèi)調(diào)度車行駛時間和裝卸自行車總時間要最少，先求解出租賃點之間的實際車行距離和居民還車的概率，也相繼能夠確定居民還車數(shù)目，根據(jù)每個租賃點的需求數(shù),經(jīng)過建立相應的數(shù)學模型,進而可得調(diào)度車在每一個租賃點的調(diào)度時間。因此能夠根據(jù)已知的道路連通圖，首先經(jīng)過Floyd算法算出任意兩個租賃點間的距離，其次以時間為權重建立最小生成樹模型，找出能使調(diào)度車耗時最少的行駛路線和調(diào)度車的分配方案。2.2問題二分析這個問題能夠在第一個問題的基礎上解答，目標都是使得整個調(diào)度花費時間最短。新增網(wǎng)點和自行車必須滿足經(jīng)費約束，為使設置方案最合理應將網(wǎng)點設在需求量較多的地方，將需求量排序后篩選出備選網(wǎng)點，按照網(wǎng)點需求將所有自行車分配，使得既滿足需求又能讓調(diào)度時間最短。同問題一一樣首先用Matlab編程求出所有網(wǎng)點間距離，利用啟發(fā)式搜索的算法，依次改變備選的新增網(wǎng)點，直到找出花費最短時間的路徑。2.3問題三分析該問經(jīng)過增加調(diào)度車的數(shù)量來減少調(diào)度時間，調(diào)度是在問題二分配的結果上進行，因此采用最小生成樹算法尋找最快調(diào)度方案，能夠?qū)⒕W(wǎng)點進行分區(qū)（相距近的網(wǎng)點為一個分區(qū)）來提高調(diào)度效率降低時間復雜度，假設需要增加p輛調(diào)度車，每輛調(diào)度車只在一個分區(qū)行駛且相互獨立，應用問題二的模型計算各自的調(diào)度時間，改變p值直到最大值不大于150分鐘，即為新增調(diào)度車。三、問題的基本假設1.調(diào)度車始終按照30km/h的平均速度行駛；2.居民的騎行距離不超過2km；3.三個時間段需求量的平均值具有可靠性，能夠滿足需要；4.問題的求解只需考慮時間、費用和數(shù)量因素；5調(diào)度車在網(wǎng)點間的行駛距離能夠按照經(jīng)緯度計算。四、符號規(guī)定裝卸車在第i個租賃點裝卸的自行車數(shù)；：第i個租賃點在調(diào)度后的自行車數(shù)；：第i個租賃點在租完還完后的自行車數(shù)；：租賃點i需要的自行車數(shù)；新增的租賃點點數(shù)；增加的自行車數(shù)；增加的調(diào)度車數(shù)；：租賃點i與租賃點j之間的距離；五、模型的建立與求解根據(jù)以上的分析，可將原問題轉(zhuǎn)化為:自行車分配和調(diào)度車路線的優(yōu)化問題。問題一的模型：在問題一中，我們考慮編號1—30的租賃點，首先，由假設可根據(jù)7:00—8:00之間各個租賃點的自行車需求量，將850輛自行車按照需求比例分給各網(wǎng)點，經(jīng)過對分配結果的分析，并結合題中的約束條件，對分配情況進行調(diào)整，然后重復分配—分析—調(diào)整，從而得到第一個時間段的最優(yōu)的分配方案，即各個租賃點的b，結果如下：網(wǎng)點編號123456789101112131415車輛數(shù)20283939233818393125253991639網(wǎng)點編號161718192021222324252627282930車輛數(shù)232831342820402040252840221825我們用0-1變量來表示租賃點i與租賃點j是否有自行車的調(diào)度,即目標函數(shù)為尋找一條從起始點開始到各個節(jié)點生成的最優(yōu)樹，要求各條線路的權值（權值即為兩個租賃點間所用的時間和裝卸自行車用的時間）和最小，附錄中列出了30個點之間的距離，我們能夠把它看成一個賦有權值的圖G，先要求出圖G的最小生成樹，使樹上各邊的總權和達到最小。然后基于最小生成樹生成一個可行的最短行車路徑。即：s.t模型的求解具體過程如下：步驟1：利用題目中給出的各租賃點的經(jīng)緯度數(shù)據(jù)，Matlab編程得到任意兩個租賃點之間的距離，然后根據(jù)還車的概率與租車點和還車點的距離成反比，即能夠得到各個租賃點還入的自行車數(shù)。步驟2：求解最小生成樹的方法有破圈法、避圈法、Dijkstra算法等。這里我們用避圈法求解，避圈法是指將圖G中的邊按照權數(shù)大小逐條考察，按不構成圈的原則加入到T（樹）中，直到為止，即T的邊數(shù)=G的頂點數(shù)-1為止。避圈法的算法是：1.把G的邊按權的大小整理成，令.2.若含圈，則轉(zhuǎn)3，否則轉(zhuǎn)4.3．令，若則轉(zhuǎn)2；否則停止，G不存在最小生成樹。4.令，。5.若，結束，是最小生成樹；否則轉(zhuǎn)3.根據(jù)避圈法的原理，matlab編程得到的結果如下：T2T1T21367810131517212224301√√3√√√6√7√√√8√√√√10√√13√√15√√√√17√√√21√√√22√√24√√√30√√（圖中打鉤的表示兩個網(wǎng)點之間有自行車的調(diào)度）步驟3：由于0-1整數(shù)規(guī)劃法中決策變量為整數(shù)，我們利用lingo優(yōu)化軟件分析求解此規(guī)劃問題，根據(jù)問題一模型的建立中目標函數(shù)及約束條件編寫lingo程序如下：sets:sk/1..30/:s,x;si/1..30/:a;sik(si,sk):c,l;endsetsmin=@sum(sk:2s*x)+@sum(sik:a);@for(si(i):@sum(sk(i):l(j,i))=1);@for(sik(i,j):l(i,j)<=w(i));@for(sk:@bin(s));@for(sik:@bin(x));data:s,c,x=@ole('C:\success.xls','s','_c','x');@ole('C:\success.xls','s','_c','x')=s,c,x;enddataend將matlab編程得到的結果結合實際情況，采用最小生成樹的算法，調(diào)度方案車一：364173214車二：1112131212625平均調(diào)度一次花費時間為:車一時間:137分鐘車二時間：134分鐘問題二的模型目標：新增租賃點能夠覆蓋更大的面積滿足需求量大的網(wǎng)點且整個調(diào)度過程花費時間最短，即minT，maxb約束：新增的租賃點和自行車所花費用小于投入建設經(jīng)費200萬元。因此得到如下模型：s.t模型的求解該模型的直接求解在短時間是非常困難的，因此我們在問題一的基礎上加以改進，采用啟發(fā)式搜索算法。此算法的步驟如下。步驟一：將備選的網(wǎng)點的自行車需求數(shù)量按照從高到低的進行有序排列，形成70×3的矩陣，每行表示該網(wǎng)點在各時間段需要的自行車。步驟二：按照需求量的大小進行選擇新增的網(wǎng)點，新增自行車即為所選網(wǎng)點的自行車總和，代入投入經(jīng)費的約束條件，選取符合條件的假設新增網(wǎng)點，用問題一所的模型分配自行車。步驟三：應用問題一的模型，根據(jù)經(jīng)緯度把新增的網(wǎng)點與原網(wǎng)點間距離用folyd算法和Matlab編程計算出來。步驟四：用最小生成樹法尋找調(diào)度花費時間最短的路徑，改變假設的新增網(wǎng)點，重復上述步驟，直到找出花費時間最短的最優(yōu)的路徑。備選租賃網(wǎng)點自行車需求量排序：網(wǎng)點編號7:00~8:30車輛需求數(shù)11:00~12:30車輛需求數(shù)17:30~19:00車輛需求數(shù)564040403140278693921235038373277333628603332374933183591322220413212127132121094268988253335812523146324283343241716722339344723363290233237842129336821121473203736761927298018362245182623671888341722264817128641786441614143615372259152324571518145115131461157135214910根據(jù)附件2中的數(shù)據(jù)可知，經(jīng)開區(qū)每個酒店附近日均人流量1500人，公共場所日均人流量一萬人，十字路口3000人，地鐵出口2萬人，社區(qū)人，在結合題目附錄所給的各個租賃點需求量，結合前期建設的30個租賃點，保證每15人一輛自行車，在考慮到調(diào)度最優(yōu)，結合問題一最小生成樹算法所得到的最優(yōu)路徑，運用MATLAB進一步分析可得到每個租賃點具體分配車方案：租賃點自行車數(shù)量56403140693950387733603349339132413271329426882581256324432472234723902384216821732076198018451867183417因此，綜上所述，共新建自行車租賃點26個，新增自行車697輛，共需花費199.7萬元。每輛車平均一次調(diào)度花費的時間為：208分鐘。問題三的模型：目標：在新增網(wǎng)點后使整個調(diào)度在150分鐘完成；約束：每輛調(diào)度車每次運送的自行車不大于50輛；因此得到模型：s.t模型求解步驟一：根據(jù)問題二的結果確定了新增網(wǎng)點的位置，首先用excel進行數(shù)據(jù)的分析處理，并按照網(wǎng)點間距離大小進行了分類，在處理數(shù)據(jù)的過程中，我們使用了一些技巧：用名稱替換的方法把網(wǎng)點名用序號代替。步驟二：采用最小生成樹算法尋找最快調(diào)度方案，能夠?qū)⒕W(wǎng)點進行分區(qū)（相距近的網(wǎng)點為一個分區(qū)）來提高調(diào)度效率降低時間復雜度，假設需要增加p輛調(diào)度車，每輛調(diào)度車只在一個分區(qū)行駛且各分區(qū)相互獨立，應用問題一的模型計算各分區(qū)的調(diào)度時間。步驟三：改變p值重復上述步驟，直到所有分區(qū)的調(diào)度時間最大值不大于150分鐘。網(wǎng)點分區(qū)圖為：用Matlab編程得到的調(diào)度方案為：調(diào)度車編號1234起點1454836終點20317452調(diào)度時間136142138129調(diào)度方案為即行車路線為：六、模型的分析和檢驗：6.1.模型的檢驗這三個問題的模型檢驗均要經(jīng)過實際的分配調(diào)度實現(xiàn)，我們在三個問題中分別應用了不同的算法和軟件進行了模型的檢驗，在問題一中應用floyd算法和matlab程序?qū)υ搯栴}進行了求解和檢驗，在問題二中運用了啟發(fā)式搜索算法原理對問題進行了檢驗，在問題三中利用最小生成樹算法進行求解和檢驗以實現(xiàn)上述三個問題的最優(yōu)性。我們利用模型一得到的自行車分配方案，將各網(wǎng)點的需求量與實際分配量相比較，各網(wǎng)點都能夠滿足需求，代入約束條件后，符合要求，而且得到的配送路線花費的時間能夠使租賃系統(tǒng)正常運行，因此認為模型一比較可靠。模型一自行車的分配需求情況由圖能夠看出分配值均大于需求值的10%，所有的租賃點都能滿足需求，因此，模型是合理的。模型二的新增網(wǎng)點的需求量情況：從圖中能夠看出三條曲線波動幅度較小，即發(fā)生調(diào)度的概率較小，而且網(wǎng)點都設置在需求量較大的地方，因此模型二較合理。6.2.模型的優(yōu)點優(yōu)點：最小生成樹算法應用比較成熟，模型中將行車時間和裝卸時間視為權值，編程經(jīng)過計算機計算實現(xiàn)，因此能夠快速的得出精確的結果。問題1：算法穩(wěn)定成熟，程序容易實現(xiàn)，結果精確。問題2：具有反饋過程，能夠不斷的優(yōu)化調(diào)度方案。問題3：租賃點分區(qū)的方法減小了時間的復雜度，是求解過程簡單。6.3.模型的缺點模型求解過程中，獲得的各個網(wǎng)點間的距離是根據(jù)經(jīng)緯度計算得到的弧長距離，而實際調(diào)度車的路線與街道分布情況一致，這樣就會導致求得的調(diào)度時間與實際有偏差，因此可根據(jù)街道的分布情況計算距離。假設調(diào)度始終發(fā)生在租車還車之后進行，而實際生活中，兩者一般都是同時發(fā)生的，因此應該使調(diào)度依據(jù)實際需要進行來完善模型。七、模型的推廣在整個解題過程中，我們都是在理論結合實際的前提下作出各種假設和量化，網(wǎng)點間距離僅根據(jù)經(jīng)緯度計算與實際情況不符，只有確定了街道的實際距離才能精確地計算出調(diào)度時間。模型一借助最小生成樹法建立，它同樣能夠推廣到其它的運輸優(yōu)化方案和資源配置優(yōu)化的問題中，可是分配調(diào)度模型也有其缺點，編程所得的路徑為理想的情況與實際有一定的偏差。八、參考文獻【1】肖華勇.實用數(shù)學建模與軟件應用西安：西北工業(yè)大學出版社.11【2】曹旭東數(shù)學建模原理與方法北京：高等教育出版社，.1【3】李學文，李炳照，王宏洲數(shù)學建模優(yōu)秀論文精選與點評.北京：清華大學出版社.9【4】陳光亭，裘哲勇數(shù)學建模北京市高等教育出版社.2九、附錄：問題一中求解任意兩個網(wǎng)點間距離的結果如下：12345678910111213141510.00.40.91.31.11.72.92.53.24.51.30.70.50.60.220.40.00.61.21.31.73.02.73.34.51.71.00.60.60.630.90.60.00.81.31.42.92.43.04.12.21.61.21.21.141.31.20.80.00.90.62.11.72.23.32.52.01.71.81.451.11.31.30.90.00.91.81.42.23.51.91.71.61.71.161.71.71.40.60.90.01.51.11.62.82.82.42.22.31.872.93.02.92.11.81.50.00.40.72.03.53.43.43.52.982.52.72.41.71.41.10.40.00.82.13.23.13.03.12.593.23.33.02.22.21.60.70.80.01.34.03.93.73.83.2104.54.54.13.33.52.82.02.11.30.05.35.14.95.04.5111.31.72.22.51.92.83.53.24.05.30.00.81.21.31.2120.71.01.62.01.72.43.43.13.95.10.80.00.40.50.7130.50.61.21.71.62.23.43.03.74.91.20.40.00.20.5140.60.61.21.81.72.33.53.13.85.01.30.50.20.00.6150.20.61.11.41.11.82.92.53.24.51.20.70.50.60.0160.30.71.11.30.91.62.72.43.14.41.20.80.70.80.2170.90.70.20.61.21.22.72.32.93.92.31.61.31.31.1181.11.41.71.50.61.52.11.82.64.01.41.41.41.61.0190.91.11.20.90.21.02.01.62.33.61.81.51.41.50.9201.31.51.51.00.20.91.61.32.13.42.01.81.71.91.2211.71.91.81.20.60.91.20.91.73.02.32.22.12.31.6222.01.91.40.71.30.41.71.31.72.63.12.72.42.52.0232.12.21.81.11.20.41.20.71.22.33.12.82.62.72.2243.02.92.51.82.31.41.91.61.41.84.23.83.53.53.1252.72.92.92.41.61.91.01.11.72.92.93.13.13.22.6262.62.82.82.11.51.60.70.81.42.72.93.03.03.22.5272.62.82.72.01.51.50.50.51.22.53.13.13.03.22.5284.24.34.03.23.12.61.41.71.00.94.94.84.74.84.2290.60.81.01.00.51.22.31.92.73.91.61.21.11.20.6303.23.33.12.32.11.70.40.70.41.63.83.83.73.83.216171819202122232425262728293010.30.91.10.91.31.72.02.13.02.72.62.64.20.63.220.70.71.41.11.51.91.92.22.92.92.82.84.30.83.331.10.21.71.21.51.81.41.82.52.92.82.74.01.03.141.30.61.50.91.01.20.71.11.82.42.12.03.21.02.350.91.20.60.20.20.61.31.22.31.61.51.53.10.52.161.61.21.51.00.90.90.40.41.41.91.61.52.61.21.772.72.72.12.01.61.21.71.21.91.00.70.51.42.30.482.42.31.81.61.30.91.30.71.61.10.80.51.71.90.793.12.92.62.32.11.71.71.21.41.71.41.21.02.70.4104.43.94.03.63.43.02.62.31.82.92.72.50.93.91.6111.22.31.41.82.02.33.13.14.22.92.93.14.91.63.8120.81.61.41.51.82.22.72.83.83.13.03.14.81.23.8130.71.31.41.41.72.12.42.63.53.13.03.04.71.13.7140.81.31.61.51.92.32.52.73.53.23.23.24.81.23.8150.21.11.00.91.21.62.02.23.12.62.52.54.20.63.2160.01.10.80.71.11.51.92.03.02.42.32.44.10.43.0171.10.01.61.11.41.71.31.72.32.82.62.53.81.02.9180.81.60.00.60.60.91.91.82.91.61.61.73.50.72.4190.71.10.60.00.30.71.41.32.41.81.71.63.30.32.3201.11.40.60.30.00.41.31.12.31.51.31.33.00.71.9211.51.70.90.70.40.01.30.92.11.11.00.92.61.11.5221.91.31.91.41.31.30.00.61.12.22.01.82.61.51.8232.01.71.81.31.10.90.60.01.21.71.41.22.21.61.3243.02.32.92.42.32.11.11.20.02.72.42.12.12.61.7252.42.81.61.81.51.12.21.72.70.00.30.62.32.11.3262.32.61.61.71.31.02.01.42.40.30.00.32.12.01.0272.42.51.71.61.30.91.81.22.10.60.30.01.92.00.8284.13.83.53.33.02.62.62.22.12.32.11.90.03.61.1290.41.00.70.30.71.11.51.62.62.12.02.03.60.02.6303.02.92.42.31.91.51.81.31.71.31.00.81.12.60.0求網(wǎng)點距離的Matlab程序代碼：dx=ones(30,30);fork=1:1:30form=1:1:30d=distance(w(k),j(k),w(m),j(m));pi=3.1415926;dx(k,m)=d*6371*1000*2*pi/360;endenddx最小生成樹算法：1、最小生成樹的定義：在一個具有幾個頂點的連通圖G中，如果存在子圖G'包含G中所有頂點和一部分邊，且不形成回路，則稱G'為圖G的生成樹，代價最小生成樹則稱為最小生成樹。2、本文用Prim算法實現(xiàn)了生成最小生成樹，如下為Prim算法：假設G(V，E)是有n個頂點的連通網(wǎng)絡，用T=（U，TE）表示要構造的最小生成樹，其中U為頂點集合，TE為邊的集合。Prim算法的具體步驟描述如下：(1)初始化：令U={?}，TE={?}。從V中取出一個頂點u0放入生成樹的頂點集U中，作為第一個頂點，此時T=（{u0}，{?}）；(2)從uU，vV-E的邊（u，v）中找一條代價最小的邊（u*，v*），將其放入TE中，并將v*放入U中。(3)重復步驟(2)，直至U=V為止。此時集合TE中必有n-1條邊，T即為所要構造的最小生成樹。上述過程的具體細節(jié)如算法見代碼所示。3、經(jīng)過試驗測試能夠求出此圖的最小生成樹為：。4、程序運行結果執(zhí)行結果：5、結論（1）、該程序成功解決了“最小生成樹問題”。（2）、根據(jù)算法分析出Prim算法的復雜度與網(wǎng)的邊數(shù)無關，適合邊稠密網(wǎng)絡的最小生成樹，但時間復雜度大，程序運行較慢。（3）、Kruskal算法僅與網(wǎng)中邊數(shù)有關，適合于邊稀疏網(wǎng)絡的最小生成樹，在時間復雜度方面小于Prim算法，提高程序運行速度。6、程序代碼（1）、Prim算法：typedefstruct//邊的存儲結構{ intfromvex,endvex;//邊的起點和終點 intlength;//邊的權值}edge;edgeT[n-1];//最小生成樹floatdist[n][n];//連通網(wǎng)絡的帶權鄰接矩陣voidPrim(inti)//i表示最小生成樹所選取的第一個頂點下標{ intj,k,m,v,min,max=100000;floatd; edgee; v=i;//將選定頂點送入中間變量v for(j=0;j<=n-2;j++)//構造第一個頂點 { T[j].fromvex=v; if(j>=v) { T[j].endvex=j+1; T[j].length=dist[v][j+1]; } else { T[j].endvex=j; T[j].length=dist[v][j]; } for(k=0;k<=n-1;k++)//求第k條邊 { min=max; for(j=k;j<=n-1;j++)//找出最短的邊并將最短邊的下標記錄在m中 if(T[j].length<min) { min=T[j].length; m=j; } e=T[m];//將最短的邊交換到T[k]單元 T[m]=T[k]; T[k]=e; v=T[k].endvex;//v中存放新找到的最短邊在V-U中的頂點 for(j=k+1;j<n-1;j++)//修改所存儲的最小邊集 { d=dist[v][T[j].endvex]; if(d<T[j].length) { T[j].length=d; T[j].fromvex=v; } } } }}//Prim算法2、程序清單：#include<stdio.h>#defineMAX_VERTEX_NUM10#defineINFINITY1000typedefstructEdge{intweight;}Edge,EdgeMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstructMGraph{EdgeMatrixedges;intvexnum;intedgenum;}MGraph;typedefstruct{intvertex;intlowcost;}Closedge;voidInitializeMG(MGraph&G){G.edgenum=G.vexnum=0;for(inti=0;i<MAX_VERTEX_NUM;++i)for(intj=0;j<MAX_VERTEX_NUM;++j)G.edges[i][j].weight=INFINITY;}voidCreateGraph(MGraph&G){inti,j;G.vexnum=6;G.edgenum=10;G.edges[0][1].weight=G.edges[1][0].weight=1;G.edges[0][2].weight=G.edges[2][0].weight=6;G.edges[0][3].weight=G.edges[3][0].weight=9; G.edges[0][5].weight=G.edges[5][0].weight=11;G.edges[1][2].weight=G.edges[2][1].weight=3;G.edges[1][5].weight=G.edges[5][1].weight=2;G.edges[2][3].weight=G.edges[3][2].weight=4;G.edges[2][4].weight=G.edges[4][2].weight=10;G.edges[3][4].weight=G.edges[5][3].weight=5;G.ed