本文共 8042 字，大约阅读时间需要 26 分钟。

图问题中动态规划的应用

阅读本文前要求读者对每个问题的描述都有了解，这里只提供实现方法

一.多段图最短路径问题

那么这里呢我们就不写输入了，数据存储到数组里面就可以了 代码:

import org.junit.Test;import java.util.ArrayList;import java.util.List;public class Main {
       int Max = 65535;   @Test    public void Test(){
           int arc[][] = {
                   {
   Max,4,2,3,Max,Max,Max,Max,Max,Max},                {
   Max,Max,Max,Max,9,8,Max,Max,Max,Max},                {
   Max,Max,Max,Max,6,7,8,Max,Max,Max},                {
   Max,Max,Max,Max,Max,4,7,Max,Max,Max},                {
   Max,Max,Max,Max,Max,Max,Max,5,6,Max},                {
   Max,Max,Max,Max,Max,Max,Max,8,6,Max},                {
   Max,Max,Max,Max,Max,Max,Max,6,5,Max},                {
   Max,Max,Max,Max,Max,Max,Max,Max,Max,7},                {
   Max,Max,Max,Max,Max,Max,Max,Max,Max,3},                {
   Max,Max,Max,Max,Max,Max,Max,Max,Max,Max}        };        int cost = BackPath(10,arc);       System.out.println("最短路径为:"+cost);   }   //该函数返回最短路径长度，同时打印最短路径    //arc是代价矩阵，n为点的个数(注意我们传入的矩阵是已经分好的多段图)    int BackPath(int n,int [][]arc){
           //path[i]用于记录i顶点点的前一个顶点(当然是在我们最后求的最短路径上的)        int path[]=new int[n];        //cost[i]表示0到i的路径长度(当然是在我们最后求的最短路径上的)        int cost[]=new int[n];        for (int i=0;i
   
    =0;i--){
                   //通过入边来更新cost与path              if(cost[j]>cost[i]+arc[i][j]){
                     cost[j]=cost[i]+arc[i][j];                  path[j]=i;              }            }        List
    
      list = new ArrayList<>();        int parent=path[n-1];        while(parent!=-1){
               list.add(0,parent);            parent=path[parent];        }        for (Integer integer : list) {
               System.out.print(integer+"->");        }        System.out.println(n-1);        return cost[n-1];    }}
    
   

假设有k条边,m个段,这时间复杂度为:O(k+m)

二.多源最短路径算法—Floyd算法

import org.junit.Test;public class Main {
       int Max = 65535;   @Test    public void Test(){
           int arc[][] = {
                   {
   Max,5,7,Max,Max,Max,2},                {
   5,Max,Max,9,Max,Max,3},                {
   7,Max,Max,Max,8,Max,Max},                {
   Max,9,Max,Max,Max,4,Max},                {
   Max,Max,8,Max,Max,5,4},                {
   Max,Max,Max,4,5,Max,6},                {
   2,3,Max,Max,4,6,Max}        };        char[] vex = {
   'A','B','C','D','E','F','G'};      int dist[][] = new int[vex.length][vex.length];       String parent[][] = new String[vex.length][vex.length];//parent[i][j]表示i经过parent[i][j]到达j       //parent[i][j]只包含了i到j的1中间节点及i，没有j，因此可以打印时自行补上       Floyd(parent,dist,7,arc,vex);       show(parent,dist,7,vex);   }   //n代表点的个数，该方法利用动规的思想，递推公式为:    //dist[i][j]=min{dist[i][k]+dist[k][j]}(0<=k<=n-1)   void Floyd(String parent[][],int dist[][],int n,int arc[][],char vex[]){
          //先做初始化的工作       for(int i=0;i
   
    dist[i][k]+dist[k][j]){
                        parent[i][j]=parent[i][k]+parent[k][j];//在这里就可以看到parent[i][j]只包含了i到j的1中间节点及i，没有j的用意是为了防止重复                       dist[i][j]=dist[i][k]+dist[k][j];                   }               }   }    void show(String parent[][],int dist[][],int n,char vex[]){
           for(int i=0;i
   

打印结果:(笔者已经检查过了，读者可以自行检查一遍是没有问题的)

A到A的最短路径为AA,对应长度为0 对称0 0A到B的最短路径为AB,对应长度为5 对称5 5A到C的最短路径为AC,对应长度为7 对称7 7A到D的最短路径为AGFD,对应长度为12 对称12 12A到E的最短路径为AGE,对应长度为6 对称6 6A到F的最短路径为AGF,对应长度为8 对称8 8A到G的最短路径为AG,对应长度为2 对称2 2B到A的最短路径为BA,对应长度为5 对称5 5B到B的最短路径为BB,对应长度为0 对称0 0B到C的最短路径为BAC,对应长度为12 对称12 12B到D的最短路径为BD,对应长度为9 对称9 9B到E的最短路径为BGE,对应长度为7 对称7 7B到F的最短路径为BGF,对应长度为9 对称9 9B到G的最短路径为BG,对应长度为3 对称3 3C到A的最短路径为CA,对应长度为7 对称7 7C到B的最短路径为CAB,对应长度为12 对称12 12C到C的最短路径为CC,对应长度为0 对称0 0C到D的最短路径为CEFD,对应长度为17 对称17 17C到E的最短路径为CE,对应长度为8 对称8 8C到F的最短路径为CEF,对应长度为13 对称13 13C到G的最短路径为CAG,对应长度为9 对称9 9D到A的最短路径为DFGA,对应长度为12 对称12 12D到B的最短路径为DB,对应长度为9 对称9 9D到C的最短路径为DFEC,对应长度为17 对称17 17D到D的最短路径为DD,对应长度为0 对称0 0D到E的最短路径为DFE,对应长度为9 对称9 9D到F的最短路径为DF,对应长度为4 对称4 4D到G的最短路径为DFG,对应长度为10 对称10 10E到A的最短路径为EGA,对应长度为6 对称6 6E到B的最短路径为EGB,对应长度为7 对称7 7E到C的最短路径为EC,对应长度为8 对称8 8E到D的最短路径为EFD,对应长度为9 对称9 9E到E的最短路径为EE,对应长度为0 对称0 0E到F的最短路径为EF,对应长度为5 对称5 5E到G的最短路径为EG,对应长度为4 对称4 4F到A的最短路径为FGA,对应长度为8 对称8 8F到B的最短路径为FGB,对应长度为9 对称9 9F到C的最短路径为FEC,对应长度为13 对称13 13F到D的最短路径为FD,对应长度为4 对称4 4F到E的最短路径为FE,对应长度为5 对称5 5F到F的最短路径为FF,对应长度为0 对称0 0F到G的最短路径为FG,对应长度为6 对称6 6G到A的最短路径为GA,对应长度为2 对称2 2G到B的最短路径为GB,对应长度为3 对称3 3G到C的最短路径为GAC,对应长度为9 对称9 9G到D的最短路径为GFD,对应长度为10 对称10 10G到E的最短路径为GE,对应长度为4 对称4 4G到F的最短路径为GF,对应长度为6 对称6 6G到G的最短路径为GG,对应长度为0 对称0 0

时间复杂度为:O(n^3)

三.TSP问题

由于此问题比较复杂，我那下面的例子来详细的讲解。

1.状态转移方程

d(i,V’)表示由i顶点出发经过V’里面的所有顶点仅仅一次然后回到出发点的最短路径长度

2.例子讲解

假设我们是以0为出发点的，最后又要回到0

根据上面的状态转移方程不难画出上面的状态树。很自然地，最下面的一层我们是知道的，

d(1,{
   })=5   发生状态转移(1-->0)d(2,{
   })= 6   发生状态转移(2-->0)d(3,{
   })=3 发生状态转移(3-->0)

接下来我们的工作就是逐层的向上最后把d(0,{1,2,3})求出来。

我们需要明白V’的个数为2^(n-1),其中n为总的顶点数，下面我们要定义数组 V[2^(n-1)],下面我们以上面的例子来看看V[i]的含义

n=4V[0]={
   }V[1]={
   1}V[2]={
   2}V[3]={
   1,2}V[4]={
   3}V[5]={
   1,3}V[6]={
   2,3}V[7]={
   1,2,3}为什么是这样我后面会来介绍

算法步骤如下:

//把0当做出发点与终点，在理解下面伪代码时，应结合上面的状态树来看//状态树最底层来看i不需要为0for(int i=1;i<2^(n-1);i++)	d[i][0]=arc[i][0];//相当于从V[1]~V[2^(n-1)]来遍历一遍，在状态树里面来看的话就是从第二层(也不是严格的,你可能会疑问为//什么，在V[j]的排列中{1,2}排在了{3}的前面,但是{1,2}却在{3}的前面,那这样可行吗?关于这个问题在代码//实现那里我会解释，但总体上我们仍然可以认为他是由底向上的，只是顺序有点不同了)开始往上走，这是合理的//然后的话我们把最顶层(即d(0,V))是单独到最后独立于循环外求的，所以j不可以为2^(n-1)-1for(int j=1;j<2^(n-1)-1;j++)//j是V[j]里面的j	//从状态树来看d(i,V')中i是不为0的(不看最顶层的话),因此i从1开始到n-1即可	for(int i=1;i

下面我们要说的是如何来具体实现呢?在实现之前我需要补充关于位运算的知识

1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算，然后

返回其十进制下的值。例如3(11)&2(10)=2(10)。

2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算，然后

返回其十进制下的值。例如3(11)|2(10)=3(11)。

3.’^’符号，x^y，会将两个十进制数在二进制下进行异或运算，然

后返回其十进制下的值。例如3(11)^2(10)=1(01)。

4.’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移

动两位，最右边用0填充，x<<2相当于让x乘以4。相应的，’>>’

是右移操作，x>>1相当于给x/2，去掉x二进制下的最右一位。

dp状态压缩一般都是与位运算联系紧密的，那么下面我将为大家介绍一些常用的位运算的公式(这些公式不用记忆，在实践中敲代码熟悉即可)

下面的运算我们常用的数据类型都是int型(假设这里int的为c语言里的2字节)A|=1<
   
    >=1)	count+=i&1;下面来介绍一下lowbit操作x&(-x)--->//举例若x=0110 1100,那么结果为100,//即找到最小的那个1的值，具体证明可以尝试用补码来证明下面介绍highbit操作int p = low_bit(x);while(p!=x)x-=p,p=low_bit(x);//最后p即为所求下面我们来介绍判断一个数是否为2的幂次x&&!(x&(x-1))//最前面的x是为了保证x不为0，0的话那么就不是2的幂次
   

下面我们实现一个求各个集合的元素个数的方法:

count[0]=0;for(int i=1;i<2^(n-1);i++){
   	count[i]=count[i>>1]+(i&1);}

最后回到我们的TSP问题

下面我要解释前面的一个的问题，在上面的伪代码中我们介绍了，其实也比较简单，只是那里留了个引子给大家，我们的方式是从V[1]~V[2^(n-1)],会担心一个问题就是由于我们的V[i]的排列顺序并不是按照元素个数大小从小到大来排列的，可能导致在计算某一个状态时他的转移状态并未有计算好从而出错，那么我们试想,加入我们再求某个状态时是将他的每一个里面的1的每次抽取一个出来来求最小值，那么当你抽取一个1时很自然地他会变小，而我们的遍历是从小到大来的，也就是说如果他前面的计算好了，那么他就是没有问题的，那么说到这很自然地可以用数学归纳法就可以证明正确性，这里我就不说了。 代码实现:

import org.junit.Test;public class Main {
       int Max = 65535;   @Test    public void Test(){
          int arc[][] = {
                  {
   Max,3,6,7},               {
   5,Max,2,3},               {
   6,4,Max,2},               {
   3,7,5,Max}       };        TSP_DP(arc,4);   }    //TSP问题,默认0为起始点    void TSP_DP(int arc[][],int n){
       //path[i][j][0]存放当前状态的上一个状态的i，path[i][j][1]存放当前状态的上一个状态的j       int path[][][] = new int[n][1<<(n-1)][2];//路经保存       int dp[][] = new int[n][1<<(n-1)];       //下面我们来初始化        for(int i=1;i
   
    arc[i][k] + dp[k][j - (1 << (k - 1))]){
                                   dp[i][j] = arc[i][k] + dp[k][j - (1 << (k - 1))];                                path[i][j][0]=k;                                path[i][j][1]=j - (1 << (k - 1));                            }                        }                    }                }            }        }        dp[0][(1<<(n-1))-1]=Max;        //最后我们对顶层元素来处理        for(int i=1;i
    
     dp[i][((1<<(n-1))-1)^(1<<(i-1))]+arc[0][i]){
                   dp[0][(1<<(n-1))-1]=dp[i][((1<<(n-1))-1)^(1<<(i-1))]+arc[0][i];                path[0][(1<<(n-1))-1][0]=i;                path[0][(1<<(n-1))-1][1]=((1<<(n-1))-1)^(1<<(i-1));            }        }        System.out.println("最短长度为:"+dp[0][(1<<(n-1))-1]);        //下面来记录路径        int i=0,j=(1<<(n-1))-1;        int temp;        System.out.print("对应路径为:");        System.out.print(0);        while(path[i][j][0]!=-1){
               temp=path[i][j][0];            j=path[i][j][1];            i=temp;            System.out.print("->"+i);        }        System.out.print("->"+0);    }}
    
   

打印结果:

上面 中添加了回溯路径,可以参考下面的图更好理解:

转载地址：http://jvlzi.baihongyu.com/