店鋪選址最短路徑與選址問題-全文預(yù)覽
【正文】 一。因?yàn)?(v5， v6)， (v5 ， v7)∈ E， 而且 v6和 v7都是 T標(biāo)號，故修改它們的 T標(biāo)號為 T(v6)＝ min[T(v6)， P(v5)+w56]＝ min[9， 7+1]= 8 T(v7)＝ min[T(v7)， P(v5)+w57]＝ min[+∞， 7+7]=14 ② 在所有 T標(biāo)號中， T(v6)＝ 8最小，于是令：P(v6)＝ 8。因?yàn)?(v4， v5)∈ E，而且 v5是 T標(biāo)號，故修改 v5的 T標(biāo)號為 T(v5)＝ min[T(v5)， P(v4)+w45]＝ min[+∞， 3+5]＝ 8 ② 在所有的 T標(biāo)號中， T(v3)＝ 4最小，故令 P(v3)＝ 4。因?yàn)?(v1， v2)， (v1， v3)， (v1， v4)∈ E， 而且 v2， v3， v4是 T標(biāo)號，所以修改這 3個(gè)點(diǎn)的 T標(biāo)號為 T(v2)＝ min[T(v2)， P(v1)+w12]＝ min[ +∞， 0+2]＝ 2 T(v3)＝ min[T(v3)， P(v1)+w13 ]＝ min[ +∞， 0+5]＝ 5 T(v4)＝ min[T(v4)， P(v1)+w14 ]＝ min[ +∞， 0+3]＝ 3 ② 在所有 T標(biāo)號中， T(V2)＝ 2最小，于是令 P(V2)＝ 2。試求城鎮(zhèn) v1到 v7之間的最短路徑。 ② 若 G中沒有 T標(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)號。 .n標(biāo)號法的基本思想 設(shè) G是一個(gè)賦權(quán)有向圖，即對于圖中的每一條邊，都賦予了一個(gè)權(quán)值。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 在路徑的優(yōu)選計(jì)算問題中，最常見的是最短路徑問題；而在頂點(diǎn)的優(yōu)選計(jì)算問題中，最為常見的是中心點(diǎn)和中位點(diǎn)選址問題。最短路徑與選址問題 216。其中，最為常見的是關(guān)于路徑和頂點(diǎn)的優(yōu)選計(jì)算問題。那么，各個(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)圖上的最短路徑問題。 n 標(biāo)號法優(yōu)點(diǎn) 不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長度 ； 同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。這些標(biāo)號，又進(jìn)一步區(qū)分為 T標(biāo)號和 P標(biāo)號兩種類型。n標(biāo)號法具體計(jì)算步驟
法律信息相關(guān)推薦
鄂ICP備17016276號-1