-
Notifications
You must be signed in to change notification settings - Fork 99
/
path.lyx
1761 lines (1272 loc) · 38.9 KB
/
path.lyx
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#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