店鋪選址最短路徑與選址問題-在線瀏覽
2025-03-17 05:28本頁面
【正文】 以上 3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。 權(quán) —— 這種權(quán)值既可以代表 “ 純距離 ” ，又可以代表 “ 經(jīng)濟(jì)距離 ” ，也可以代表 “ 時(shí)間距離 ” 。 n 標(biāo)號(hào)法優(yōu)點(diǎn) 不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長(zhǎng)度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長(zhǎng)度 ； 同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。在圖 G中指定兩個(gè)頂點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè) v1為起點(diǎn)， vk為終點(diǎn)。這些標(biāo)號(hào)，又進(jìn)一步區(qū)分為 T標(biāo)號(hào)和 P標(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)?P標(biāo)號(hào)。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]。否則，把點(diǎn) 的 T標(biāo)號(hào)修改為 P標(biāo)號(hào)，然后再轉(zhuǎn)入 ① 。 例 1：在圖 ，每一個(gè)頂點(diǎn) vi（ i=1， 2， … ， n） 代表一個(gè)城鎮(zhèn)；每一條邊代表相應(yīng)兩個(gè)城鎮(zhèn)之間的交通線，其長(zhǎng)度用邊旁的數(shù)字表示。 圖 賦權(quán)有向交通網(wǎng)絡(luò)圖解 ：首先給 v1標(biāo)上 P標(biāo)號(hào) P(v1)=0， 表示從 v1到 v1的最短路徑為零。 第 1步 ： ① v1是剛得到 P標(biāo)號(hào)的點(diǎn)。 第 2步 ： ① v2是剛得到 P標(biāo)號(hào)的點(diǎn)。 第 3步 ： ① v4是剛得到 P標(biāo)號(hào)的點(diǎn)。 第 4步： ① v3是剛得到 P標(biāo)號(hào)的點(diǎn)。 第 5步： ① v5是剛得到 P標(biāo)號(hào)的點(diǎn)。 第 6步： ① v6是剛得到 P標(biāo)號(hào)的點(diǎn)。 從城鎮(zhèn) v1到 v7之間的最短路徑為 (v1， v2， v3， v5， v6， v7)， 最短路徑長(zhǎng)度為 13。選址問題涉及人類生產(chǎn)、生活、文化、娛樂等各個(gè)方面。 本節(jié)的討論僅限于選址的范圍是一個(gè)地理網(wǎng)絡(luò)，而且選址位置位于網(wǎng)絡(luò)圖的某一個(gè)或幾個(gè)頂點(diǎn)上。 （一） 中心點(diǎn)選址問題 例 ：某縣要在其所轄的 6個(gè)鄉(xiāng)鎮(zhèn)之一修建一個(gè)消防站，為 6個(gè)鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。 中心點(diǎn)選址問題適宜于醫(yī)院、消防站點(diǎn)等一類服務(wù)設(shè)施的布局問題。 這些距離中的最大數(shù)稱為頂點(diǎn) vi的最大服務(wù)距離，記為 e(vi)。每一頂點(diǎn)代表一個(gè)鄉(xiāng)鎮(zhèn)；每一條邊代表連接兩個(gè)鄉(xiāng)鎮(zhèn)之間的公路，每一條邊旁的數(shù)字代表該條公路的長(zhǎng)度。試問該消防站應(yīng)該設(shè)在哪一個(gè)鄉(xiāng)鎮(zhèn)（頂點(diǎn)）？ 圖 解 ： 第 1步： 用標(biāo)號(hào)法求出每一個(gè)頂點(diǎn) vi至其他各個(gè)頂點(diǎn) vj的最短路徑長(zhǎng)度 dij（ i， j ＝ 1， 2，… ， 6）， 并將它們寫成如下的距離矩陣 第 2步： 求每一個(gè)頂點(diǎn)的最大服務(wù)距離。 第 3步： 判定。也就是說
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1