如何連接通信站使費用最少

數(shù)學實驗第12章如何連接通信站使費用最少

---最小生成樹2022/12/13

數(shù)學家之擅長證明緣于對證明過程的大量研讀和反復實踐。同樣，可以通過涉獵引人入勝、特色各異的算法，嘗試設計各種問題的解決方法，培養(yǎng)算法設計的成熟性和機敏性。

---作者2022/12/13實驗目的掌握最小生成樹的Prim算法和Kruskal算法，了解貪婪算法的基本思想，發(fā)揮聯(lián)想力，把知識融會貫通，舉一反三。初步領會用Matlab語言編寫非數(shù)值計算問題的編程技術；通過實例學習怎樣建立最小生成樹模型；通過自己提出問題，動手做實驗，并在文獻檢索、調(diào)查研究、動手和動腦等方面得到鍛煉，提高創(chuàng)造力和解決實際問題的能力。2022/12/13主要內(nèi)容樹圖—直觀現(xiàn)象的表示工具引例：計算機網(wǎng)絡的線路設計生成樹算法及其MATLAB程序實現(xiàn)范例：制造系統(tǒng)設計的分組技術布置實驗2022/12/1312.1樹圖—直觀形象的表示工具2022/12/1312.1樹圖—直觀形象的表示工具一個連通圖連通圖：其中任意兩點之間都有路徑，當一條路徑的起點和終點是同一頂點時，稱這條路徑為圈2022/12/1312.1樹圖—直觀形象的表示工具

樹：沒有圈的連通圖

--樹中任意兩點間有唯一路徑。

--樹的邊數(shù)恰好為頂點數(shù)減1。--在樹中任意去掉一條邊，將會不連通。

--樹中任意兩個不相鄰頂點間添一邊后，就恰好含一個圈。2022/12/1312.1樹圖—直觀形象的表示工具2022/12/1312.2引例—計算機網(wǎng)絡的線路設計

城市電信局有許多業(yè)務如收費，營業(yè)，112，114等，希望在全市范圍實現(xiàn)計算機聯(lián)網(wǎng)服務，共享各種資源。一個主要關心的問題是用數(shù)據(jù)通訊線把一組站點聯(lián)結起來，而不允許通訊線在非站點處相交，如何連接可使通訊線的花費最??？2022/12/1312.2引例—計算機網(wǎng)絡的線路設計假設各站點間可以鋪設通訊線路進行連接的情況如圖所示，頂點為站點，邊為連接兩站點之間的通訊線，邊的權為其費用。2022/12/1312.2引例—計算機網(wǎng)絡絡的線路設設計思考：1）左圖中哪哪些是多余余的？2）最經(jīng)濟的的網(wǎng)絡應具具備什么特特性？3）如何求出出最經(jīng)濟的的連接路線線圖？2022/12/812.2引例—計算機網(wǎng)絡絡的線路設設計最經(jīng)濟的網(wǎng)網(wǎng)絡不應該該有任何封封閉的回路路。橡筋圈上剪剪一刀后，，仍然是一一個整段。。聯(lián)想2022/12/812.2引例—計算機網(wǎng)絡絡的線路設設計生成數(shù)或支支撐樹（spanningtree）：若G的子圖T是樹，且其其頂點集等等于G的頂點集。。2022/12/812.2引例—計算機網(wǎng)絡絡的線路設設計確定應在哪哪些站點之之間鋪設通通訊線路，，是否可看看作是在相相應的加權權圖中構造造最小費用用的生成樹樹的問題？？生成樹的權權：其上所有有邊權之和和。2022/12/812.2引例—計算機網(wǎng)網(wǎng)絡的線線路設計計2022/12/812.2引例—計算機網(wǎng)網(wǎng)絡的線線路設計計2022/12/812.3生成樹算算法及其其MATLAB程序實現(xiàn)現(xiàn)Kruskal算法算法的MATLAB程序實現(xiàn)現(xiàn)背景聚焦焦Prim算法2022/12/8Kruskal算法2022/12/8Kruskal算法思考：計算機如如何實現(xiàn)現(xiàn)上述非非數(shù)值計計算算法法？計算機如如何判斷斷一些邊邊是否形形成圈？？2022/12/8Kruskal算法2022/12/8Kruskal算法給每個子子樹一個個不同的的編號2022/12/82022/12/8Kruskal算法2022/12/82022/12/8Kruskal算法2022/12/8最小生成樹算算法的背景聚聚焦1956年，美國電話話電報公司（（AT&T）利用最小生生成樹計算出出對幾家商業(yè)業(yè)客戶的索價價。一張大比例的的美國地圖鋪鋪在地板上，，尋找聯(lián)結所所有站點的總總長度最小的的網(wǎng)絡。用手工（并且且跪著）操作作的方式完成成的問題很有有限。2022/12/8最小生成樹算算法的背景聚聚焦2022/12/8最小生成樹算算法的背景聚聚焦2022/12/8Prim算法算法的手工操操作：任選一個頂點點v1，將其涂紅；；在一個端點為為紅色，另一一個端點為黃黃色的邊中，，找一條權最最小的邊涂紅紅，把該邊的的黃端點也涂涂成紅色；重復②直到所有頂點點都成紅色為為止，最終的的紅色邊和頂頂點便是最小小生成樹。2022/12/8Prim算法法2022/12/8提示示2022/12/8注意意2022/12/812.4范例例：：制制造造系系統(tǒng)統(tǒng)的的分分組組技技術術2022/12/812.4范例例：：制制造造系系統(tǒng)統(tǒng)的的分分組組技技術術2022/12/812.4范例：：制造造系統(tǒng)統(tǒng)的分分組技技術2022/12/812.4范例：：制造造系統(tǒng)統(tǒng)的分分組技技術思考：1）ω(i,j)=0和ω(i,j)=1分別表表示什什么？？2）ω表達了了什么么？2022/12/8建模2022/12/82022/12/82022/12/82022/12/8布置實驗2022/12/8布置實驗2022/12/82022/12/8實驗內(nèi)容2022/12/8實驗內(nèi)容2022/12/82022/12/82022/1