局部后效性的处理

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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