#LyX 2.0 created this file. For more info see http://www.lyx.org/

\lyxformat 413

\begin_document

\begin_header

\textclass scrartcl

\begin_preamble

\usepackage{datetime}

\renewcommand{\dateseparator}{-}

\usepackage[BoldFont,SlantFont,CJKsetspaces,CJKchecksingle]{xeCJK}

\setCJKmainfont[BoldFont=STSong,ItalicFont=STKaiti]{STSong}

\setCJKsansfont[BoldFont=STHeiti]{STHeiti}

\setCJKmonofont{STFangsong}

\parindent 2em

\end_preamble

\use_default_options true

\maintain_unincluded_children false

\language chinese-simplified

\language_package default

\inputencoding auto

\fontencoding global

\font_roman default

\font_sans default

\font_typewriter default

\font_default_family default

\use_non_tex_fonts true

\font_sc false

\font_osf false

\font_sf_scale 100

\font_tt_scale 100

\graphics none

\default_output_format default

\output_sync 0

\bibtex_command default

\index_command default

\paperfontsize default

\spacing single

\use_hyperref true

\pdf_title "背包问题九讲"

\pdf_author "崔添翼"

\pdf_bookmarks true

\pdf_bookmarksnumbered true

\pdf_bookmarksopen true

\pdf_bookmarksopenlevel 2

\pdf_breaklinks true

\pdf_pdfborder true

\pdf_colorlinks true

\pdf_backref section

\pdf_pdfusetitle true

\papersize a4paper

\use_geometry false

\use_amsmath 1

\use_esint 1

\use_mhchem 1

\use_mathdots 1

\cite_engine basic

\use_bibtopic false

\use_indices false

\paperorientation portrait

\suppress_date false

\use_refstyle 1

\index Index

\shortcut idx

\color #008000

\end_index

\secnumdepth 3

\tocdepth 3

\paragraph_separation indent

\paragraph_indentation default

\quotes_language english

\papercolumns 1

\papersides 1

\paperpagestyle default

\tracking_changes false

\output_changes false

\html_math_output 0

\html_css_as_file 0

\html_be_strict false

\end_header

\begin_body

\begin_layout Title

寻寻觅觅∙道阻且长

\begin_inset Newline newline

\end_inset

动态规划与寻路问题

\begin_inset Newline newline

\end_inset

v0.3 preview

\end_layout

\begin_layout Author

崔添翼 (Tianyi Cui)

\begin_inset Foot

status open

\begin_layout Plain Layout

a.k.a.

dd_engi

\end_layout

\end_inset

\end_layout

\begin_layout Date

\begin_inset ERT

status open

\begin_layout Plain Layout

\backslash

yyyymmdddate

\backslash

today

\end_layout

\end_inset

\begin_inset Foot

status open

\begin_layout Plain Layout

Build

\begin_inset ERT

status open

\begin_layout Plain Layout

\backslash

pdfdate

\end_layout

\end_inset

\end_layout

\end_inset

\end_layout

\begin_layout Standard

本文题为《寻寻觅觅∙道阻且长》，副题为《动态规划与寻路问题》，从属于《动态规划的思考艺术》系列。

\end_layout

\begin_layout Standard

本文的修订历史及最新版本请访问

\begin_inset CommandInset href

LatexCommand href

target "https://github.com/tianyicui/DP-Book"

\end_inset

查阅。

\end_layout

\begin_layout Standard

本文版权归原作者所有，采用

\begin_inset CommandInset href

LatexCommand href

name "CC BY-NC-SA"

target "http://creativecommons.org/licenses/by-nc-sa/3.0/"

\end_inset

协议发布。

\end_layout

\begin_layout Standard

本文的这个版本并未公开发布，只由作者直接发布给若干试读者，试读者没有传播给别人的权利。若你并非作者指定的试读者，而通过其它途径读到本文，则说明存在至少一位试读者

未尽保密义务。

\end_layout

\begin_layout Standard

\begin_inset CommandInset toc

LatexCommand tableofcontents

\end_inset

\end_layout

\begin_layout Section

寻路问题导引

\end_layout

\begin_layout Standard

