第十三講空間分析與查詢四

1、第十三講 空間分析與查詢（四）中山大學(xué) 遙感與地理信息工程系網(wǎng)絡(luò)分析 網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的基本組成部分和屬性 1、鏈（link） 網(wǎng)絡(luò)中流動(dòng)的管線如街道、河流、水管，其狀態(tài)屬性包括阻力和需求。 2、結(jié)點(diǎn)（node） 網(wǎng)絡(luò)中鏈的結(jié)點(diǎn)，如港口、車(chē)站等，其狀態(tài)屬性包括阻力和需求等。 結(jié)點(diǎn)中的特殊類(lèi)型障礙（barrier），禁止網(wǎng)絡(luò)上流動(dòng)的點(diǎn)。拐點(diǎn)（turn），出現(xiàn)在網(wǎng)絡(luò)中的分割點(diǎn)上，其狀態(tài)有屬性和阻力，如拐彎的時(shí)間和限制（如在8點(diǎn)到18點(diǎn)不允許左拐）。中心（center），是接受或分配資源的位置，如水庫(kù)、商業(yè)中心，電站等，其狀態(tài)包括資源容量（如總量），阻力限額（中心到鏈的最大距離或時(shí)間）。站點(diǎn)（stop）

2、，在路徑選擇中資源增減的結(jié)點(diǎn)，如庫(kù)房、車(chē)站等，其狀態(tài)屬性有資源需求，如產(chǎn)品數(shù)量。 路徑分析靜態(tài)求最佳路徑：在給定每條鏈上的屬性后，求最佳路徑。n條最佳路徑分析：確定起或終點(diǎn)，求代價(jià)最小的n條路徑，因?yàn)樵趯?shí)際中最佳路徑的選擇只是理想情況，由于種種要素而要選擇近似最佳路徑。最短路徑或最佳耗費(fèi)路徑：確定起點(diǎn)終點(diǎn)和要經(jīng)過(guò)的中間點(diǎn)、中間連線，求最短路徑或最佳耗費(fèi)路徑。動(dòng)態(tài)最佳路徑分析：實(shí)際網(wǎng)絡(luò)中權(quán)值是隨權(quán)值關(guān)系式變化的，可能還會(huì)臨時(shí)出現(xiàn)一些障礙點(diǎn)，需要?jiǎng)討B(tài)的計(jì)算最佳路徑。 int findmin(int *array, int bound)int min=1000;for(int i=0;ibound;

3、i+) if(arrayi=min) min=arrayi;return min; int array7=789,33,7898,7565,76,22,88;int result=findmin(array,7);assert(result = =22)最佳路徑求解 最佳路徑求解有多種不同的方法，其中dijkstra算法適合于求解某個(gè)起點(diǎn)（源點(diǎn)）到網(wǎng)絡(luò)中的其它各個(gè)結(jié)點(diǎn)的最佳路徑。dijkstra算法（1）1、引進(jìn)一個(gè)輔助向量d，它的每個(gè)分量di表示當(dāng)前所找到的從起點(diǎn) vm 到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。 假設(shè)用帶權(quán)的鄰接矩陣arcs來(lái)表示帶權(quán)有向圖，arcsij表示弧 上的權(quán)值。若 不連通，

4、則arcsij=。那么di的初值為：di=arcsmi viv此外，將已找到的從vm 出發(fā)的最短路徑的終點(diǎn)的集合記為s，它的初始狀態(tài)為空集。dijkstra算法（2）2、選擇 vj 使得dj=mindi | viv-svj就是當(dāng)前求得的一條從vm出發(fā)的最短路徑的終點(diǎn)。其中j為這條最短路徑的終點(diǎn)，將其加入到終點(diǎn)集合s，令s=sjdijkstra算法（3）3、修改輔助向量d，即修改從vm出發(fā)到集合v-s上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。 顯然，若dj+arcsjkdk，則表明從vm出發(fā)，經(jīng)過(guò)vj到達(dá)vk的路徑更短。因此，如果dj+arcsjkdk，則修改dk為dk=dj+arcsjkvmvjvka

5、rcsjk= 8dk= 15dj =5v-ssdijkstra算法（4）4、重復(fù)操作第二步、第三步共n-1次。由此求得從v到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。 例子v5v0v4v1v3v21006030101020505帶權(quán)有向圖鄰接矩陣?yán)?思路)acibi如圖所示，a為所求最短距離的起點(diǎn)，其他bi, ci 為終點(diǎn)。我們要求的是一系列最短距離。我們先假定這些最短距離互不相等。那么我們可以把這些最短距離按升序（從小到大）排列。我們把所有頂點(diǎn)分為兩類(lèi)c和b.令a到bi這些頂點(diǎn)的最短距離不為無(wú)窮大。 a到ci這些頂點(diǎn)的最短距離為無(wú)窮大。這就說(shuō)明a到ci中的點(diǎn)要么不通，要么通過(guò)bi中的

6、點(diǎn)與之連接。 例子(思路)acibi這樣，對(duì)于a到ci中任何一個(gè)點(diǎn)的最小距離，我們總可以在bi中找到一點(diǎn)，使得a到這一點(diǎn)的最小距離小于前一個(gè)距離。（因?yàn)椋篴到ci中的點(diǎn)要么不通，要么通過(guò)bi中的點(diǎn)與之連通。 ）因此，我們可以先不考慮ci中的點(diǎn)。例子(思路)于是，對(duì)于右圖，我們第一步只考慮下圖：v5v0v4v1v3v210060301010505v5v0v4v21003010bi=v2,v4,v5例子(思路)我們用mindist這個(gè)數(shù)組來(lái)保存由v0到其它頂點(diǎn)的最小距離，這些距離按升序排列?？紤]右圖：第一步，通過(guò)比較，我們知道 mindistancev0v2=mindist0=10,（v0-v2)

