【杂谈】从最短路到动态规划

· · 算法·理论

前言

本文是笔者看教练教小朋友用 DFS 做最短路的时候有感而发写出来的，所以不会涉及到很深的水准。

关于《再谈概率期望》系列：等更新吧。

引入

你是一个刚刚学完 DFS 的小蒟蒻，你碰到了一道题。很自信地，你很快写出了这道题的代码并提交。 :::error[TLE]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
struct edge
{
    int v, w;
};
vector<edge> e[100001];
vector<ll> dis;
void dfs(int u)
{
    for(auto v:e[u])
        if(dis[v.v]>dis[u]+v.w)
        {
            dis[v.v]=dis[u]+v.w;
            dfs(v.v);
        }
}
int n, m,start;
int main()
{
    cin >> n >> m>>start;
    for (int i = 0, s, t, w; i < m; i++)
    {
        cin >> s >> t >> w;
        e[s].push_back(edge{t, w});
    }
    dis=vector<ll>(n+1,(ll)INT_MAX);
    dis[start]=0;
    dfs(start);
    for(int i=1;i<dis.size();i++)
        cout<<dis[i]<<' ';
    return 0;
}

::: 为什么你过不了呢？教练明明说过 dis 数组把数据记下来了，那不就是记忆化搜索吗？

后来，你又学习了 Bellman-Ford 算法，发现其中的核心操作跟你也差不多，但为什么就你 T 呢？

从最短路到动态规划

对“引入”中问题的解答

实际上，现在大多数的 Bellman-Ford 都是经过滚动数组的版本。原版是基于 dp_{i,v}\gets \min(dp_{i,v},dp_{i-1,u}+w(u,v)) 进行状态转移的动态规划，其中 i 代表已经走过的边数，在大多数实现中已经被滚动数组的方式优化掉了。

再看到原本 DFS 的形式，对于每个点，其并没有确定所走过的路径条数，因此会重复更新一个点很多次，复杂度是指数级别的。而 Bellman-Ford 虽然也会更新多次，最多更新 n 次；Dijkstra 算法则是通过优先队列的方式牺牲维护时间并利用贪心性质保证每一个点最多更新一次。

:::info[一些补充] 事实上，直接将 Bellman-Ford SPFA 优化用优先队列，其在全正边权的情况下表现与 Dijkstra 一致，而在有负权边的情况下有可能会被卡成类似原 DFS 形式的指数级复杂度。 :::

本文中 DFS 的“记忆化”是假的“记忆化”，因为其还可能会被重新更新。真正的动态规划的“记忆化”则是通过一次算完就固定的形式，通过固定的状态给到固定的解重复利用计算结果而优化时间的。

课后作业

通过今天的学习，你已经理解了最短路和记忆化搜索、动态规划之间的联系了。

今天的作业是：完成这道题。

课后讲评在这里。

最短路与动态规划

很显然，本文不可能只有这点内容，否则就会：

观察目前所有最短路算法可以发现，其形式最后要么是以 Floyd 为代表的 DP[^dp]，要么是以 Dijkstra 为代表的贪心，最后都可以归约到 DP 上。

而 Johnson 算法比较特别，它是由 Bellman-Ford 和 Dijkstra 组合在一起而形成的；其在稠密图上劣于 Floyd，在稀疏图上显著优于 Floyd。

由此思考：为什么使用 DP 呢？

DP 有一个核心思想，那就是将求解的过程划分为一个个阶段，然后重复利用已有的结果，这个思想表现出来则分为两个原则——“最优子结构”和“无后效性”原则[^ziwenti]。

“最优子结构”保证了每个子结构必须都是最优的。“无后效性”则保证了对于相同的状态，转移时只需要认为它是一个黑箱，而不必关心状态对应的最优子结构实际是哪一个。

最短路问题则正好符合 DP 的思路。“最优子结构”正好对应了最短路要求的“最短”必须路径上的每个节点走的都是最短路径。“无后效性”则对应的是对于每个节点，不管之前走过的路径如何，其接下来能走的边、边的边权等都是一定的。

