算法动态规划

状态=阶段+附加信息；排除高维状态空间的冗余维度

字数统计: 2.5k字   |   阅读时长: 10分

摘要: 状态=阶段+附加信息，其中有冗余信息的优化方法

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

高维空间动态规划

仅把 DP 的阶段要素放到 DP 状态中有时不足以找到最优子结构，也就是不足以执行状态的转移。此时的处理方法是增加附加信息到 DP 状态的新的维度里。在文章 阶段不足表示状态：附加信息作为状态维度 中我们分析了一个例子。

对于复杂的问题，在增加附加信息之后，有可能会出现冗余信息，使得在状态推导过程中出现很多无效计算，因此我们需要在确定 DP 状态时选择最小的能覆盖整个状态空间的维度集合。

因此当 DP 状态由多个维度构成时，需要注意这些维度之间能不能互相导出，

在转移的时候，总是从一个阶段到下一个阶段，因此没必要关心附加信息维度的大小变化情况，也就是附加状态维度的推导方向不重要，无后效性已经由阶段保证。

本文我们通过一个复杂问题走一遍上述流程。有三个点需要注意：

  • 附加状态的冗余维度可以通过其它维度表示。
  • 附加状态 $(x, y)$ 的推导顺序不重要。
  • 状态计算考虑从当前状态对后续阶段的状态的贡献。

移动服务

274. 移动服务

一个公司有三个移动服务员，最初分别在位置 1，2，3 处。

如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。

某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。

从 p 到 q 移动一个员工，需要花费 c(p,q)。

这个函数不一定对称，但保证 c(p,p)=0。

给出 N 个请求，请求发生的位置分别为 p1∼pN。

公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。

1
2
3
4
5
6
7
8
9
10
11
12
输入格式
第 1 行有两个整数 L,N，其中 L 是位置数量，N 是请求数量，每个位置从 1 到 L 编号。
第 2 至 L+1 行每行包含 L 个非负整数，第 i+1 行的第 j 个数表示 c(i,j) ，并且它小于 2000。
最后一行包含 N个整数，是请求列表。
一开始三个服务员分别在位置 1，2，3。

输出格式
输出一个整数 M，表示最小花费。

数据范围
3<=L<=200,
1<=N<=1000

输入样例：
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
输出样例：
5

算法：动态规划

阶段划分

如果用动态规划对本题建模，由于需要按顺序完成需求，也就是任务之间有时间的先后顺序，因此阶段应该是按顺序已经完成的请求数量，这隐含了时间信息。

在第 $i$ 个阶段时，通过指派一名服务员（决策），从原有位置 $p$ 以一定花费 $c(p, q)$ 移动到需要请求的位置 $q$。进入下一个阶段。

附加信息

为了计算决策对答案的贡献（指派人员的花费），需要知道状态转移时每个人员的位置。这个信息是阶段提供不了的，因此需要附加信息到状态维度中。最直接的就是把三个服务员位置都塞到 DP 状态中。

状态定义为 $dp(i, x, y, z)$ 表示已经完成 $i$ 个请求，三名员工位置分别为 $x, y, z$ 时的最小花费。边界值为 $dp(0, 1, 2, 3)$，答案为 $\min\limits_{x, y, z}dp(n, x, y, z)$

考虑状态转移的时候，可以考虑如何从先前阶段的已知状态计算当前状态，也可以考虑从当前状态可以更新后续阶段的哪些状态。参考文章 由先前阶段已知状态计算当前状态；由当前状态更新后续阶段未知状态，这里比较自然的是做第二种考虑：

显然从当前阶段的状态 $dp(i, x, y, z)$ 可以更新后续阶段的三个状态，对应着三种决策，也就是指派哪个人到第 $i+1$ 个请求处。

以上三行为当前状态 $dp(i, x, y, z)$ 对三个决策对应的下一个状态的贡献，注意转移的合法性需要判断。

去掉冗余维度

注意第 $i$ 个请求完成时，一定有某个员工处于位置 $p_{i}$，因此只需要知道阶段 $i$ 和另外两个人的位置即可描述一个状态，处于 $p_{i}$ 的位置是冗余信息。

状态定义改为 $dp(i, x, y)$ 表示已经完成前 $i$ 个请求，其中一个员工位于 $p_{i}$，另外两个人处于 $x, y$ 时的最小花费。因绕考虑从当前状态可以更新后续的哪些状态：