本文所探讨的寻路问题是指：给定某个可抽象为图论中的模型的图，要求找到图中满足某种性质的一条路径。除判别存在性之外，一般均要求此条路径具备某种最优性，亦即在某种计

算方法下最短或最长。对于路径的起点和终点也常常有着限制。

\end_layout

\begin_layout Standard

寻路问题一般都是最优化问题，这一点上与动态规划是一致的。所以说，很多寻路类型的题目都可用动态规划解答，图论中的Dijkstra算法（见

\begin_inset CommandInset ref

LatexCommand ref

reference "sub:Dijkstra算法"

\end_inset

）、Floyd算法（见

\begin_inset CommandInset ref

LatexCommand ref

reference "sub:全图寻路的Floyd算法"

\end_inset

）都是动态规划在图论中的经典应用。

\end_layout

\begin_layout Standard

另一方面，很多原本不存在图论模型的动态规划题目，也可转化成或建立起图论模型，并利用图论中的寻路算法进行解答。例如完全背包问题（TODO：引用《背包问题九讲》的相

应章节），就可转化为图论模型：容量为

\begin_inset Formula $V$

\end_inset

的背包转化为编号从

\begin_inset Formula $0$

\end_inset

到

\begin_inset Formula $V$

\end_inset

的点，每个费用为

\begin_inset Formula $v_{i}$

\end_inset

、价值为

\begin_inset Formula $w_{i}$

\end_inset

的物品转化为

\begin_inset Formula $V-v_{i}+1$

\end_inset

条从

\begin_inset Formula $k+v_{i}$

\end_inset

到

\begin_inset Formula $k$

\end_inset

的长度为

\begin_inset Formula $w_{i}$

\end_inset

的边（

\begin_inset Formula $0\leq k\le V-v_{i}$

\end_inset

）。而找到一组最优解则对应为找到这个有向无环图中点

\begin_inset Formula $V$

\end_inset

到点

\begin_inset Formula $0$

\end_inset

的一条最长路（具体算法见

\begin_inset CommandInset ref

LatexCommand ref

reference "sub:有向无环图中的寻路"

\end_inset

）。

\end_layout

\begin_layout Standard

综上，寻路问题与动态规划有着千丝万缕的联系。本文后面的部分便着重探讨这种联系衍生出的千变万化的动态规划题目与解法。

\end_layout

\begin_layout Section

特殊图中的寻路

\end_layout

\begin_layout Subsection

\begin_inset CommandInset label

LatexCommand label

name "sub:矩阵中的寻路"

\end_inset

矩阵中的寻路

\end_layout

\begin_layout Subsubsection

基础问题

\end_layout

\begin_layout Standard

问题是这样的：设有一

\begin_inset Formula $M\times N$

\end_inset

的矩阵

\begin_inset Formula $P$

\end_inset

，矩阵单元格中的元素皆是数字。从矩阵的左上角走到右下角，只能向右或向下走，怎样能使覆盖到的数字之和最大？（TODO：配图？）

\end_layout

\begin_layout Standard

\begin_inset Formula $M\times N$

\end_inset

的矩阵从左上走到右下，需要走

\begin_inset Formula $M+N-2$

\end_inset

步，其中向下走

\begin_inset Formula $M-1$

\end_inset

步，向右走

\begin_inset Formula $N-1$

\end_inset

步，故可能的方案数共有

\begin_inset Formula $\left(\begin{array}{c}

M-1\\

M+N-2

\end{array}\right)$

\end_inset

种。用搜索穷举所有方案的时间复杂度太高，考虑使用动态规划算法。

\end_layout

\begin_layout Standard

动态规划算法的一个典型思考方式是“只想一步”。以这道题目为例来说明，尽管要求做出的是

\begin_inset Formula $M+N-2$

\end_inset

个向右或者向下的指令，我们不妨想想：知道了什么信息，就可以得出第一步应该怎么走。

\end_layout

\begin_layout Standard

第一步有两种走法，向右走从

\begin_inset Formula $(0,0)$

\end_inset

走到

\begin_inset Formula $(0,1)$

\end_inset

，或者向下走从

\begin_inset Formula $(0,0)$

\end_inset

走到

\begin_inset Formula $(1,0)$

