Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(2)

在问题1线性搜索里,我们提到了状态转移图模型,因为与通用解法等价,所以基本所有动态规划问题都可以用图论的方法求解,很多问题等价于一个最短路径问题。而本文主要介绍一下通俗的最短路问题——DP第二题:SPA(Shortest Path in an Acyclic Graph)。

对于一个无环图来讲(有环图后面讲到),一个起始节点为s,一个目标节点为t,DPFE为:f(p) = min q{ b(p,q) + f(q)},其中b(p,q)是从p到q的距离,f(p)是从p到t的最短路径,另外这里的p是q的前驱节点,如果p不是q的直接前驱,那么b(p,q)=∞。而目标函数就是求 f(s),base condition就是f(t)=0。

那么举例如下:一个有向无环图,其有四个节点,集合为{s,x,y,t},五条边,边集合为{(s,x), (s,y), (x,y), (x,t), (y,t)},长度为{3,5,1,8,5}。那么求从s到t的最短路径。

image

首先使每个节点都有到t的边,如果没有的,加一条虚拟边,长度为∞,即(s,t)=∞。DPFE为:f(s) = min{b(s,x)+f(x), b(s,y)+f(y), b(s,t)+f(t)},f(x) = min{b(x,y)+f(y), b(x,t)+f(t)},f(y) = min{b(y,t)+f(t)},f(t)=0。依次代入,得到f(y)=min{5+0}=5,f(x)=min{1+5,8+0}=6,f(s)=min{3+6,5+5,∞+0}=9。

因此最短路径长度为9,路径为s->x->y->t。

代码是经典的最短路代码,使用邻接矩阵来表示一个有向无环图,这里仍然用一个递归函数来简化:

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:  
  18: import java.util.HashSet;
  19: import java.util.Set;
  20:  
  21: public class ShortestPathAcyclic {
  22:  
  23:     private static final int INF = Integer.MAX_VALUE;
  24:  
  25:     // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3
  26:     private static int[][] distance = { 
  27:         { INF, 3,      5,     INF }, 
  28:         { INF, INF, 1,     8 },
  29:         { INF, INF, INF, 5 }, 
  30:         { INF, INF, INF, INF } 
  31:     };
  32:  
  33:     private static Set<Integer> possibleNextNodes(int node) {
  34:         Set<Integer> result = new HashSet<Integer>();
  35:         for (int i = 0; i < distance[node].length; i++) {
  36:             if (distance[node][i] != INF) {
  37:                 result.add(new Integer(i));
  38:             }
  39:         }
  40:         return result;
  41:     }
  42:     
  43:     public static double f(int currentNode){
  44:         if(currentNode==3) return 0.0;
  45:         else{
  46:             Set<Integer> possibleSuccessors = possibleNextNodes(currentNode);
  47:             double min = Double.MAX_VALUE;
  48:             for(Integer d : possibleSuccessors){
  49:                 double dis = distance[currentNode][d]+f(d);
  50:                 if(dis<min) {
  51:                     min = dis;
  52:                 }
  53:             }
  54:             return min;
  55:         }
  56:     }
  57:  
  58:     /**
  59:      * @param args
  60:      */
  61:     public static void main(String[] args) {
  62:         double shortest = f(0);
  63:         System.out.println(shortest);
  64:     }
  65:  
  66: }

 

其实这个版本的代码没有记录路径,只求出了最短距离值,路径的记录有很多种方式,最直观的方法是在f函数内部的for循环结束后,把最小距离计算出的对应的后继节点d保存,然后记录一个(currentNode,d)这样的一个节点对,保存到currentNode为key的一个map里,表示对应从currentNode开始到d选定的最短距离的边,最后把map里所有这些边都拿出来拼成一个路径即可。具体代码就不写了(因为考虑到影响对动态规划的理解,记得算法导论里也是把记录路径单独写一个函数去讲解的)。


posted on 2014-03-17 13:40 changedi 阅读(1308) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。


网站导航: