Java教程

算法设计与分析:动态规划

本文主要是介绍算法设计与分析:动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 3-2 编辑距离
    • 问题描述
    • 算法描述
    • 关键代码
    • 结果分析
  • 3-5 乘法表问题
    • 问题描述
    • 算法描述
    • 关键代码
    • 结果分析
  • 3-7 汽车加油行驶问题
    • 问题描述
    • 算法描述
    • 关键代码
    • 结果分析

3-2 编辑距离

问题描述

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离,记为d(A,B)。对于给定的字符串A和字符串B,计算其编辑距离 d(A,B)。

算法描述

解决两个字符串的动态规划问题,一般都是用两个指针 i, j 分别指向两个字符串的最后,然后一步步往前走,缩小问题的规模。

对于每对字符 s1[i]s2[j],可以有四种操作:

if s1[i-1] == s2[j-1]
    不作操作(skip)
    i, j 同时向前移动
else
    三选一,取最小:
        插入(insert)
        删除(delete)
        替换(replace)

定义 dp 数组:dp[i][j] 存储 s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离

上述四种选择所对应的 dp 递推表达式为:

匹配操作:

\[dp[i][j]=dp[i-1][j-1] \]

插入,删除,替换操作,

\[dp[i][j] = min( dp[i][j - 1] + 1,dp[i - 1][j] + 1,dp[i - 1][j - 1] + 1) \]

关键代码

        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1+1][n2+1];

        //base case
        for(int i=0;i<=n2;i++){
            dp[0][i]=i;
        }
        for(int i=0;i<=n1;i++){
            dp[i][0]=i;
        }
        //状态转移
        for(int i=1;i<=n1;i++){
            for(int j =1;j<=n2;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=1+Math.min(
                        dp[i][j-1],
                        Math.min(dp[i-1][j],dp[i-1][j-1])
                    );
                }
            }
        }
 	   System.out.println(dp[n1][n2]);

结果分析

输入: word1 = "fxpimu", word2 = "xwrs"

输出:5

输入: word1 = "horse", word2 = "ros"

输出:3

输入:word1 = "intention", word2 = "execution"

输出:5

dp数组的每一项均只被访问一次,算法时间复杂度为\(O(n1*n2)\),空间复杂度为\(O(n1*n2)\),\(n1,n2\)分别为字符串w1,w2的长度

3-5 乘法表问题

问题描述

定义于字母表∑{a,b,c)上的乘法表如表所示:

  img

依此乘法表,对任一定义于∑{a,b,c}上的字符串,适当加括号表达式后得到一个表达式。

例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。

试设计一个动态规划算法,对任一定义于∑{a,b,c}上的字符串x=x1x2…xn,计算有多少种不同的加括号方式, 使由x导出的加括号表达式的值为a。

算法描述

设 0, 1 ,2 分别表示常量a,b,c,N为字符串的长度。

定义dp数组:dp[i][j][k],表示字符字串i-j有多少种不同的加括号方式得到k

设字符串的第 i 到 第 j 位乘积为 a 的加括号法有 dp[i][j][0]种,

 字符串的第 i 到 第 j 位乘积为 b 的加括号法有dp[i][j][1] 种,

 字符串的第 i 到 第 j 位乘积为 c 的加括号法有 dp[i][j][2] 种。

则原问题的解是: dp[0][N-1][0] 。

设 k 为 i 到 j 中的某一个字符,则对于 k 来说,根据乘法表有:

dp[i][j][0] += dp[i][k][0] * dp[k + 1][j][2] + dp[i][k][1] * dp[k + 1][j][2] + dp[i][k][2] * dp[k + 1][j][0];
dp[i][j][1] += dp[i][k][0] * dp[k + 1][j][0] + dp[i][k][0] * dp[k + 1][j][1] + dp[i][k][1] * dp[k + 1][j][1];
dp[i][j][2] += dp[i][k][1] * dp[k + 1][j][0] + dp[i][k][2] * dp[k + 1][j][1] + dp[i][k][2] * dp[k + 1][j][2];

dp数组遍历顺序:

img

关键代码

        String str = scan.nextLine();
        int n = str.length();

        //dp[i][j][k]表示字符子串i:j乘积为k的总数(k=a,b,c)
        int[][][] dp = new int[n][n][3];
        for (int i = 0; i < n; i++) {
            dp[i][i][0] = str.charAt(i) == 'a' ? 1 : 0;
            dp[i][i][1] = str.charAt(i) == 'b' ? 1 : 0;
            dp[i][i][2] = str.charAt(i) == 'c' ? 1 : 0;
        }
        for (int r = 2; r <= n; r++) {
            for (int i = 0; i < n - r + 1; i++) {
                //字符子串i:j
                int j = i + r - 1;
                for (int k = i; k < j; k++) {
     dp[i][j][0] += dp[i][k][0]*dp[k + 1][j][2] + dp[i][k][1]*dp[k + 1][j][2] + dp[i][k][2]*dp[k + 1][j][0];
     dp[i][j][1] += dp[i][k][0]*dp[k + 1][j][0] + dp[i][k][0]*dp[k + 1][j][1] + dp[i][k][1]*dp[k + 1][j][1];
     dp[i][j][2] += dp[i][k][1]*dp[k + 1][j][0] + dp[i][k][2]*dp[k + 1][j][1] + dp[i][k][2]*dp[k + 1][j][2];
                }
            }
        }
        System.out.println(dp[0][n - 1][0]);
    }

结果分析

输入:bbbba

输出:6

输入:bbcbabcabc

输出:2093

算法时间复杂度\(O(N^3)\),空间复杂度\(O(N^2)\),N为字符串的长度

3-7 汽车加油行驶问题

问题描述

给定一个N×N 的方形网格,设其左上角为起点◎,坐标(1,1),X轴为正, Y轴向下为正,每个方格边长为 1 ,如图所示。

一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 (N,N)。

在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

  1. 汽车只能沿网格边行驶,装满油后能行驶 K 条网格边。出发时汽车已装满油,在起点与终点处不设油库。
  2. 汽车经过一条网格边时,若其 X 坐标或 Y 坐标减小,则应付费用 BB ,否则免付费用。
  3. 汽车在行驶过程中遇油库则应加满油并付加油费用 A。
  4. 在需要时可在网格点处增设油库,并付增设油库费用 CC(不含加油费用AA )。
  5. N,K,A,B,C均为正整数, 且满足约束: 2≤N≤100,2≤K≤10。

设计一个算法,求出汽车从起点出发到达终点所付的最小费用。

算法描述

首先尝试标准动态规划算法

定义dp数组:dp[i][j][k]

dp[x][y][0]表示从(1,1)到(x,y)所需最少费用。
dp[x][y][1]表示从汽车行驶到(x,y)还能行驶的网格边数。
最终即求dp[N][N][0]

过程分析:
1.比如现在到了(x,y),上个位置有4种可能:左上右下(考虑越界的情况,有时候小于4),这四个位置都对应一个费用;
2.比如先选择上个位置是a,现在再去考虑当前位置(到油站否,有没有有油),并加上相应的价格;
3.此时得到一种可能下的(x,y)处费用;
4.我们遍历4个位置,寻找到(x,y)处的最小费用即可。

base case:

dp[1][1][0] = 0
dp[1][1][1] = K

递推关系式:

从上个位置到达(x,y),"上个位置"有四种情况。
dp[x][y][0] = min{dp[x+si][y+si][0]},0≤i≤3
dp[x][y][1] = dp[x+si][y+si] - 1
若(x,y)是油库:
dp[x][y][0] += A
dp[x][y][1] = K
若(x,y)是不是油库,但是此时没有油了dp[x][y][1]=0
dp[x][y][0] += A+C
dp[x][y][1] = K
其中si数组表示四个方向的信息:
s={{1,0,B},{0,1,B},{-1,0,0},{0,-1,0}

动态规划的关键代码:

		//cost[i][j][0]从(1,1)走到(i,j)的最小花费
        //cost[i][j][1]走到(i,j)之后的剩余步数
        int[][][] cost = new int[N + 1][N + 1][2];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cost[i][j][0] = Integer.MAX_VALUE / 4;
                cost[i][j][1] = K;
            }
        }
        cost[1][1][0] = 0;
        int[][] s = {
                {-1, 0, 0},
                {0, -1, 0},
                {1, 0, B},
                {0, 1, B}
        };
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                if (x == 1 && y == 1) {
                    continue;
                }
                int minCost = Integer.MAX_VALUE / 4;
                int remainStep = 0;
                int tempCost, tempStep;
                for (int i = 0; i < 3; i++) {
                    //越界
                    if (x + s[i][0] < 1 || x + s[i][0] > N || y + s[i][1] < 1 || y + s[i][1] > N) {
                        continue;
                    }
                    //对于回退的情况,tempCost为无穷大,在之后的比较中被忽略
                    tempCost = cost[x + s[i][0]][y + s[i][1]][0] + s[i][2];
                    tempStep = cost[x + s[i][0]][y + s[i][1]][1] - 1;
                    if (a[x][y] == 1) {
                        //遇加油站必须加油
                        tempCost += A;
                        tempStep = K;
                    } else if (tempStep == 0 && (x != N || y != N)) {
                        //走不动了必须建加油站
                        tempCost += C + A;
                        tempStep = K;
                    }
                    if (tempCost < minCost) {
                        minCost = tempCost;
                        remainStep = tempStep;
                    } else if (tempCost == minCost) {
                        if (remainStep < tempStep) {
                            remainStep = tempStep;
                        }
                    }
                    if (cost[x][y][0] > minCost) {
                        cost[x][y][0] = minCost;
                        cost[x][y][1] = remainStep;
                    }
                }
            }
        }
        return cost[N][N][0];

