纸上谈兵: 最短路径与贪婪

  • 时间:
  • 浏览:0

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

图是由节点和连接节点的边构成的。节点之间还前要由路径,即边的序列。根据路径,还前要从某些到达另某些。在另三个 繁杂的图中,图中两点还前要居于某些路径。最短路径讨论了另三个 非常简单的图论什么的问题,图中从A点到B点 ,那条路径耗费最短?

你你这种什么的问题又异常繁杂,过后网络的构成情形过后很繁杂。

另三个 最简单的思路,是找出所但会 的从A到B的路径,再通过比较,来寻找最短路径。然而,这并可不不需要 不需要 将什么的问题繁杂2个。过后搜索从A到B的路径,这四种 好多好多 很繁杂的事情。而我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 在搜索所有路径的过程中,有某些路径过后绕了很远,详细可不不需要 不需要 搜索的必要。比如从上海到纽约的路线,详细可不不需要 不需要 必要先从上海飞到南极,再从南极飞到纽约,尽管你你这种路径也是第十根可行的路径。

好多好多 ,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 前要曾经另三个 算法:它还前要搜索路径,并当已知路径包括最短路径时,即停止搜索。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 先以无权网络为例,看另三个 可行的最短路径算法。

无权网络

无权网络(unweighted network)是相对于加权网络的,这里的“权”是权重。每条边的耗费相同,都为1。路径的总耗费即为路径底下的总数。

我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 用“甩鞭子”的依据 ,来寻找最短路径。鞭子的长度代表路径的距离。

手拿另三个 特定长度的鞭子,站在A点。甩出鞭子,能打到某些点。比如C和D。

将鞭子的长度增加1。再甩出鞭子。此时,从C或D出发,寻找距离为1的邻接点,即E和F。哪几种点到A点的距离,为此时鞭子的长度。

记录点E和F,并记录它们的上游节点。比如E(C), F(D)。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 同样还前要记录此时该点到A的距离,比如5。

 

过后要记录节点E时,发现它过后经常突然出现在过后的记录中,这说明曾经有更短的距离到E。此时,不将E放满记录中。毕竟,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 感兴趣的是最短路径。如下图中的E:

黄色的E不被记录

最初的鞭子长度为0,站在A点,可不不需要 不需要 打到A点自身。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 不断增加鞭子长度,第一次还前要打到B时,可不不需要 不需要 此时鞭子的长度,好多好多 从A到B的最短距离。循着我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 的记录,倒推上游的节点,就还前要找出整个最短路径。

我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 的记录本是个很有意思的东西。某个点放满记录时,此时的距离,都是 A点到该点的最短路径。根据记录,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还前要反推出记录中任何某些的最短路径。这就好像真诚对待每另一方。这能保证,当你遇到真爱时,你过后是在真诚相待了。实际上,记录将所有节点分割成另三个 世界:记录内的,已知最短距离的;记录外的,未知的。

加权网络

加权网络中(weighted network),每条边有每个人的权重。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 选取某个路径时,总耗费为路径上所有边的权重之和。

加权网络在生活中很常见,比如从北京到上海,还前要坐火车,也还前要坐飞机。但四种 选取耗费的时间不言而喻同。再比如,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 打出租车和坐公交车,都还前要到市区,但车资都是 所不同。在计算机网络中,过后硬件性能不同,连接的传输时延都是 所差异。加权网络正适用于以上场景。无权网络是加权网络的另三个 特例。

你你这种什么的问题看起来和无权网络颇为累似 。但过后套用底下的依据 ,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 会发现,记录中的节点不言而喻一定是最短距离。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 看下面的例子:

很明显,最短路径是A->C->D->B,过后它的总耗费可不不需要 不需要 4。按照底下的依据 ,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 先将A放满记录。从A出发,有B和C另三个 过后将B和C一块儿放满记录,可不不需要 不需要 记录中的B不言而喻符合最短距离的要求。

可不不需要 不需要 ,为哪几种无权网络可行呢?假设某次记录时,鞭子长度为5,可不不需要 不需要 这次记录点的邻接点,必然是距离为6的点。过后哪几种邻接点可不不需要 不需要 经常突然出现过,可不不需要 不需要 6好多好多 它们的最短距离。所有第一次经常突然出现的邻接点,都将加入到下次的记录中。比如下面的例子,C/D/E是到达A的邻接点,它们到A的最短距离必然都是 1。

对于加权网络来说,即使知道了邻接点,也无法判断它们与否符合最短距离。在记录C/D/E时,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 无法判断未来与否居于如下图虚线的连接,原困A的邻接点E并都是 下一步的最短距离点:

但情形并可不不需要 不需要 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 想的可不不需要 不需要 糟糕。仔细观察,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 发现,实在无法一次判定所有的邻接点为下一步的最短距离点,但我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还前要选取点C过后居于从A出发的最短距离情形。A到C的其它过后性,比如途径D和E,必然原困更大的成本。

也好多好多 说,邻接点中,有另三个 达到了最短距离点,即邻接点中,到达A距离最短的点,比如底下的C。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还前要安全的把C改为已知点。A和C都是 已知点,点P成为新的邻接点。P到A得距离为4。

出于底下的观察,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还前要将节点分为四种 :

  • 已知点:已知到达A最短距离的点。“我是成功人士。”
  • 邻接点:有从记录点出发的边,直接相邻的点。“和成功人士接触,都是 成功的过后哦。”
  • 未知点:“还早得很。”

最初的已知点可不不需要 不需要 A。已知点的直接下游节点为邻接点。对于邻接点,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 前要独立的记录它们。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 要记录的有:

  • 当前情形下,从A点出发到达该邻接点的最短距离。比如对于底下的点D,为6。
  • 此最短距离下的上游节点。对于底下的点D来说,为A。

