通信網(wǎng)規(guī)劃理論-wenkub
2022-10-28 16:28:17 本頁(yè)面
【正文】 連通圖 G 的 生成樹(shù) (spanning tree)，若 T 是 G的子圖且包含圖 G 的所有的節(jié)點(diǎn) A CDBA CDBA CDBADCB? 如何找到一棵生成樹(shù) – 深探法 (depth first search)：任選一點(diǎn)標(biāo)記為 0 點(diǎn)開(kāi)始搜索，選一條未標(biāo)記的邊走到下一點(diǎn)，該點(diǎn)標(biāo)記為 1，將走過(guò)的邊標(biāo)記；假設(shè)已標(biāo)記到 i 點(diǎn)，總是從最新標(biāo)記的點(diǎn)向下搜索，若從 i 點(diǎn)無(wú)法向下標(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)：是一種有層級(jí)結(jié)構(gòu)的搜索，一般得到的是樹(shù)形圖 33 最小生成樹(shù)（最小部分樹(shù)） 例 通信網(wǎng)規(guī)劃中通信線路的連接問(wèn)題 某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建信息高速公路把這些城市連接起來(lái)， 使得從其中任何一個(gè)城市都可以經(jīng)信息高速公路直接或間接到達(dá)另一個(gè)城市 . 假定已經(jīng)知道了任意兩個(gè)城市之間修建信息高速公路的成本，那么應(yīng)如何決定在哪些城市間修建信息高速公路，使得總成本最??？ ? 顯然，這要求在已知邊長(zhǎng)度的網(wǎng)路圖中找最小生成樹(shù) 最小生成樹(shù)的算法 ： 34 ? Kruskal 算法： 將圖中所有邊按權(quán)值從小到大排列 選所剩最小的邊加入邊集 T 是否和前面加入 的邊構(gòu)成回路 T 中是否有 n?1 條邊 將邊加入圖中 N N T 是最小生成樹(shù) Y 舍去該邊 Y 定理 指定圖中任一點(diǎn) vi，如果 vj 是距 vi 最近的相鄰節(jié)點(diǎn)，則關(guān)聯(lián)邊 eij 必在某個(gè)最小生成樹(shù)中。 網(wǎng)絡(luò)規(guī)劃就是研究如何有效地計(jì)劃、管理和控制網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會(huì)和經(jīng)濟(jì)效益 9 網(wǎng) 絡(luò) 規(guī) 劃 簡(jiǎn) 介 ? 網(wǎng)絡(luò)規(guī)劃與圖 ? 網(wǎng)絡(luò)規(guī)劃問(wèn)題的例子 ? 圖與網(wǎng)路分析 10 網(wǎng) 絡(luò) 規(guī) 劃 簡(jiǎn) 介 ——網(wǎng)絡(luò)規(guī)劃與圖 ? 網(wǎng)絡(luò)：數(shù)學(xué)模型、數(shù)學(xué)結(jié)構(gòu) 圖 從若干可能的安排或方案中尋求某
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1