\end_inset

，二者的分野不仅存在于这一步覆盖到的数字不同，也体现在今后可选择的策略不同。例如若第一步向右走则左边第一列的数字再也无法拿到。

\end_layout

\begin_layout Standard

如何才能判别从

\begin_inset Formula $(0,0)$

\end_inset

到

\begin_inset Formula $(M-1,N-1)$

\end_inset

的路途中第一步怎么走呢？怎样比较第一步的两种走法的优劣呢？很简单，这一方面取决于

\begin_inset Formula $\text{(0,1)}$

\end_inset

和

\begin_inset Formula $\text{(1,0)}$

\end_inset

上面的数字，另一方面也取决于，从这两点出发，走到终点的过程中还会覆盖哪些数字，可能覆盖的最大的数字之和是多少。

\end_layout

\begin_layout Standard

于是这样抽象出动态规划的子问题：

\end_layout

\begin_layout Standard

设

\begin_inset Formula $F[i,j]$

\end_inset

表示从

\begin_inset Formula $(i,j)$

\end_inset

出发，走到

\begin_inset Formula $(M-1,N-1)$

\end_inset

，可以覆盖到的数字之和的最大值，需求解的原问题既是

\begin_inset Formula $F[0,0]$

\end_inset

，边界条件是

\begin_inset Formula $F[M-1,N-1]=P_{M-1,N-1}$

\end_inset

，状态转移方程是：

\end_layout

\begin_layout Standard

\begin_inset Formula

\[

F[i,j]=P_{i,j}+\mathrm{max}\left\{ \begin{array}{c}

F[i,j+1]\:\mathbf{if}\: j+1<N\\

F[i+1,j]\:\mathbf{if}\: i+1<M

\end{array}\right\}

\]

\end_inset

\end_layout

\begin_layout Standard

若将此方程以记忆化递归的方法实现，伪代码如下：

\end_layout

\begin_layout LyX-Code

def

\begin_inset Formula $\mathsf{MatrixWalkRec}$

\end_inset

(

\begin_inset Formula $F$

\end_inset

,

\begin_inset Formula $i$

\end_inset

,

\begin_inset Formula $j$

\end_inset

)

\end_layout

\begin_layout LyX-Code

if

\begin_inset Formula $i\geq M$

\end_inset

or

\begin_inset Formula $j\geq N$

\end_inset

\end_layout

\begin_layout LyX-Code

return

\begin_inset Formula $0$

\end_inset

\end_layout

\begin_layout LyX-Code

if

\begin_inset Formula $F[i,j]=undefined$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[i,j]\,\leftarrow P_{i,j}$

\end_inset

+ max(

\begin_inset Formula $\mathsf{MatrixWalkRec}$

\end_inset

(

\begin_inset Formula $F$

\end_inset

,

\begin_inset Formula $i$

\end_inset

,

\begin_inset Formula $j+1$

\end_inset

),

\family roman

\series medium

\shape up

\size normal

\emph off

\bar no

\strikeout off

\uuline off

\uwave off

\noun off

\color none

\lang english

\begin_inset Formula $\mathsf{MatrixWalkRec}$

\end_inset

(

\begin_inset Formula $F$

\end_inset

,

\begin_inset Formula $i+1$

\end_inset

,

\begin_inset Formula $j$

\end_inset

))

\end_layout

\begin_layout LyX-Code

return

\begin_inset Formula $F[i,j]$

\end_inset

\end_layout

\begin_layout Standard

刚才应用了“只想一步”的方法，成功地解决了这道题目如何划分子问题、如何写出状态转移方程的问题。美中不足的是，上面给出的自然的实现是递归的实现。怎样将递归的状态转

移方程实现成非递归的程序呢？

\end_layout

\begin_layout Standard

这就需要对我们的状态转移方程所决定的状态之间的相互关系进行分析。我们看到，每个状态

\begin_inset Formula $(i,j)$

\end_inset

依赖于它右方和下方的

\begin_inset Formula $(i+1,j)$

\end_inset

和

\begin_inset Formula $(i,j+1)$

\end_inset