算法时间复杂度\(O(N^2)\),空间复杂度\(O(N^2)\),N为方形网络地图宽度

标准动态规划算法的问题:

虽然该dp算法考虑了上个位置的4种可能,但由于遍历顺序的限制,仔细分析后发现只有左边和上边的位置能为状态转移提供信息,也就是说标准动态规划无法包含回退的情况,所得出的结果是局部最优解,类似于贪心算法的结果。

再考虑SPFA算法

SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,是一种十分高效的最短路算法。实现方法:建立一个队列,初始时队列里只有起始点,在建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。然后执行松弛操作,用队列里有的点去刷新起始点到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

将方形网格抽象成图结构,将状态抽象成结点,将问题转换成求起点(1,1,K)到(N,N,k)的最短路径。SPFA算法在负权重图也能适用。SPFA算法能让一个结点多次入队,只要该结点的最小花费被更新,就将它入队,重新衡量该结点邻居的最小花费。

cost[x][y][k]表示从起点到(i,j)所剩余步数为k的情况下所花费的最小费用
visited[x][y][k]表示由x,y,z所决定的状态是否已经位于队列中

由a[x][y]的值去处理加油或者建造加油厂的逻辑,对于能更新最小花费的状态就入队

然后处理上一个位置的4种可能,对于能更新最小花费的状态也入队

关键代码

 		int[][] s = {
                {-1, 0, B},
                {0, -1, B},
                {1, 0, 0},
                {0, 1, 0}
        };
		Pair pair1 = new Pair(1, 1, K);
        //cost[i][j][k]表示从起点到(i,j)所剩余步数为k的情况下所花费的最小费用
        queue.offer(pair1);
        cost[1][1][K] = 0;
        visited[1][1][K] = 1;

        while (!queue.isEmpty()) {
            pair1 = queue.poll();
            int x = pair1.x;
            int y = pair1.y;
            int k = pair1.step;
            visited[x][y][k] = 0;

            //需要加油
            if (a[x][y] == 1 && k != K) {
                if (cost[x][y][K] > cost[x][y][k] + A) {
                    cost[x][y][K] = cost[x][y][k] + A;
                    if (visited[x][y][K] == 0) {
                        visited[x][y][K] = 1;
                        queue.offer(new Pair(x, y, K));
                    }
                }
                continue;
            } else {
                //建造加油厂
                if (cost[x][y][K] > cost[x][y][k] + A + C) {
                    cost[x][y][K] = cost[x][y][k] + A + C;
                    if (visited[x][y][K] == 0) {
                        visited[x][y][K] = 1;
                        queue.offer(new Pair(x, y, K));
                    }
                }
            }
            if (k > 0) {
                for (int i = 0; i < 4; i++) {
                    int nx = x + s[i][0];
                    int ny = y + s[i][1];
                    //越界
                    if (nx < 1 || nx > N || ny < 1 || ny > N) {
                        continue;
                    }
                    if (cost[nx][ny][k - 1] > cost[x][y][k] + s[i][2]) {
                        cost[nx][ny][k - 1] = cost[x][y][k] + s[i][2];
                        if (visited[nx][ny][k - 1] == 0) {
                            visited[nx][ny][k - 1] = 1;
                            queue.offer(new Pair(nx, ny, k - 1));
                        }
                    }
                }
            }
        }

结果分析

输入:

9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

输出:12

输入:

9 2 4 3 6
0 0 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 1
1 0 0 1 0 1 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
0 0 0 1 0 0 1 1 0
0 1 0 0 0 0 0 0 0

输出:38

由于SPFA算法本质上依然被认为是Bellman-Ford算法的一个特例,SPFA算法的最差复杂度依然被认为是\(O(VE)\),其中\(E\)为边数,\(V\)为点数。该网格所抽象出的边数为\(4N^2\),所抽象出的点数为\(N^2\),所以算法最差时间复杂度\(O(N^4)\),空间复杂度\(O(N^2)\),N为方形网络地图宽度

这篇关于算法设计与分析:动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!