[精選]店鋪選址最短路徑與選址問題.pptx

《[精選]店鋪選址最短路徑與選址問題.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、最短路徑與選址問題最短路徑問題選址問題對(duì)于許多地理問題，當(dāng)它們被抽象為圖論意義下的網(wǎng)絡(luò)圖時(shí)，問題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計(jì)算問題。其中，最為常見的是關(guān)于路徑和頂點(diǎn)的優(yōu)選計(jì)算問題。在路徑的優(yōu)選計(jì)算問題中，最常見的是最短路徑問題；而在頂點(diǎn)的優(yōu)選計(jì)算問題中，最為常見的是中心點(diǎn)和中位點(diǎn)選址問題?！凹兙嚯x”意義上的最短路徑例如，需要運(yùn)送一批物資從一個(gè)城市到另一個(gè)城市，選擇什么樣的運(yùn)輸路線距離最短？“經(jīng)濟(jì)距離”意義上的最短路徑例如，某公司在10大港口C1，C2，…，C10設(shè)有貨棧，從Ci到Cj之間的直接航運(yùn)價(jià)格，是由市場(chǎng)動(dòng)態(tài)

2、決定的。如果兩個(gè)港口之間無直接通航路線，則通過第三個(gè)港口轉(zhuǎn)運(yùn)。那么，各個(gè)港口之間最廉價(jià)的貨運(yùn)線路是什么？一、最短路徑問題（一）最短路徑的含義“時(shí)間”意義上的最短路徑例如，某家經(jīng)營公司有一批貨物急需從一個(gè)城市運(yùn)往另一個(gè)城市，那么，在由公路、鐵路、河流航運(yùn)、航空運(yùn)輸?shù)?種運(yùn)輸方式和各個(gè)運(yùn)輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運(yùn)輸路線最節(jié)省時(shí)間？以上3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。權(quán)——這種權(quán)值既可以代表“純距離”，又可以代表“經(jīng)濟(jì)距離”，也可以

3、代表“時(shí)間距離”。（二）最短路徑的算法標(biāo)號(hào)法1959年E.W.Dijkstar提出的標(biāo)號(hào)法是最短路徑問題最好的求解方法。標(biāo)號(hào)法優(yōu)點(diǎn)不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長度；同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。.標(biāo)號(hào)法的基本思想設(shè)G是一個(gè)賦權(quán)有向圖，即對(duì)于圖中的每一條邊，都賦予了一個(gè)權(quán)值。在圖G中指定兩個(gè)頂點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè)v1為起點(diǎn)，vk為終點(diǎn)。首先從v1開始，給每一個(gè)頂點(diǎn)標(biāo)一個(gè)數(shù)，稱為標(biāo)號(hào)。這些標(biāo)號(hào)，又進(jìn)一步區(qū)分為T標(biāo)號(hào)和P標(biāo)號(hào)兩種類型。其中

4、，每一個(gè)頂點(diǎn)的T標(biāo)號(hào)表示從起點(diǎn)v1到該點(diǎn)的最短路徑長度的上界，這種標(biāo)號(hào)為臨時(shí)標(biāo)號(hào)；P標(biāo)號(hào)表示從v1到該點(diǎn)的最短路長度，這種標(biāo)號(hào)為固定標(biāo)號(hào)。在最短路徑計(jì)算過程中，對(duì)于已經(jīng)得到P標(biāo)號(hào)的頂點(diǎn)，不再改變其標(biāo)號(hào)；對(duì)于凡是沒有標(biāo)上P標(biāo)號(hào)的頂點(diǎn)，先給它一個(gè)T標(biāo)號(hào)；算法的每一步就是把頂點(diǎn)的T標(biāo)號(hào)逐步修改，將其變?yōu)镻標(biāo)號(hào)。那么，最多經(jīng)過k-1步，就可以求得到從起點(diǎn)v1到每一個(gè)頂點(diǎn)的最短路徑及其長度。標(biāo)號(hào)法具體計(jì)算步驟①如果剛剛得到P標(biāo)號(hào)的點(diǎn)是vi，那么，對(duì)于所有這樣的點(diǎn)將其T標(biāo)號(hào)修改為：min[T(vj)，P(vi)+wij]。②若G

5、中沒有T標(biāo)號(hào)，則停止。否則，把點(diǎn)的T標(biāo)號(hào)修改為P標(biāo)號(hào)，然后再轉(zhuǎn)入①。其中，滿足開始，先給v1標(biāo)上P標(biāo)號(hào)P(v1)＝0，其余各點(diǎn)標(biāo)上T標(biāo)號(hào)T(vj)＝+∞（j≠1）。例1：在圖10.2.1所示的賦權(quán)有向圖中，每一個(gè)頂點(diǎn)vi（i=1，2，…，n）代表一個(gè)城鎮(zhèn)；每一條邊代表相應(yīng)兩個(gè)城鎮(zhèn)之間的交通線，其長度用邊旁的數(shù)字表示。試求城鎮(zhèn)v1到v7之間的最短路徑。圖10.2.1賦權(quán)有向交通網(wǎng)絡(luò)圖解：首先給v1標(biāo)上P標(biāo)號(hào)P(v1)=0，表示從v1到v1的最短路徑為零。其他點(diǎn)(v2，v3，…，v7)標(biāo)上T標(biāo)號(hào)T(vj)＝+∞（j＝2

6、，3，…，7）。第1步：①v1是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T標(biāo)號(hào)，所以修改這3個(gè)點(diǎn)的T標(biāo)號(hào)為T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+2]＝2T(v3)＝min[T(v3)，P(v1)+w13]＝min[+∞，0+5]＝5T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+3]＝3②在所有T標(biāo)號(hào)中，T(V2)＝2最小，于是令P(V2)＝2。第2步：①v2是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v2，v3)，(v2

7、，v6)∈E，而且v3,v6是T標(biāo)號(hào)，故修改v3和v6的T標(biāo)號(hào)為T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9②在所有的T標(biāo)號(hào)中，T(v4)＝3最小，于是令P(v4)＝3。第3步：①v4是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v4，v5)∈E，而且v5是T標(biāo)號(hào)，故修改v5的T標(biāo)號(hào)為T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8②在所有的T標(biāo)號(hào)中，T(v3)＝4最小，故令P(v3)＝4。第

8、4步：①v3是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v3，v5)，(v3，v6)∈E，而且v5和v6為T標(biāo)號(hào)，故修改v5和v6的T標(biāo)號(hào)為T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9②在所有的T標(biāo)號(hào)中，T(v5)＝7最小，故令P(v5)＝7。第5步：