每次,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 将邻接点中最短距离最小的点X转为已知点,并将该点的直接下游节点,改为邻接点。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 前要计算从A出发,经由X,到达哪几种新增邻接点的距离:新距离 = X最短距离 + QX边的权重。此时有四种 情形,

  • 过后下游节点Q还都是 邻接点,可不不需要 不需要 直接加入,Q最短距离 = 新距离,Q上游节点为X。
  • 过后下游节点Q过后是邻接点,记录在册的上游节点为Y,最短距离为y。过后新距离小于y,可不不需要 不需要 最小距离改为新距离,上游节点也改为X。但会 保持原记录不变。

我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还用底下的图,探索A到E的路径:

第一步

  情形 已知距离 上游
A 已知 0 A
邻接 1 A
D 邻接
E 邻接
P 未知  无穷  

第二步

  情形 已知距离 上游
A 已知 0 A
已知 1 A
D 邻接
E 邻接
P 邻接 4 C

第二步

  情形 已知距离 上游
A 已知 0 A
已知 1 A
D 邻接
E 邻接 7 P
P 已知  4 C

第三步

  情形 已知距离 上游
A 已知 0 A
已知 1 A
D 已知
E 邻接 7 P
P 已知  4 C

最后,E成为已知。倒退,还前要知道路径为E, P, C, A。正过来,好多好多 从A到E的最短路径了。

底下的算法是经典的Dijkstra算法。本质上,每个邻接点记录的,是基于已知点的情形下,最好的选取,也好多好多 所谓的“贪婪算法”(greedy algorithm)。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 贪婪时,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 的决定是临时的,并可不不需要 不需要 做出最终的决定。转换某个点成为已知点后,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 增加了新的过后性,贪婪再次起作用。根据对比。你还能不能 ,某个邻接点成为新的“贪无可贪”的点,即经由其它任意邻接点,到达该点都只会造成更高的成本; 经由未知点到达该点更不过后,过后未知点还可不不需要 不需要 开放,必然前要经过现有的邻接点到达,只会更加绕远。好吧,该点再也可不不需要 不需要 贪婪的动力,就被扔到“成功人士”里,成为已知点。成功学不断传染,最后感染到目标节点B,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 就找到了B的最短路径。

实现

理解了底下的原理,算法的实现是小菜一碟。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 借用图 (graph)中的数据形态,略微修改,构建加权图。

我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 将底下的表格做成数组records,用于记录路径探索的信息。

重新给点A,C,D,E,P命名,为0, 1, 2, 3, 4。

代码如下:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5
#define INFINITY 500000

typedef struct node *position;
typedef struct record *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);
void shortest_path(position, label, int, int, int);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    struct record records[NUM_V];
    int i;

    // initialize the vertices
    for(i=0; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
        (graph+i)->weight  = -1;
    }

    // insert edges
    insert_edge(graph,0,1,1);
    insert_edge(graph,0,2,6);
    insert_edge(graph,0,3,9);
    insert_edge(graph,1,4,3);
    insert_edge(graph,4,3,3);

    print_graph(graph,NUM_V);
    
    // initialize the book
    for (i=0; i<NUM_V; i++){
        (records+i)->status   = -1;
        (records+i)->distance = INFINITY;
        (records+i)->previous = -1;
    }
    
    shortest_path(graph, records, NUM_V, 0, 3);
    
    // 
}
void shortest_path(position graph, label records, 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 = new_neighbors(graph, records, nv, current);
    }
    
    while(current != start) {
        printf("%d <- ", current);
        current = (records+current)->previous;
    }
    printf("%d\n", current);
}

int new_neighbors(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 neighbors
    p = (graph+current)->next;
    while(p != NULL) {
        v = p->element;
        (records + v)->status = 0;
        newDist = p->weight + (records + current)->distance;
        if ((records + v)->distance > newDist) {
            (records + v)->distance = newDist;
            (records + v)->previous = current;
        }
        p = p->next;
    }
    
    // find the next known
    d = INFINITY;
    for (i=0; i<nv; i++) {
        if ((records + i)->status==0 && (records + i)->distance < d){
            d = (records + i)->distance;
            v = i;
        }
    }
    return v;
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%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;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    nodeAddr->weight  = weight;
    np->next = nodeAddr;
}

运行结果如下:

From   0: 0->3; w:9 0->2; w:6 0->1; w:1 

From   1: 1->4; w:3 

From   2: 

From   3: 

From   4: 4->3; w:3 

3 <- 4 <- 1 <- 0

即从0到1到4到3,也好多好多 从A到C到P到E,是我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 的最短路径。

底下的算法中,最坏情形是目标节点最后成为已知点,即要寻找[$O(|V|)$]。而每个已知点是通过寻找[$O(|V|)$]个节点的最小值得到的。最后,打印出最短的路径过程中,前要倒退,最多过后有[$O|E|$],也好多好多 说,算法繁杂度为[$O(|V|^2 + |E|)$]。

底下的records为另三个 数组,用于记录路径探索信息。我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 还前要用另三个 优先队列来代替它,将已知的节点移除优先队列。曾经还前要达到更好的运算时延。

练习: 自行设计另三个 加权网络,寻找最短路径。

总结

最短路径是寻找最优解的算法。在繁杂的网络中,简单的实现依据 无法运行,前要求能够精心设计的算法,比如这里的Dijkstra算法。利用贪婪的思想,我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 我们歌词 歌词 不断的优化结果,直到找到最优解。

欢迎阅读“纸上谈兵: 算法与数据形态”系列