动态规划问题——城市路径问题

若城市路径示意图如下图所示， 图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。

 

思路：

1．标记路口
    为了叙述和编程的方便，对每一个可能经过的路口进行标记。记每个路口为(i，j)，i表示行，j表示列，0≤i≤3，0≤j≤4；记起点A为(0，0)，终点B为(3，4)。    ，
    根据题目的条件，在从A到B的一条通路中，任意两相邻路口 C(i1，j1)。D(i2，j2)的行列必有如下联系：
    i1=i2且j1+1=j2，  或者  i1+1=i2且j1=j2
也就是说，它们或者行相同，或者列相同。
    2．定义函数如dpl(i,j)为从标号为(0，0)的A地到标号为(i，j)的路口最短可能路径长度。例如如dpl(1，0)=1，dpl(0，2)+5，因为它们只有一条路径可选择。而从A地到(1，1)则有两条路可选择：
    (1，0)—>(1，1)  d1=dpl(1，0)+2=1+2=3
    (0，1)—>(1，1)  d2=dpl(0，1)+2=2+2=4应选其中最小值3。用公式表示为：
    dpl(1，1)=min{dpl(1，0)+2，dpl(0，1)+2}
    在一般情况下，如果我们用二维数组H(i，j)和V(i，j)分别表示水平方向和竖直方向的各路段长度，如H(1，2)表示水平方向上路口 (1，1)到路口(1，2)的路段长度，V(1，2)表示竖值方向上路口(0，2)到路口(1，2)的路段长度，则有公式：如 dpl(i，j)=min{dpl(i-1，j)+v(i，j)，dpl(i，j-1)+h(i，j)}  (公式一)其中

┌──┬──────────┐ │  H │  1    2    3  4(j) │ ├──┼──────────┤ │  0 │  1    3    2    3  │ │  1 │  2    2    1    4  │ │  2 │  2    3    4    5  │ │  3 │  2    3    1    2  │ └──┴──────────┘

┌──┬────────────┐ │  V │  0    1    2    3  4(j)│ ├──┼────────────┤ │  1 │  2    2    1    2    4 │ │  2 │  3    4    1    2    3 │ │  3 │  2    1    2    2    3 │ └──┴────────────┘

 

    则找到dpl(3，4)的值，即到达目的地，搜索过程结束。
    3．算法
    (1)搜索最短路径。以(公式一)为递推公式，从dpl(0，0)=0开始，从左往右、从下到上逐一求出各路口的dpl值，直至求出dpl(3， 4)为止。算法为： procedure search_path;
┌───────────────────┐
│初始化dpl(0,0)=0；                    │
├───────────────────┤
│给数组H，V赋值；                      │
├───────────────────┤
│for i:=1 to 3 do                      │
│  ┌─────────────────┤
│  │dpl[i,0]:=dpl[i-1,0]+V[i,0]；     │
├─┴─────────────────┤
│for j:=1 to 4 do                      │
│  ┌─────────────────┤
│  │dpl[0,j]:=dpl[0,j-1]+H[0,j]；     │
├─┴─────────────────┤
│for i:=1 to 3 do                      │
│  ┌─────────────────┤
│  │for j:=1 to 4 do                  │
│  │  ┌───────────────┤
│  │  │d1:=dpl[i-1,j]+V[i,j]；       │
│  │  ├───────────────┤
│  │  │d2:=dpl[i,j-1]+H[i,j]；       │
│  │  ├───────────────┤
│  │  │  T    　＼ d1 < d2 ／     F  │
│  │  ├───────┬───────┤
│  │  │dpl[i,j]:=d1; │dpl[i,j]:=d2；│
└─┴─┴───────┴───────┘    (2)寻找最短路径。把通过算法(1)搜索到的最短路径保存下来，可以用逆推法。即从(3，4)开始，找(3，3)和(2，4)两点，判断哪个路口是来的路口。这只要比较从这两路口来的路程长度哪个等于 dpl[i,j]即可。算法如下：
 procedure fond_pnth；
    Begin
    i:=m；j:=n；
    pnt:=0；
    pnth_i[0]:=i；    {记录目的路口横坐标}
    path_j[0]:=j；    {记录目的路口纵坐标}
    repeat
      dl: =dpl[i-l,j] +v[i,j];
      d2: =dplIi,j-1] +h[i,j];
      if d1 < d2 then i:=i-1 else j:=j-1;
      inc(pnt);
      path_i[pnt]:= i;path_j[pnt]:=j;  {记录路径上各点坐标}
    until (i=O) and (j=O); {横、纵坐标均为0，回到出发地，倒推结束}
 End;

 

代码：

 

#include <stdio.h>
void main()
{
 int v[4][5] = {{0,0,0,0,0}, {2,2,1,2,4}, {3,4,1,2,3}, {2,1,2,2,3}};
 int h[4][5] = {{0,1,3,2,3}, {0,2,2,1,4}, {0,2,3,4,5}, {0,2,3,1,2}};
 int cost[4][5] = {0};
 int i, j, temp1, temp2, count = 0, row[8] = {0}, column[8] = {0};
/*************
 求最短代价
*************/
 for (i = 1; i <= 3; i++)
 {
  cost[i][0] = cost[i-1][0] + v[i][0];
 }
 for (j = 1; j <= 4; j++)
 {
  cost[0][j] = cost[0][j-1] + h[0][j];
 }
 for (i = 1; i <= 3 ; i++)
  for (j = 1; j <=4; j++)
  {
   temp1 = cost[i-1][j] + v[i][j];
   temp2 = cost[i][j-1] + h[i][j];
   cost[i][j] = temp1 > temp2 ? temp2 : temp1;
  }
 printf("最小代价是：%d\n", cost[3][4]);
/*************
 求最短路径
*************/
 i = 3;
 j = 4;
 row[0] = i;
 column[0] = j;
 while (i!=0 && j!=0)
 {
  temp1 = cost[i-1][j] + v[i][j];
  temp2 = cost[i][j-1] + v[i][j];
  temp1 < temp2 ? i-- : j--;
  count++;
  row[count] = i;
  column[count] = j;
 }
 printf("最短路径为：\n");
 for (i = 7; i >= 0 ; i--)
 {
  printf("(%d, %d)\n", row[i], column[i]);
 }
}