实际上的实现的不同则取决于其状态设计的不同。Bellman-Ford 的实现思路在前文已有叙述。Floyd 采取的是 f_{i,j,k} 代表只经过前 k 个点中的点由 i 到达 j 的最短路，一般实现中会将最后一维用滚动数组优化到。又因为必然存在无环的最短路（不然就没有最短路了），所以其正确性得到了保证。

Dijkstra 使用了优先队列以保证贪心的正确性，DP 形式可以写成以 f_i 代表搜完 i 个点之后的结果。

记忆化搜索

“记忆化搜索”事实上只是动态规划的递归实现形式。

因为其采用了记忆化的形式，所以不会像一般搜索一样一个状态搜很多次的指数级复杂度；而是像一般的动态规划一样的多项式级别复杂度^fuzadu。

最简单的判别方式是：如果只要一个状态已经计算过一次之后，就不需要再计算，而是调用已有的记忆，那么这个搜索就是“记忆化搜索”。

比如这段代码就是典型的记忆化搜索版的 01 背包。 :::success[代码]

int n, t;
int tcost[103], mget[103];
int mem[103][1003];

int dfs(int pos, int tleft) {
  if (mem[pos][tleft] != -1)
    return mem[pos][tleft];  // 已经访问过的状态，直接返回之前记录的值
  if (pos == n + 1) return mem[pos][tleft] = 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos])
    dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];  // 状态转移
  return mem[pos][tleft] = max(dfs1, dfs2);  // 最后将当前状态的值存下来
}

int main() {
  memset(mem, -1, sizeof(mem));
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, t) << endl;
  return 0;
}

:::

而引入中的程序，虽然使用了 dis 数组记录路径，但因为一个点搜索过后可能再度进行搜索，所以不满足记忆化搜索的条件。

再来看这段代码，请问它属于记忆化搜索吗？ :::info[小木棍]

bool dfs
(int rest/*还剩多少根*/,
int now/*现在拼了多少*/,
int len/*总长*/,
int max_can_used/*现在可以用的最长木棍*/)
{
    if(!rest)
    {
        ans=len;
        return true;
    }//成功
    if(now==len)
    {
        return dfs(rest-1,0,len,max_stick);
    }
    for(int /*长一点的木棍试过了，行就不会回溯了*/i=max_can_used;i>=min_stick;i--)
    {
        if(a_bucket[i]&&now+i<=len/*还剩，拼上去不会超*/)
        {
            a_bucket[i]--;
            if(dfs(rest,now+i,len,i))
            {
                a_bucket[i]++;
                return true;
            }//从最大的开始看行不行
            a_bucket[i]++;
            if(now+i==len||now==0)
                break;//拼新木棍或者拼完木棍都不行，肯定是前面错了
        }
    }
    return false;
}

::: :::warning[请自行思考后再查看答案] 不是。

上述代码中，相同的给定数据下并没有采取记忆化的形式，并且最后是在递归的底层得出的答案。 :::

尾声

虽然本文只涉及了浅显的最短路和动态规划的内容，但即使是这些简单的内容，也是无数前辈从零开始推出来的。

这些算法看上去简单，但放在 66 年前，其可能就是最前沿的科研成果。不要因为自己学会的看似比别人多就看不起这些“简单”的成果。

在这里引用《【杂谈】隔行如隔山：如何正确看待算法竞赛与软件工程》中的一句话：

真正的强者，从不吝啬对他人的尊重，也从不随意在自己未知的领域指手画脚。

愿我们在追求技术的道路上，少一些 CleanIce 式的傲慢，少一些“李老师”式的笑话，多一份对技术本身的敬畏。

考古成果

  1. 崔泽禹，《再谈动态规划的正确打开方式：从记忆化搜索到动态规划》
  2. litjohn，《基础的搜索优化技巧》
  3. xhhkwy（用户不可见），《SPFA算法的玄学方法》
  4. interestingLSY，《聊聊动态规划与记忆化搜索》

    创作声明

    本文遵循 CC BY-SA 4.0 协议。

作者保证未使用 AI 工具进行创作。

更新日志

[^dp]:Dynamic Programming，简称 DP，中文译名动态规划，可见动态规划基础，本文中可能会多种名字混用。 [^ziwenti]:如果需要使用 DP 优化时间复杂度，还需要“子问题重叠”的性质，但一般想出了 DP 做法这种性质不需要再单独构造。