纸上谈兵 最短路径与贪婪.docx

《纸上谈兵 最短路径与贪婪.docx》由会员分享，可在线阅读，更多相关《纸上谈兵 最短路径与贪婪.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图是由节点和连接节点的边构成的。节点之间可以由路径，即边的序列。根据 路径，可以从一点到达另一点。在一个复杂的图中，图中两点可以存在许多路 径。最短路径讨论了一个非常简单的图论问题，图中从A点到B点，那条路 径耗费最短？这个问题又异常复杂，因为网络的构成状况可能很复杂。一个最简单的思路，是找出所有可能的从A到B的路径，再通过比拟，来寻找最短路径。然而，这并没有将问题简化多少。因为搜索从A到B的路径,这本 身就是很复杂的事情。而我们在搜索所有路径的过程中,有许多路径已经绕了状态距离A0C1D邻接6E邻接9P邻接4第二步状态距离A0C1D邻接6E邻接7状态距离P4第三步状态距离A0C1D6E邻接7

2、P4最后，E成为。倒退，可以知道路径为E, P, C, Ao正过来，就是从A到E 的最短路径了。上面的算法是经典的Dijkstra算法。本质上，每个邻接点记录的，是基于 点的情况下,最好的选择，也就是所谓的“贪婪算法(greedy algorithm)o 当我们贪婪时，我们的决定是临时的，并没有做出最终的决定。转换某个点成 为点后，我们增加了新的可能性，贪婪再次起作用。根据比照。随后，某 个邻接点成为新的贪无可贪”的点，即经由其它任意邻接点，到达该点都只 会造成更高的本钱；经由未知点到达该点更不可能，因为未知点还没有开放, 必然需要经过现有的邻接点到达，只会更加绕远。好吧，该点再也没有贪婪的

3、动力，就被扔到“成功人士”里，成为点。成功学不断传染，最后感染到 目标节点B ,我们就找到了 B的最短路径。实现理解了上面的原理，算法的实现是小菜一碟。我们借用图（graph）中的数据结 构，略微修改，构建加权图。我们将上面的表格做成数组records ,用于记录路径探索的信息。重新给点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 edge* with weight*/void insert_edge(position graph, int from, int to, int weight) (position np;posit

11、ion 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;运行结果如下：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 ,因为它的总耗费只有4。按照上面的方 法，我们先将A

12、放入记录。从A出发，有B和C两个如果将B和C同时放入 记录，那么记录中的B并不符合最短距离的要求。那么，为什么无权网络可行呢？假设某次记录时，鞭子长度为5 ,那么这次记录点的邻接点，必然是距离为6的点。如果这些邻接点没有出现过，那么6就 是它们的最短距离。所有第一次出现的邻接点，都将加入到下次的记录中。比 如下面的例子，C/D/E是到达A的邻接点，它们到A的最短距离必然都是L对于加权网络来说，即使知道了邻接点，也无法判断它们是否符合最短距离。 在记录C/D/E时，我们无法判断未来是否存在如下列图虚线的连接,导致a的邻 接点E并不是下一步的最短距离点：但情况并没有我们想的那么糟糕。仔细观察，我们

13、发现，虽然无法一次判定所 有的邻接点为下一步的最短距离点，但我们可以确定点C已经处在从A出发的最短距离状态。A到C的其它可能性，比方途径D和E ,必然导致更大的成 本。也就是说，邻接点中，有一个到达了最短距离点，即邻接点中，到达A距离最 短的点，比方上面的Co我们可以平安的把C改为点。A和C都是点，点P成为新的邻接点。P到A得距离为4O出于上面的观察，我们可以将节点分为三种： 点：到达A最短距离的点。我是成功人士。邻接点：有从记录点出发的边，直接相邻的点。”和成功人士接 触，也有成功的机会哦。 未知点：还早得很。最初的点只有Ao点的直接下游节点为邻接点。对于邻接点，我们需 要独立的记录它们。我

14、们要记录的有： 当前情况下，从A点出发到达该邻接点的最短距离。比方对于上 面的点D ,为6。 此最短距离下的上游节点。对于上面的点D来说，为Ao每次，我们将邻接点中最短距离最小的点X转为点，并将该点的直接下游 节点，改为邻接点。我们需要计算从A出发，经由X,到达这些新增邻接点的 距离：新距离=X最短距离+ QX边的权重。此时有两种情况, 如果下游节点Q还不是邻接点，那么直接加入，Q最短距离= 新距离，Q上游节点为X。 如果下游节点Q已经是邻接点，记录在册的上游节点为Y ,最短 距离为y。如果新距离小于y ,那么最小距离改为新距离,上游节 点也改为X。否那么保持原记录不变。我们还用上面的图，探索A到E的路径：第一步状态距离A0C邻接1D邻接6E邻接9P未知无穷第二步