算法动态规划

局部后效性的处理

字数统计: 1.7k字   |   阅读时长: 8分
, ,

摘要: 有后效性：状态之间互相转移，互相影响。无法确定合适的阶段。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$0 有后效性问题的背景

阶段是 DP 的三要素之一，无后效性是 DP 算法有效的三个前提之一。参考 动态规划概念和基础线性DP

在一些问题中，抽象出状态维度，并设计出状态表示和状态转移方程后，可能会发现这样的状态设计不满足无后效性，部分状态之间互相转移，互相影响，构成了环形。

对于环形问题，有一种【可拆解的环形问题】，这样的问题是可以拆环后转化成线性结构上的 DP 问题，参考： 环形DP 。

而对于有后效性的这种环形，是无法拆解的，无法确定出一个合适的阶段，使得状态总是沿着某个方式执行递推。

$1 有后效性问题的处理方式

场景1 (高斯消元)

可以将 DP 的各个状态看做未知量，状态的转移看做若干个方程，如果仅仅是无后效性无法满足，并且状态转移方程都是一次方程，那么可以不进行线性递推，而是用高斯消元直接求出状态转移方程的解。

场景2 (递推 + 高斯消元)

状态转移分阶段带环。把 DP 和高斯消元相结合，在整体上用 DP 的框架，在局部上用高斯消元接触互相影响的状态。

$2 题目

给定一张 N * M 的棋盘，有一个机器人处于(x,y)位置。

这个机器人可以进行很多轮行动，每次等概率地随机选择停在原地、向左移动一格、向右移动一格或向下移动一格。

当然机器人不能移出棋盘。

求机器人从起点走到最后一行的任意一个位置上，所需行动次数的数学期望值。

算法：期望DP

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][j] := (i, j) 到最后一行所需步数的期望值

初始化
dp[N][1..M] = 0

答案
dp[x][y]

转移
dp[i][1] = 1/3 * (dp[i][1] + dp[i][2] + dp[i + 1][1]) + 1
dp[i][M] = 1/3 * (dp[i][M] + dp[i][M - 1] + dp[i + 1][M]) + 1
2 <= j <= M 时
dp[i][j] = 1/4 * (dp[i][j] + dp[i][j - 1] + dp[i][j + 1] + dp[i + 1][j]) + 1

这是分阶段带环的问题。其中 i 这一维只能从 i 转移到 i + 1，因此 i 满足无后效性，而 j 可以转移到 j - 1，j + 1，可以互相转移无法确定递推顺序。

(1) DP 部分

以 i 为阶段，枚举 i = M, M-1, ..., x，求第 i 行每个位置 j 走向最后一行所需行动次数的数学期望。

(2) 高斯消元部分

求 dp[i][1...M] 时，dp[i+1][1..M] 为已知数。dp[i][1], ..., dp[i][M] 共 M 个未知数。

每个位置一个方程共 M 个方程。可以用高斯消元求 dp[i][1..M]

系数矩阵除主对角线和主对角线两侧的斜线，其余位置为零。这样每行只有 2 到 3 个位置需要相减。

M = 1 需要特判。

代码 (DP 套高斯消元)

高斯消元 $O(M^{2})$，总 $O(NM^{2})$ 超时。

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
80
81
#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

const double EPS = 1e-8;

void gaussian_elimination(vector<vector<double>>& A)
{
    int M = A.size() - 1;

    // 对增广矩阵 A 高斯消元
    for(int i = 1; i <= M; ++i)
    {
        // 第 1 行只需要消第 2 行的 A[2][1], A[2][2]
        // 第 M 行只需要消第 M - 1 行的 A[M - 1][M - 1], A[M - 1][M]
        // 第 2 <= i <= M - 1 行只需要消 i - 1 行和 i + 1 行
        for(int j = 1; j <= min(i + 1, M); ++j)
        {
            if(i == j) continue;
            double rate = A[j][i] / A[i][i];
            for(int k = i; k <= min(i + 1, M); ++k)
                A[j][k] -= rate * A[i][k];
            A[j][M + 1] -= rate * A[i][M + 1];
        }
    }
}

int main()
{
    fstream fin("./test/prob290.test");
    int N, M;
    // cin >> N >> M;
    fin >> N >> M;
    int x, y;
    // cin >> x >> y;
    fin >> x >> y;
    vector<vector<double>> dp(N + 1, vector<double>(M + 1, 0.0));
    cout << std::fixed << std::setprecision(4);
    if(M == 1)
    {
        // 特判
        for(int i = N - 1; i >= x; --i)
            dp[i][1] = dp[i + 1][1] + 2.0;
        cout << dp[x][1] << endl;
        return 0;
    }
    // M >= 2
    vector<vector<double>> A(M + 1, vector<double>(M + 2)); // 增广矩阵
    for(int i = N - 1; i >= x; --i)
    {
        // dp[i][1], dp[i][2], ..., dp[i][M] 共 M 个未知数
        // 系数矩阵为 M * M

        // 增广矩阵 A 的第一行
        A[1][1] = 2;
        A[1][2] = -1;
        A[1][M + 1] = 3 + dp[i + 1][1];
        // 增广矩阵 A 的第 M 行
        A[M][M] = 2;
        A[M][M - 1] = -1;
        A[M][M + 1] = 3 + dp[i + 1][M];
        // 增广矩阵 A 的第 2~M-1 行
        for(int l = 2; l <= M - 1; ++l)
        {
            A[l][l] = 3;
            A[l][l + 1] = -1;
            A[l][l - 1] = -1;
            A[l][M + 1] = 4 + dp[i + 1][l];
        }

        gaussian_elimination(A);

        for(int j = 1; j <= M; ++j)
            dp[i][j] = A[j][M + 1] / A[j][j];
    }

    cout << dp[x][y] << endl;
}

代码 (高斯消元优化)

系数矩阵是这样子的

先从上向下消成这样

再从下向上消成这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void gaussian_elimination(vector<vector<double>>& A)
{
    int M = A.size() - 1;

    for(int i = 1; i < M; ++i)
    {
        // 用第 i 行消第 i + 1 行
        double rate = A[i + 1][i] / A[i][i];
        for(int k = i; k <= (i + 1); ++k)
            A[i + 1][k] -= rate * A[i][k];
        A[i + 1][M + 1] -= rate * A[i][M + 1];
    }
    for(int i = M; i >= 2; --i)
    {
        // 用第 i 行消第 i - 1 行
        double rate = A[i - 1][i] / A[i][i];
        A[i - 1][i] -= rate * A[i][i];
        A[i - 1][M + 1] -= rate * A[i][M + 1];
    }
}
Share