7、這是我們求出的第一個(gè)最小距離。一旦我們得到v2，我們就可以知道：v5v0v4v21003010例子(思路)v0跟 v2直接連通到的點(diǎn)v3 之間的最小距離不再是無(wú)窮大，它應(yīng)當(dāng)是mindistancev0v2+disv2v3, 這樣我們應(yīng)當(dāng)把v3放入前面的集合bi中。（注意：有多少v2直接連通到的點(diǎn)都應(yīng)當(dāng)考慮進(jìn)來(lái)。）v5v0v4v3v2100301050bi=v2,v4,v5,v3例子(思路)第二步，我們把與v2直接連通的點(diǎn)v3考慮進(jìn)來(lái)。dis05=100; dis04=30;dis02=10; dis03=60;除10以外，30是最小的。 我們可以證明30是v0到其它頂點(diǎn)除10以外最小的。v5v

8、0v4v3v2100301050例子(思路)不可能存在這樣一個(gè)點(diǎn)vn，使得10mindistance0n30.原因如前所述。v5v0v4v3v2100301050vnbi例子(思路)這樣我們得到我們的第二個(gè)最小距離：mindistancev0v4=mindist1=30 ,(v0-v4)接下來(lái)，我們把v4與之直接連通的點(diǎn)考慮進(jìn)來(lái)。v5v0v4v3v2100301050bi例子以v0為起點(diǎn)，計(jì)算它到其它各頂點(diǎn)的最短路徑，計(jì)算過(guò)程中最短路徑長(zhǎng)度向量d的變化見(jiàn)d0-d4，計(jì)算出的各條最短路徑見(jiàn)表4-4。10030100d10030601d90502d603d4d例子例子起點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度v0v

9、1無(wú) v2(v0,v2)10 v3(v0,v4,v3)50 v4(v0,v4)30 v5(v0,v4,v3,v5)60求最短路徑的方法中心選址問(wèn)題 中心點(diǎn)選址問(wèn)題中，最佳選址位置的判定標(biāo)準(zhǔn)，是使其所在的頂點(diǎn)與圖中其它頂點(diǎn)之間的最大距離達(dá)到最小。 這個(gè)選址問(wèn)題實(shí)際上就是求網(wǎng)絡(luò)圖的中心點(diǎn)問(wèn)題。這類(lèi)選址問(wèn)題適宜于醫(yī)院、消防站等服務(wù)設(shè)施的布局問(wèn)題。 中心選址問(wèn)題的圖論描述 設(shè)g=(v,e)是一個(gè)無(wú)向賦權(quán)連通圖，其中v=v1,v2,vn，e=e1,e2,en。連接兩個(gè)頂點(diǎn)的邊的權(quán)值代表該兩頂點(diǎn)之間的距離。對(duì)于每個(gè)頂點(diǎn)vi，它與各頂點(diǎn)之間的最短路徑長(zhǎng)度為di1,di2,din。頂點(diǎn)vi的最大服務(wù)距離是這幾

10、個(gè)最短路徑長(zhǎng)度中的最大值，記為e(vi0)。e(vi0)=max(di1,di2,din)那么，中心點(diǎn)選址問(wèn)題，就是求圖g的中點(diǎn)vi0，使得該頂點(diǎn)的最大服務(wù)距離達(dá)到最小，即 e(vi0)=mine(vi)中心選址問(wèn)題的實(shí)例例如，某縣要在其所轄的8個(gè)鄉(xiāng)鎮(zhèn)之一修建一個(gè)消防站，為8個(gè)鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。假設(shè)該8個(gè)鄉(xiāng)鎮(zhèn)之間的交通網(wǎng)絡(luò)被抽象為圖4-10所示的無(wú)向賦權(quán)連通圖，權(quán)值為鄉(xiāng)鎮(zhèn)之間的距離。下面求解消防站應(yīng)設(shè)在哪個(gè)鄉(xiāng)鎮(zhèn)，即哪個(gè)頂點(diǎn)？中心選址問(wèn)題的實(shí)例v6v8v1v7v5v4v2v389363253757中心選址問(wèn)題的實(shí)例首先，用dijkstra算法計(jì)算出每一個(gè)頂點(diǎn)vi至其它各頂點(diǎn)vj的最短路徑長(zhǎng)度dij(i, j=1,2,6)，寫(xiě)出距離矩陣： 中心選址問(wèn)題的實(shí)例其次，求距離矩陣中每行的最大值，即各個(gè)頂點(diǎn)的最大服務(wù)距離，得e(v1)=14, e(v2)=15, e(v3)=20, e(v4)=12, e(v5)=15, e(v6)=17, e(v7)=12, e(v8)=20最后計(jì)算最大服務(wù)距離的最小值。顯然，e(v4) = e(v7) = min e(vi)。所以，消防站應(yīng)建在v4或v7點(diǎn)所在的鄉(xiāng)鎮(zhèn)即可。中心選址問(wèn)題的實(shí)例其次，求距離矩陣中每行的最大值，即各個(gè)頂點(diǎn)的最大服務(wù)距離，得e(v1)=14, e(v2)=15, e(v3)=20, e(v4)