紙上談兵 最短路徑與貪婪

1、圖是由節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊構(gòu)成的。節(jié)點(diǎn)之間可以由路徑，即邊的序列。根據(jù) 路徑，可以從一點(diǎn)到達(dá)另一點(diǎn)。在一個(gè)復(fù)雜的圖中，圖中兩點(diǎn)可以存在許多路 徑。最短路徑討論了一個(gè)非常簡單的圖論問題，圖中從A點(diǎn)到B點(diǎn)，那條路 徑耗費(fèi)最短？這個(gè)問題又異常復(fù)雜，因?yàn)榫W(wǎng)絡(luò)的構(gòu)成狀況可能很復(fù)雜。一個(gè)最簡單的思路，是找出所有可能的從A到B的路徑，再通過比擬，來尋找最短路徑。然而，這并沒有將問題簡化多少。因?yàn)樗阉鲝腁到B的路徑,這本 身就是很復(fù)雜的事情。而我們?cè)谒阉魉新窂降倪^程中,有許多路徑已經(jīng)繞了狀態(tài)距離A0C1D鄰接6E鄰接9P鄰接4第二步狀態(tài)距離A0C1D鄰接6E鄰接7狀態(tài)距離P4第三步狀態(tài)距離A0C1D6E鄰接7

2、P4最后，E成為。倒退，可以知道路徑為E, P, C, Ao正過來，就是從A到E 的最短路徑了。上面的算法是經(jīng)典的Dijkstra算法。本質(zhì)上，每個(gè)鄰接點(diǎn)記錄的，是基于 點(diǎn)的情況下,最好的選擇，也就是所謂的“貪婪算法(greedy algorithm)o 當(dāng)我們貪婪時(shí)，我們的決定是臨時(shí)的，并沒有做出最終的決定。轉(zhuǎn)換某個(gè)點(diǎn)成 為點(diǎn)后，我們?cè)黾恿诵碌目赡苄裕澙吩俅纹鹱饔?。根?jù)比照。隨后，某 個(gè)鄰接點(diǎn)成為新的貪無可貪”的點(diǎn)，即經(jīng)由其它任意鄰接點(diǎn)，到達(dá)該點(diǎn)都只 會(huì)造成更高的本錢；經(jīng)由未知點(diǎn)到達(dá)該點(diǎn)更不可能，因?yàn)槲粗c(diǎn)還沒有開放, 必然需要經(jīng)過現(xiàn)有的鄰接點(diǎn)到達(dá)，只會(huì)更加繞遠(yuǎn)。好吧，該點(diǎn)再也沒有貪婪的

3、動(dòng)力，就被扔到“成功人士”里，成為點(diǎn)。成功學(xué)不斷傳染，最后感染到 目標(biāo)節(jié)點(diǎn)B ,我們就找到了 B的最短路徑。實(shí)現(xiàn)理解了上面的原理，算法的實(shí)現(xiàn)是小菜一碟。我們借用圖（graph）中的數(shù)據(jù)結(jié) 構(gòu)，略微修改，構(gòu)建加權(quán)圖。我們將上面的表格做成數(shù)組records ,用于記錄路徑探索的信息。重新給點(diǎn)A,C,D,E,P命名，為A 1, 2, 3, 40代碼如下：/* By Vamei */ftinclude ftinclude ftdefine NUM_V 5ttdefine INFINITY 10000typedef struct node position;typedef struct record *

4、label;/* node */struct node int element;position next;int weight;);/* table element, keep record */struct record int status;int distance;int previous;/* operations (stereotype)*/void insert_edge(position, int, int, int);void print_ graph(position, int);int new neighbors(position, label, int, int);vo

