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