店鋪選址最短路徑與選址問題(已修改)
2025-02-21 05:28 本頁面
【正文】 最短路徑與選址問題 216。最短路徑問題216。選址問題 對于許多地理問題，當(dāng)它們被抽象為圖論意義下的網(wǎng)絡(luò)圖時，問題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計算問題。其中，最為常見的是關(guān)于路徑和頂點的優(yōu)選計算問題。 在路徑的優(yōu)選計算問題中，最常見的是最短路徑問題；而在頂點的優(yōu)選計算問題中，最為常見的是中心點和中位點選址問題。 n “純距離 ”意義上的最短路徑 例如， 需要運送一批物資從一個城市到另一個城市，選擇什么樣的運輸路線距離最短？n “經(jīng)濟距離 ”意義上的最短路徑 例如，某公司在 10大港口 C1， C2， … ，C10設(shè)有貨棧，從 Ci到 Cj之間的直接航運價格，是由市場動態(tài)決定的。如果兩個港口之間無直接通航路線，則通過第三個港口轉(zhuǎn)運。那么，各個港口之間最廉價的貨運線路是什么？一、最短路徑問題（一）最短路徑的含義n “ 時間 ” 意義上的最短路徑 例如，某家經(jīng)營公司有一批貨物急需從一個城市運往另一個城市，那么，在由公路、鐵路、河流航運、航空運輸?shù)?4種運輸方式和各個運輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運輸路線最節(jié)省時間？ 以上 3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 權(quán) —— 這種權(quán)值既可以代表 “ 純距離 ” ，又可以代表 “ 經(jīng)濟距離 ” ，也可以代表 “ 時間距離 ” 。 （二） 最短路徑的算法n 標(biāo)號法 1959年 提出的標(biāo)號法是最短路徑問題最好的求解方法 。 n 標(biāo)號法優(yōu)點 不僅可以求出起點到終點的最短路徑及其長度，而且可以求出起點到其他任何一個頂點的最短路徑及其長度 ； 同時適用于求解有向圖或無向圖上的最短路徑問題。 .n標(biāo)號法的基本思想 設(shè) G是一個賦權(quán)有向圖，即對于圖中的每一條邊，都賦予了一個權(quán)值。在圖 G中指定兩個頂點，確定為起點和終點，不妨設(shè) v1為起點， vk為終點。 首先 從 v1開始，給每一個頂點標(biāo)一個數(shù)，稱為標(biāo) 號。這些標(biāo)號，又進一步區(qū)分為 T標(biāo)號和 P標(biāo)號兩種類型。其中，每一個頂點的 T標(biāo)號表示從起點 v1到該點的最短路徑長度的上界，這種標(biāo)號為臨時標(biāo)號； P標(biāo)號表示從 v1到該點的最短路長度，這種標(biāo)號為固定標(biāo)號。 在最短路徑計算過程中，對于已經(jīng)得到 P標(biāo)號的頂點，不再改變其標(biāo)號；對于凡是沒有標(biāo)上 P標(biāo)號的頂點，先給它一個 T標(biāo)號；算法的每一步就是把頂點的 T標(biāo)號逐步修改，將其變?yōu)?P標(biāo)號。 那么，最多經(jīng)過 k1步，就可以求得到從起點 v1到每一個頂點的最短路徑及其長度。n標(biāo)號法具體計算步驟 ① 如果剛剛得到 P標(biāo)號的點是 vi， 那么，對于所有這樣的點 將其 T標(biāo)號修改為： mi
法律信息相關(guān)推薦
鄂ICP備17016276號-1