5、id shortest_path(position, label, int, int, int);/* for testing purpose */void main()(struct node graphNUM_V;struct record recordsNUM_V;int i;/ initialize the verticesfor(i=0; ielement = i;(graph+i)-next = NULL;(graph+i)-weight =-1;/ insert edgesinsert_edge(graph,0,1,1);insertedge(graph,0,2,6);inser

6、t_edge(graph, 0, 3, 9);insert edge (graph, 1, 4, 3);insert_edge(graph, 4, 3, 3);print_graph(graph, NUM_V);/ initialize the bookfor (i=0; istatus =-1;(records+i)-distance = INFINITY;(records+i)-previous =-1;shortest_path(graph, records, NUM_V, 0, 3);/)void shortest_path(position graph, label records,

7、 int nv, int start, int end) int current;(records+start)-status二 1；(records+start)-distance = 0;(records+start)-previous = 0;current = start;while(current != end) current = newneighbors(graph, records, nv, current);while (current != start) printf (，z%d一 ，current);current = (records+current)-previous

8、;printf (z，%dn，z, current);)int newneighbors(position graph, label records, int nv, int current) int newDist;int v;int i;int d;position p;/ update the current known(records + current)-status = 1;/ UPDATE new neighborsp 二(graph+current)-next;while(p !二 NULL) v = p-element;(records + v)-status = 0;new

9、Dist = p-weight + (records + current)-distance; if (records + v)-distance newDist) (records + v)-distance = newDist;(records + v)-previous = current;p = p-next;/ find the next knownd = INFINITY;for (i=0; istatus=0 & (records + i)-distance d) d 二(records + i)-distance;v = i;)return v;/* print the gra

10、ph */void print_graph(position graph, int nv) int i;position p;for (i=0; inext;printfCFrom %3d: ，i);while(p != NULL) printf (，z%d-%d; w:%d ，i, p-element, p-weight);p = p-next;printf (n);)/*insert an edgewith weight*/void insert_edge(position graph, int from, int to, int weight) (position np;position

11、 nodeAddr;np 二 graph + from;nodeAddr =(position) malloc(sizeof(struct node);nodeAddr-element = to;nodeAddr-next = np-next;nodeAddr-we i ght = weight;np-next = nodeAddr;運(yùn)行結(jié)果如下：From 0: 0-3; w:9 0-2; w:6 0-l; w:lFrom 1: l-4; w:3From 2:From 3:From 4: 4-3; w:33 - 4 - 1 C-D-B ,因?yàn)樗目偤馁M(fèi)只有4。按照上面的方 法，我們先將A放入記

12、錄。從A出發(fā)，有B和C兩個(gè)如果將B和C同時(shí)放入 記錄，那么記錄中的B并不符合最短距離的要求。那么，為什么無權(quán)網(wǎng)絡(luò)可行呢？假設(shè)某次記錄時(shí)，鞭子長度為5 ,那么這次記錄點(diǎn)的鄰接點(diǎn)，必然是距離為6的點(diǎn)。如果這些鄰接點(diǎn)沒有出現(xiàn)過，那么6就 是它們的最短距離。所有第一次出現(xiàn)的鄰接點(diǎn)，都將加入到下次的記錄中。比 如下面的例子，C/D/E是到達(dá)A的鄰接點(diǎn)，它們到A的最短距離必然都是L對(duì)于加權(quán)網(wǎng)絡(luò)來說，即使知道了鄰接點(diǎn)，也無法判斷它們是否符合最短距離。 在記錄C/D/E時(shí)，我們無法判斷未來是否存在如下列圖虛線的連接,導(dǎo)致a的鄰 接點(diǎn)E并不是下一步的最短距離點(diǎn)：但情況并沒有我們想的那么糟糕。仔細(xì)觀察，我們發(fā)現(xiàn)，

13、雖然無法一次判定所 有的鄰接點(diǎn)為下一步的最短距離點(diǎn)，但我們可以確定點(diǎn)C已經(jīng)處在從A出發(fā)的最短距離狀態(tài)。A到C的其它可能性，比方途徑D和E ,必然導(dǎo)致更大的成 本。也就是說，鄰接點(diǎn)中，有一個(gè)到達(dá)了最短距離點(diǎn)，即鄰接點(diǎn)中，到達(dá)A距離最 短的點(diǎn)，比方上面的Co我們可以平安的把C改為點(diǎn)。A和C都是點(diǎn)，點(diǎn)P成為新的鄰接點(diǎn)。P到A得距離為4O出于上面的觀察，我們可以將節(jié)點(diǎn)分為三種：點(diǎn)：到達(dá)A最短距離的點(diǎn)。我是成功人士。鄰接點(diǎn)：有從記錄點(diǎn)出發(fā)的邊，直接相鄰的點(diǎn)。”和成功人士接 觸，也有成功的機(jī)會(huì)哦。未知點(diǎn)：還早得很。最初的點(diǎn)只有Ao點(diǎn)的直接下游節(jié)點(diǎn)為鄰接點(diǎn)。對(duì)于鄰接點(diǎn)，我們需 要獨(dú)立的記錄它們。我們要記錄的有：當(dāng)前情況下，從A點(diǎn)出發(fā)到達(dá)該鄰接點(diǎn)的最短距離。比方對(duì)于上 面的點(diǎn)D ,為6。此最短距離下的上游節(jié)點(diǎn)。對(duì)于上面的點(diǎn)D來說，為Ao每次，我們將鄰接點(diǎn)中最短距離最小的點(diǎn)X轉(zhuǎn)為點(diǎn)，并將該點(diǎn)的直接下游 節(jié)點(diǎn)，改為鄰接點(diǎn)。我們需要計(jì)算從A出