通信網(wǎng)規(guī)劃理論-資料下載頁
2024-10-17 16:28本頁面
【導(dǎo)讀】第一節(jié)圖論基礎(chǔ)知識。第六節(jié)電信網(wǎng)規(guī)劃中的財務(wù)經(jīng)濟(jì)評價指標(biāo)及經(jīng)濟(jì)分析。第八節(jié)智能算法及其應(yīng)用。通過本章介紹的一些定量分析方法，掌握電信網(wǎng)規(guī)劃。為進(jìn)一步的進(jìn)行實(shí)際的規(guī)劃工作奠定基。本章的內(nèi)容涉及：。電信網(wǎng)中局、站間最短路的算法。能源和物質(zhì)分派網(wǎng)絡(luò)、人際關(guān)系網(wǎng)絡(luò)等等。梁雄健、李魯湘，《電信網(wǎng)規(guī)劃》，人民郵電出版。馬永源、馬力，《電信規(guī)劃方法》，北京郵電大學(xué)。謝金星、邢文訓(xùn)，《網(wǎng)絡(luò)優(yōu)化》，清華大學(xué)出版。網(wǎng)絡(luò)流量的重新分布！意兩個城市之間修建信息高速公路的成本，所以國際上稱之為中國郵遞員問題.這一問題的研究歷史十分。悠久，通常稱之為旅行商問題.,lm}組成，圖表述網(wǎng)的。有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記。次數(shù)為0的點(diǎn)稱為孤立點(diǎn)，次數(shù)
【正文】 樹中必不存在回路 ?任何樹必存在次數(shù)為 1 的點(diǎn) ?具有 n 個節(jié)點(diǎn)的樹 T 的邊恰好為 n?1 條，反之，任何有 n 個節(jié)點(diǎn)， n?1 條邊的連通圖必是一棵樹 32 圖的生成樹 ? 樹 T 是連通圖 G 的 生成樹 (spanning tree)，若 T 是 G的子圖且包含圖 G 的所有的節(jié)點(diǎn) A CDBA CDBA CDBADCB? 如何找到一棵生成樹 – 深探法 (depth first search)：任選一點(diǎn)標(biāo)記為 0 點(diǎn)開始搜索，選一條未標(biāo)記的邊走到下一點(diǎn)，該點(diǎn)標(biāo)記為 1，將走過的邊標(biāo)記；假設(shè)已標(biāo)記到 i 點(diǎn)，總是從最新標(biāo)記的點(diǎn)向下搜索，若從 i 點(diǎn)無法向下標(biāo)記，即與 i 點(diǎn)相關(guān)聯(lián)的邊都已標(biāo)記或相鄰節(jié)點(diǎn)都已標(biāo)記，則退回到 i ?1 點(diǎn)繼續(xù)搜索，直到所有點(diǎn)都被標(biāo)記 – 廣探法 (breadth first search)：是一種有層級結(jié)構(gòu)的搜索，一般得到的是樹形圖 33 最小生成樹（最小部分樹） 例 通信網(wǎng)規(guī)劃中通信線路的連接問題 某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建信息高速公路把這些城市連接起來， 使得從其中任何一個城市都可以經(jīng)信息高速公路直接或間接到達(dá)另一個城市 . 假定已經(jīng)知道了任意兩個城市之間修建信息高速公路的成本，那么應(yīng)如何決定在哪些城市間修建信息高速公路，使得總成本最小？ ? 顯然，這要求在已知邊長度的網(wǎng)路圖中找最小生成樹 最小生成樹的算法 ： 34 ? Kruskal 算法： 將圖中所有邊按權(quán)值從小到大排列 選所剩最小的邊加入邊集 T 是否和前面加入 的邊構(gòu)成回路 T 中是否有 n?1 條邊 將邊加入圖中 N N T 是最小生成樹 Y 舍去該邊 Y 定理 指定圖中任一點(diǎn) vi，如果 vj 是距 vi 最近的相鄰節(jié)點(diǎn)，則關(guān)聯(lián)邊 eij 必在某個最小生成樹中。 推論 將網(wǎng)路中的節(jié)點(diǎn)劃分為兩個不相交的集合 V1和V2， V2=V?V1，則 V1和 V2間權(quán)值最小的邊必定在某個最小生成樹中。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1