，非递归的实现的实质是要确定一种合适的状态的求解顺序，保证任何状态的求解都在其依赖的状态之求解完成之后才开始。一种合适的顺序是：从下到上，从右至左。伪代码如下：

\end_layout

\begin_layout LyX-Code

def

\begin_inset Formula $\mathsf{MatrixWalk}$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[0\ldots M,N]\,\leftarrow0$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[M,0\ldots N]\,\leftarrow0$

\end_inset

\end_layout

\begin_layout LyX-Code

for

\begin_inset Formula $i\,\leftarrow M-1$

\end_inset

to

\begin_inset Formula $0$

\end_inset

\end_layout

\begin_layout LyX-Code

for

\begin_inset Formula $j\,\leftarrow N-1$

\end_inset

to

\begin_inset Formula $0$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[i,j]\,\leftarrow P_{i,j}+\mathrm{max}(F[i,j+1],F[i+1,j]$

\end_inset

\end_layout

\begin_layout Standard

至此，本问题的动态规划解法分析完毕。留一个问题让读者思考：前面利用“只想一步”的思考方式时，想的是“第一步应该怎么走”，如果考虑的角度变成“最后一步应该怎么走”

，会导出怎样的子问题定义、状态转移方程以及伪代码实现呢？

\end_layout

\begin_layout Subsubsection

变形问题

\end_layout

\begin_layout Standard

第一种变形问题是：改变计算权值的方法。

\end_layout

\begin_layout Standard

例如，将求最大值改成最小值，将求和的加法运算改成乘法，将矩阵单元格中的值由实数改成向量，等等⋯⋯

\end_layout

\begin_layout Standard

一般而言，这种变形问题只需对状态转移方程进行一些微调就可以。

\end_layout

\begin_layout Standard

但要注意的是，子问题的局部最优性是否还代表着全局最优性。例如，将问题中的“数字之和最大”改成“数字之积最大”之后，还按照上文中“如何踏出第一步”的方法思考时，假

如说

\begin_inset Formula $(0,0)$

\end_inset

中的数字是个负数，那么接下来向右走及向下走之后要解决的子问题就不是求“数字之积最大”而是希望求得一个“积是负数且绝对值最大”的子路径。

\end_layout

\begin_layout Standard

也就是说，将“和”改成“积”后，对于每个子问题

\begin_inset Formula $(i,j)$

\end_inset

，需要运算及记录的是两个值：一个是路径上数字之积的可能的最大值

\begin_inset Formula $F[i,j]$

\end_inset

，一个是可能的最小值

\begin_inset Formula $G[i,j]$

\end_inset

（或称绝对值最大的负值）。

\end_layout

\begin_layout Standard

这个变形问题的伪代码及其实现强烈建议读者尝试一下。

\end_layout

\begin_layout Standard

（TODO：是否在这里给出伪代码呢？）

\end_layout

\begin_layout Standard

第二种变形问题是：改变路径的可行性。

\end_layout

\begin_layout Standard

在原问题中，所有

\begin_inset Formula $\left(\begin{array}{c}

M-1\\

M+N-2

\end{array}\right)$

\end_inset

种路径都是可行的，但我们可以人为设置一些限制条件。例如，设置一些单元格为禁止通行的单元格。或设置一些单元格之间的边界为禁止通过的边界。或设置通过单元格或单元格之

间的边界时必须满足某种条件。这样的限制条件并不会更改状态转移方程的形式，只不过可以转移到的状态要在程序中根据题义进行判断，这种判断可以设计得相当复杂。

\end_layout

\begin_layout Standard

给一个这种变形的例题：单元格之间有可能存在锁着的门，打开一扇门必须耗费一把钥匙，不同的门需要的钥匙的种类不同，单元格中可能会捡到钥匙；问题仍然是求解最优的路径。

\end_layout

\begin_layout Standard

这道例题的求解，需要在状态转移方程中增加一维来表示手中现有的钥匙种类和数量。然后在计算过程中根据捡到和消耗的钥匙进行状态之间的转移。

\end_layout

\begin_layout Standard

（TODO：加个示意图？）

\end_layout

\begin_layout Standard

第三种变形问题是：增加路径的条数。

\end_layout

\begin_layout Standard

典型问题如，要求两条从矩阵左上到右下的路径，这两条路径不可以相交（或相交后同一单元格的数值只算一次），最大化路径经过的权值和。

\end_layout

\begin_layout Standard

这种题目可以以两条路径所经过的单元格距左上单元格的距离划分阶段，以两条路径所经过的单元格坐标做为状态，列出状态转移方程。

\end_layout

\begin_layout Standard

（TODO：方程其实写出来很难看，不如写程序代码附录进去。）

\end_layout

\begin_layout Standard

以上说明了矩阵中寻路问题的三种变形问题的方向，在实际中，将这道基础的动态规划题目经由多个方向同时变形，就可以构造出看似很复杂的题目。

\end_layout

\begin_layout Standard

（TODO：还有什么变形问题的种类吗？）

\end_layout

\begin_layout Subsection

\begin_inset CommandInset label

LatexCommand label

name "sub:有向无环图中的寻路"

\end_inset

有向无环图中的寻路

\end_layout

\begin_layout Subsubsection

\begin_inset CommandInset label

LatexCommand label

name "sub:从矩阵寻路到有向无环图"

\end_inset

从矩阵寻路到有向无环图

\end_layout

\begin_layout Standard

在上一节

\begin_inset CommandInset ref

LatexCommand ref

reference "sub:矩阵中的寻路"

\end_inset

中，我们给出的基础问题及其所有变形问题都有一个共同点：要求找到从左上角到右下角的一条路径，且只能向相邻的右方、下方的单元格走。

\end_layout

\begin_layout Standard

这个限制条件给所有的单元格排了个顺序，亦即，单元格

\begin_inset Formula $(i+p,j+q)$

\end_inset

和

\begin_inset Formula $(i,j)$

\end_inset

若均在路径中出现，

\begin_inset Formula $(i+p,j+q)$

\end_inset

一定出现在

\begin_inset Formula $(i,j)$

\end_inset

之后（

\begin_inset Formula $p\geq0,q\geq0,p+q>0$

\end_inset

）。这个顺序决定了我们把动态规划的状态的表示确定为单元格的坐标时，状态之间的依赖关系是很明晰的，状态的求解顺序也不是个难题。

\end_layout

\begin_layout Standard

我们来看一道没有这个只能向右、下走的限制条件的例题

\begin_inset Foot

status open

\begin_layout Plain Layout

PKU 1088

\end_layout

\end_inset

：

\end_layout

\begin_layout Standard

仍然是

\begin_inset Formula $M\times N$

\end_inset

的数字矩阵

\begin_inset Formula $P$

\end_inset

，要求寻找的路径可以从任意一点出发，可以向上、下、左、右任意方向延伸，但路径经过的数字必须越来越小、单调递减。求矩阵中存在的最长的满足要求的路径。

\end_layout

\begin_layout Standard

去掉了仅能向右、下走及固定起点、终点的限制条件，加上了一个路径中数字单调递减的限制条件。这里还是利用“只想一步”的方法来思考。路径的起点在哪里？不知道，设为

\begin_inset Formula $(i,j)$

\end_inset

。路径的第一步往哪儿走？往哪里走能走得更远就往哪里走。于是状态转移方程是：

\end_layout

\begin_layout Standard

\begin_inset Formula

\[

F[i,j]=1+\mathrm{max}\left\{ \begin{array}{c}

0\\

F[i,j-1]\text{ if }P_{i,j-1}<P_{i,j}\\

F[i,j+1]\text{ if }P_{i,j+1}<P_{i,j}\\

F[i-1,j]\text{ if }P_{i-1,j}<P_{i,j}\\

F[i+1,j]\text{ if }P_{i+1,j}<P_{i,j}

\end{array}\right\}

\]

\end_inset

\end_layout

\begin_layout Standard

考察这个状态转移方程所隐含的状态之间的依赖关系：一个状态的计算有可能依赖于它上下左右的任意一个状态，这看上去很可能存在状态间的循环依赖以至于状态转移方程无法被求

解。但实际上，一个状态只依赖于其上下左右的单元格中元素数值比自身小的那些。换句话说，若将所有的单元格按照其中元素从小到大的顺序排个序，并按这个顺序求解状态的话，

则只会有后面的状态依赖于前面的状态，不会出现求解某一状态时它所依赖的状态还未解出的可能。下面给出伪代码：

\end_layout

\begin_layout LyX-Code

def

\begin_inset Formula $\mathsf{MatrixDecPath}$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[0\ldots M+1,0\ldots N+1]\,\leftarrow0$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $Q\,\leftarrow\left[(P_{i,j},i,j)\:|\:\text{for }i,j\text{ in }(1\ldots M,1\ldots N)\right]$

\end_inset

\end_layout

\begin_layout LyX-Code

sort

\begin_inset Formula $Q$

\end_inset

\end_layout

\begin_layout LyX-Code

for

\begin_inset Formula $p,i,j$

\end_inset

in

\begin_inset Formula $Q$

\end_inset

\begin_inset Formula $ $

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $d\,\leftarrow[(0,-1),(0,+1),(-1,0),(+1,0)]$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $ $

\end_inset

for

\begin_inset Formula $k\,\leftarrow0$

\end_inset

to

\begin_inset Formula $3$

\end_inset

\end_layout

\begin_layout LyX-Code

if

\begin_inset Formula $P_{i+d[k].x,j+d[k].y}<P_{i,j}$

\end_inset

\end_layout

\begin_layout LyX-Code

\begin_inset Formula $F[i,j]\,\leftarrow\mathrm{max}\{F[i,j],1+F[i+d[k].x,j+d[k].y]\}$

\end_inset

\end_layout

\begin_layout Standard

最后的答案就是

\begin_inset Formula $F[1\ldots M,1\ldots N]$

\end_inset

中的最大值。

\end_layout

\begin_layout Standard

值得指出的是，以上给出的非递归的伪代码在理解和实现上均略有些麻烦。在看清了状态的求解不存在循环依赖的时候，就可以不用排序，而直接用记忆化递归的方法（TODO：引

用MatrixWalkRec）实现。

\end_layout

\begin_layout Subsubsection

有向无环图的拓扑排序

\end_layout

\begin_layout Standard

上一节（

\begin_inset CommandInset ref

LatexCommand ref

reference "sub:从矩阵寻路到有向无环图"

\end_inset

）引入的新问题中，在矩阵中寻找的路径可以是任意的，不仅仅局限于从左上到右下的不准绕远路的那一种路径。命题者需要寻找的最佳路径，可以根据数据具有任意的形状。但有一

点值得注意，不管路径走成何种形状，都不可能存在一条数字单调递减的路径与自身交叉。换句话说，这个“单调递减”的条件，保证了作为寻路结果的路径中不可能存在环，导致了

动态规划的状态转移中不可能出现循环依赖，决定了这道题目可以用动态规划来解。

\end_layout

\begin_layout Standard

用图论的术语来说明，不管是只能向右、向下移动的矩阵，还是经过数字单调递减的矩阵，抽象成图论中图的模型之后，都是有向无环图。有向无环图的最重要性质就是，其中的定点

可以进行拓扑排序。

\end_layout

\begin_layout Standard

下面从数学中“关系”的角度诠释一下有向无环图的拓扑排序。

\end_layout

\begin_layout Standard

数学中定义的二元关系

\begin_inset Formula $R$

\end_inset

，是指任意的有序对的集合。若

\begin_inset Formula $R\subseteq X\times Y$

\end_inset

，则用

\begin_inset Formula $xRy$

\end_inset

表明

\begin_inset Formula $x$

\end_inset

与

\begin_inset Formula $y$

\end_inset

之间存在关系

\begin_inset Formula $R$

\end_inset

，有

\begin_inset Formula $\text{x\in X,y\in Y,(x,y)\in R}$

\end_inset

。常见的一种二元关系即是“函数”，函数的特点是，定义域中的一个值，对应于值域中的唯一一个值。而在一般的关系中则没有这样的限制。

\end_layout

\begin_layout Standard

有一类特殊的关系叫做严格偏序关系，其定义是：满足反自反、反对称、传递的关系。反自反的意思是说，任何元素和自己都不存在关系，

\begin_inset Formula $\forall x\:(x,x)\notin R$

\end_inset