以上三行为当前状态 $dp(i, x, y)$ 对三个决策对应的下一个状态的贡献，注意转移的合法性需要判断。三个决策的含义是让位于 $p_{i}, x, y$ 的人前往 $p_{i+1}$ 处理请求。

不妨设 $p_{0} = 3$，于是边界值为 $dp(0, 1, 2) = 0$，目标为 $\min\limits_{x,y}dp(n,x,y)$

在转移的时候，状态总是从一个阶段转移到另一个阶段，因此没必要关心附加信息维度的大小变化情况，也就是附加状态维度的推导方向不重要，无后效性已经由阶段保证。也就是在同样的 $i$ 下的 $(x, y)$，从 $(1, 1)$ 到 $(L, L)$ 的计算顺序不重要。

代码 (C++，线性递推)

注意以下要点：

  • 附加状态的冗余维度可以可以通过其它维度表示。
  • 附加状态 $(x, y)$ 的推导顺序不重要。
  • 状态计算考虑从当前状态对后续阶段的状态的贡献。 
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
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXL = 201;
const int MAXN = 1001;
int dp[MAXN][MAXL][MAXL];
int c[MAXL][MAXL];
int p[MAXN];

int main()
{
    int L, N;
    cin >> L >> N;
    for(int i = 1; i <= L; ++i)
        for(int j = 1; j <= L; ++j)
            cin >> c[i][j];
    for(int i = 1; i <= N; ++i)
        cin >> p[i];
        
    memset(dp, INF, sizeof(dp));
    
    dp[0][1][2] = 0;
    p[0] = 3;
    for(int i = 0; i < N; ++i)
    {
        // 当前请求为 p[i]
        for(int x = 1; x <= L; ++x)
        {
            for(int y = 1; y <= L; ++y)
            {
                if(x == y || y == p[i] || p[i] == x)
                    continue;
                // 当前 dp[i][x][y]，更新后续阶段的状态
                dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y] + c[p[i]][p[i + 1]]);
                dp[i + 1][p[i]][y] = min(dp[i + 1][p[i]][y], dp[i][x][y] + c[x][p[i + 1]]);
                dp[i + 1][x][p[i]] = min(dp[i + 1][x][p[i]], dp[i][x][y] + c[y][p[i + 1]]);
            }
        }
    }
    int ans = INT_MAX;
    for(int x = 1; x <= L; ++x)
    {
        for(int y = 1; y <= L; ++y)
        {
            if(x == y || y == p[N] || p[N] == x)
                continue;
            ans = min(ans, dp[N][x][y]);
        }
    }
    cout << ans << endl;
}

代码 (C++，记忆化搜索)

两个要点：

  • 每一层递归函数表示一个阶段。因此同一阶段的各个状态在同一轮递归函数中更新答案。
  • 记忆化搜索中考虑从当前状态可以更新后续阶段的哪些状态。
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
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXL = 201;
const int MAXN = 1001;
int dp[MAXN][MAXL][MAXL];
int c[MAXL][MAXL];
int p[MAXN];
int N, L;

void iterative(int i)
{
    // 当前阶段为 i
    if(i == N)
        return;

    for(int x = 1; x <= L; ++x)
        for(int y = 1; y <= L; ++y)
        {
            // 当前的附加信息为 p[i], x, y
            // x != y != p[i]
            if(x == y || x == p[i] || p[i] == y)
                continue;
            // 基于当前阶段的各个状态 dp[i][x][y]，更新后续阶段的状态
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y] + c[p[i]][p[i + 1]]);
            dp[i + 1][p[i]][y] = min(dp[i + 1][p[i]][y], dp[i][x][y] + c[x][p[i + 1]]);
            dp[i + 1][x][p[i]] = min(dp[i + 1][x][p[i]], dp[i][x][y] + c[y][p[i + 1]]);
        }

    // 进入下一阶段
    traverse(i + 1);
}

int main()
{
    cin >> L >> N;
    for(int i = 1; i <= L; ++i)
        for(int j = 1; j <= L; ++j)
            cin >> c[i][j];
    for(int i = 1; i <= N; ++i)
        cin >> p[i];

    memset(dp, INF, sizeof(dp));

    dp[0][1][2] = 0;
    p[0] = 3;
    iterative(0);

    int ans = INT_MAX;
    for(int x = 1; x <= L; ++x)
    {
        for(int y = 1; y <= L; ++y)
        {
            if(x == y || y == p[N] || p[N] == x)
                continue;
            ans = min(ans, dp[N][x][y]);
        }
    }
    cout << ans << endl;
}
Share