动态规划

       动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

Dijkstra算法

原理

1.首先，引入一个辅助向量D，它的每个分量 D

  

表示当前所找到的

Dijkstra算法运行动画过程

从起始点

  

（即源点

  

）到其它每个顶点

  

的长度。

例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。[1] 

2.D的初始状态为：若从

  

到

  

有弧（即从

  

到

  

存在连接边），则D

  

为弧上的权值（即为从

  

到

  

的边的权值）；否则置D

  

为∞。

显然，长度为 D

  

= Min{ D |

  

∈V } 的路径就是从

  

出发到顶点

  

的长度最短的一条路径，此路径为(

  

)。

3.那么，下一条长度次短的是哪一条呢？也就是找到从源点

  

到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点

  

到顶点

  

的最短路径长度。

假设该次短路径的终点是

  

，则可想而知，这条路径要么是(

  

)，或者是(

  

)。它的长度或者是从

  

到

  

的弧上的权值，或者是D

  

加上从

  

到

  

的弧上的权值。

4.一般情况下，假设S为已求得的从源点

  

出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为

  

）要么是弧(

  

)，或者是从源点

  

出发的中间只经过S中的顶点而最后到达顶点

  

的路径。

因此，下一条长度次短的的最短路径长度必是D

  

= Min{ D

  

|

  

∈V-S }，其中D

  

要么是弧(

  

)上的权值，或者是D

  

(

  

∈S)和弧(

  

,

  

)上的权值之和。

算法描述如下：

1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从

  

出发的的终点的集合，初始状态为空集。那么，从

  

出发到图上其余各顶点

  

可能达到的长度的初值为D=arcs[Locate Vex(G,

  

)]，

  

∈V；

2）选择

  

，使得D

  

=Min{ D |

  

∈V-S } ；

3）修改从

  

出发的到集合V-S中任一顶点

  

的最短路径长度。[1] 

问题描述

在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短值。[2] 

算法思想

按路径长度递增次序产生算法：

把顶点集合V分成两组：

（1）S：已求出的顶点的集合（初始时只含有源点V0）

（2）V-S=T：尚未确定的顶点集合

将T中顶点按递增的次序加入到S中，保证：

（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

（反证法可证）

求最短路径步骤

算法步骤如下：

G={V,E}

1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中

3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法实现

下面是该算法的C语言实现[1] 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<stdio.h> #include<stdlib.h> #define max 11000000000 inta[1000][1000]; intd[1000];//d表示某特定边距离 intp[1000];//p表示永久边距离 inti,j,k; intm;//m代表边数 intn;//n代表点数 intmain() { scanf("%d%d",&n,&m); intmin1; intx,y,z; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); a[x][y]=z; a[y][x]=z; } for(i=1;i<=n;i++) d[i]=max1; d[1]=0; for(i=1;i<=n;i++) { min1=max1; for(j=1;j<=n;j++) if(!p[j]&&d[j]<min1) { min1=d[j]; k=j; } p[k]=j; for(j=1;j<=n;j++) if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j]) d[j]=d[k]+a[k][j]; } for(i=1;i<n;i++) printf("%d->",p[i]); printf("%d\n",p[n]); return0; }

大学经典教材<<数据结构>>(C语言版 严蔚敏 吴为民 编著) 中该算法的实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

/* 测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大 6 1000000 1000000 10 100000 30 100 1000000 1000000 5 1000000 1000000 1000000 1000000 1000000 1000000 50 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10 1000000 1000000 1000000 20 1000000 60 1000000 1000000 1000000 1000000 1000000 1000000 结果： D[0]   D[1]   D[2]   D[3]   D[4]   D[5]  0   1000000   10     50     30     60 */ #include <iostream> #include <cstdio> #define MAX 1000000 using namespace std; int arcs[10][10];//邻接矩阵 int D[10];//保存最短路径长度 int p[10][10];//路径 int final[10];//若final[i] = 1则说明 顶点vi已在集合S中 int n = 0;//顶点个数 int v0 = 0;//源点 int v,w; void ShortestPath_DIJ() {      for (v = 0; v < n; v++) //循环 初始化      {           final[v] = 0; D[v] = arcs[v0][v];           for (w = 0; w < n; w++) p[v][w] = 0;//设空路径           if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}      }      D[v0] = 0; final[v0]=0; //初始化 v0顶点属于集合S      //开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中      for (int i = 1; i < n; i++)      {           int min = MAX;           for (w = 0; w < n; w++)           {                //我认为的核心过程--选点                if (!final[w]) //如果w顶点在V-S中                {                     //这个过程最终选出的点 应该是选出当前V-S中与S有关联边                     //且权值最小的顶点 书上描述为 当前离V0最近的点                     if (D[w] < min) {v = w; min = D[w];}                }           }           final[v] = 1; //选出该点后加入到合集S中           for (w = 0; w < n; w++)//更新当前最短路径和距离           {                /*在此循环中 v为当前刚选入集合S中的点                则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新                比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]                */                if (!final[w] && (min+arcs[v][w]<D[w]))                {                     D[w] = min + arcs[v][w];                    // p[w] = p[v];                     p[w][w] = 1; //p[w] = p[v] +　[w]                }           }      } }     int main() {     cin >> n;     for (int i = 0; i < n; i++)     {          for (int j = 0; j < n; j++)          {               cin >> arcs[i][j];          }     }     ShortestPath_DIJ();     for (int i = 0; i < n; i++) printf("D[%d] = %d\n",i,D[i]);     return 0; }

动态规划、记忆化搜索、Dijkstra算法的总结

原文：http://blog.csdn.net/lieacui/article/details/51750682