【正文】 （ 1） 網(wǎng)絡(luò)描述 ，即網(wǎng)絡(luò)的物理數(shù)據(jù)模型，包括網(wǎng)絡(luò)部件的相對(duì)內(nèi)存與高效存取相關(guān)信息的指針信息； （ 2） 標(biāo)記方法 ，它決定了待掃描點(diǎn)的集合； （ 3） 選擇規(guī)則與結(jié)點(diǎn)集數(shù)據(jù)結(jié)構(gòu) ，選擇規(guī)則決定了下一個(gè)待掃描的結(jié)點(diǎn)。 所有點(diǎn)對(duì)間的最短路徑 點(diǎn)對(duì)間的最短路徑： 每一對(duì)頂點(diǎn)之間的最短路徑。 （ 4）根據(jù)回溯的方法輸出起始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最優(yōu)路徑，以及最短距離 gv。 （ 1）設(shè)置初值； （ 2）從 T中選出具有最小 f*值的結(jié)點(diǎn) v，即令v=min{fu*}。（ 相容性條件 ） 167。 估計(jì)函數(shù)： f*(j)=g(j)+h*(j) 優(yōu)點(diǎn)： 可以首先搜索可能性較大的結(jié)點(diǎn)，提高搜索效率。 A*算法 啟發(fā)式搜索： 在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估 ，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。 Floyd算法 Floyd算法的基本步驟 ： （ 1）設(shè)置初值，令 Aij＝ w(vi,vj)，若 w(vi,vj)＜ ∞ ， 且 i≠j ，則令 Pij＝ [i]+[j]； （ 2）對(duì) k＝ 1,2,… ,n, j ＝ 1,2,… ,n, 判斷是否有 Aik+Akj＜ Aij，若是，置 Aij ＝ Aik+Akj ， Pij ＝ Pik+Pkj ； （ 3）迭代 n次之后，算法結(jié)束， Aij 為從 vi到 vj 的最短路徑的長(zhǎng)度， Pij 為相應(yīng)的最短路徑 。依次類推，以經(jīng)過 n次比較之后，最后求得的必是從 vi到 vj的最短路徑。若存在，則比較（ vi,vj）和（ vi,v1,vj）的路徑長(zhǎng)度，較短者為從 vi到 vj的中間頂點(diǎn)的序號(hào)不大于 1的最短路徑； 2）假如在路徑上再增加一個(gè)頂點(diǎn) v2，若路徑（ vi,… ,v2）和（ v2,… ,vj）分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于 1的最短路徑，那么后來的路徑（ vi,… ,v2,… ,vj）有可能是從 vi到 vj的中間頂點(diǎn)不大于 2的最短路徑。 Floyd算法 Floyd算法是一個(gè) 求圖中所有結(jié)點(diǎn)間 最短路徑的算法 ，可解決權(quán)值為負(fù)的情況。 反向追蹤，可得 v0到 vi的最短路徑。 （ 6） k=5, 由于 d（ 1） =∞ ，即最后一個(gè)未標(biāo)記的點(diǎn)為 ∞ 。 Dijkstra算法 （ 4） k=4， 顯然 d（ 3） = 50最小，標(biāo)記 （ v4,v3） ，即 （ v4,v3）是從 v4到 v3的最短路徑。 （ 3） k=2, 顯然 d（ 4） = 30最小，標(biāo)記 （ v0,v4） ，即 （ v0,v4） 是從 v0到 v4的最短路徑。 Dijkstra算法 例： 用 Dijkstra算法求解如圖所示的最短路徑。如果所有點(diǎn)已標(biāo)記，則算法完全退出，否則，記 k=i，轉(zhuǎn)到（ 2）再繼續(xù)，直到所有點(diǎn)都已標(biāo)記。從已標(biāo)記的點(diǎn)中找到連接到點(diǎn) i的前一點(diǎn) j*,并令 i=j*作為前一點(diǎn)。從上述結(jié)點(diǎn)集中，選取 dj最小所對(duì)應(yīng)的點(diǎn)為最短路徑中的下一連接點(diǎn) i，并作標(biāo)記。將起源點(diǎn) s標(biāo)號(hào)，記 k=s，其他點(diǎn)尚未處理； （ 2）距離計(jì)算。 Dijkstra算法的具體步驟 ： （ 1）初始化：設(shè)置源 s點(diǎn)： ds=0,ps=空集 。 Dijkstra算法的基本思想 ： 標(biāo)記源點(diǎn)到已得到點(diǎn)的最短路徑，再尋找到下一個(gè)點(diǎn)的最短路徑（由近及遠(yuǎn)尋找起點(diǎn)到其他節(jié)點(diǎn)的最佳路徑，直至到達(dá)目標(biāo)節(jié)點(diǎn)）。 167。按研究的目標(biāo)可有不同的分類。 ? ?? ? ? ??????????????????????????????????niniixxxxaEvvjiEvvijijEvvijijijjiji,112,01,10m i n,167。 ? ? ? ?? ????PEeewPW167。 路徑分析分類 ： 兩類，一類是確定軌跡的網(wǎng)絡(luò)路徑問題；另一類是無確定軌跡的路徑分析。 設(shè) P為 G中兩點(diǎn)間的一條有向路徑，定義 P的權(quán)值 則 G中兩點(diǎn)間權(quán)最小的有向路徑稱為這 兩點(diǎn)的最佳路徑 。 最短路徑分析 路徑分析 ： 是在指定網(wǎng)絡(luò)的結(jié)點(diǎn)間找出最佳路徑。 物理數(shù)據(jù)模型： 是通過一定的數(shù)據(jù)結(jié)構(gòu)，完成空間數(shù)據(jù)的物理組織、空間存取及索引方法的設(shè)計(jì)。包括 幾何數(shù)據(jù)模型 和 語義數(shù)據(jù)模型 。主要有概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。 167。其屬性主要是拐角的阻礙強(qiáng)度。 障礙 ：對(duì)資源傳輸起阻斷作用的結(jié)點(diǎn)或鏈，它阻礙了資源在與其相連的鏈間的流動(dòng)，代表了網(wǎng)絡(luò)中元素的不可通行狀態(tài)。 中心 ：網(wǎng)絡(luò)中具有一定的容量，能夠從鏈上獲取資源的結(jié)點(diǎn)所在地。 站點(diǎn) ：網(wǎng)絡(luò)中裝載或卸下資源的結(jié)點(diǎn)位置。屬性信息包括阻礙強(qiáng)度、資源需求量、資源流動(dòng)的約束條件。 鏈 ：圖或網(wǎng)絡(luò)中的線狀要素，表現(xiàn)的是網(wǎng)絡(luò)中的地理實(shí)體和現(xiàn)象，通常用中心線代表地理實(shí)體和現(xiàn)象本身。資源通過在網(wǎng)絡(luò)中的流動(dòng)實(shí)現(xiàn)傳輸和分配。 167。 167。 一、網(wǎng)絡(luò)中的基本元素及屬性： 網(wǎng)絡(luò)屬性 包括資源需求量及阻礙強(qiáng)度。 網(wǎng)絡(luò)分析的主要研究?jī)?nèi)容 ：最短路徑分析、資源分配、連通分析、流分析等?？杀硎緸橛删W(wǎng)絡(luò)結(jié)點(diǎn)集 V、網(wǎng)絡(luò)邊集 E和事件點(diǎn)集 P組成的集合，即有 D = {V， E， P} 網(wǎng)絡(luò)分析 ：是對(duì)地理網(wǎng)絡(luò)和城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)等網(wǎng)狀事物以及它們的相互關(guān)系和內(nèi)在聯(lián)系進(jìn)行地理分析和模型化。 167。 【 問題的解決 】 大數(shù)學(xué)家 歐拉 注意到，每個(gè)點(diǎn)如果有進(jìn)去的邊就必須有出來的邊，從而每個(gè)點(diǎn)連接的邊數(shù)必須有偶數(shù)個(gè)才能完成一筆畫。 從 Ae中去掉一行，且秩為 p1的矩陣，稱為 D的 關(guān)聯(lián)矩陣 ，記作 A。 關(guān)聯(lián)矩陣 設(shè) D是有 p個(gè)頂點(diǎn)， q條弧的有向圖，并假定圖是連通的而且沒有環(huán)。 圖論基礎(chǔ)（ 14） 定理 ：設(shè) D是連通有向圖，對(duì)任意 v∈V （ D），如果 那么 D恰有一條有向回路。 定理 ：設(shè) C是連通有向圖 D的一個(gè)子圖， v是 C中任意頂點(diǎn)，如果 （ 1） （ 2） 那么 C是一條有向回路。 入度 :有向圖 D中從頂點(diǎn) v為終點(diǎn)的弧的數(shù)目叫做 v的入度，記作 。 167。 如果在有向圖 D中，存在一條（ u,v）的有向路，那么頂點(diǎn) v叫做在 D中從頂點(diǎn) u出發(fā)是可到達(dá)的 ，或者說 由 u可到達(dá) v。 有向閉鏈 :起點(diǎn)與終點(diǎn)重合的有向鏈。v0稱為 w的 起點(diǎn) ， vk稱為 w的 終點(diǎn) ， k稱為 w的 長(zhǎng) 。 167。 基礎(chǔ)圖 ：若對(duì)有向圖 D，可以在頂點(diǎn)集合 V上作一個(gè)圖 G，使得對(duì)應(yīng)于 D的每一條弧， G有一條相同端點(diǎn)的邊，這樣得到的無向圖 G稱為有向圖 D的基礎(chǔ)圖。 有向圖 ：帶有方向的邊的圖。 ? ? ? ?? ?0,},{ ??? lll ewEeewW其中，? ? ? ? min?? ?? Tt Ee tewTW?kjjET1??167。 定理 ：令 {(U1,ET1),(U2,ET2)… (Uk,ETk)}是網(wǎng)絡(luò) N =（ V,E,W）的一個(gè)生成林。 圖論基礎(chǔ)（ 10） 最小生成樹問題（ MST） 最小生成樹問題 :在賦權(quán)網(wǎng)絡(luò) N中，求解權(quán)數(shù)總和最小的生成樹。 第二類問題 ：求賦權(quán)圖中任意兩頂點(diǎn)間的最短路徑。從 vi到 vj的最短路徑的權(quán)記作 d（ vi,vj）。 最短路徑問題 :在所有的（ vi,vj）路中尋求權(quán)為最小的路。 圖論基礎(chǔ)（ 9） 三、最短路徑和最小生成樹 最短路徑 賦權(quán)圖 :若圖 G的每一條邊（ vi,vj）相應(yīng)的有一個(gè)數(shù) l（ vi,vj）（或簡(jiǎn)記為 lij） ,稱此數(shù)為該邊的 權(quán) ，則圖 G為賦權(quán)圖。如此繼續(xù)下去，最后得到的連通的