📄 no33.htm
字号:
mso-font-pitch:fixed; mso-font-signature:1 134742016 16 0 1048576 0;}@font-face {font-family:"MS Mincho"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:"ＭＳ 明朝"; mso-font-charset:128; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:fixed; mso-font-signature:1 134676480 16 0 131072 0;}@font-face {font-family:Gulim; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:\AD74\B9BC; mso-font-charset:129; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:fixed; mso-font-signature:1 151388160 16 0 524288 0;}@font-face {font-family:"MS Gothic"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:"ＭＳ ゴシック"; mso-font-charset:128; mso-generic-font-family:modern; mso-font-format:other; mso-font-pitch:fixed; mso-font-signature:1 134676480 16 0 131072 0;}@font-face {font-family:Century; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-charset:0; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;}@font-face {font-family:仿宋_GB2312; panose-1:2 1 6 9 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:1 135135232 16 0 262144 0;}@font-face {font-family:"\@仿宋_GB2312"; panose-1:2 1 6 9 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:1 135135232 16 0 262144 0;}@font-face {font-family:"\@宋体"; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:1 135135232 16 0 262144 0;} /* Style Definitions */p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0cm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:宋体; mso-font-kerning:1.0pt;}p.MsoFooter, li.MsoFooter, div.MsoFooter {margin:0cm; margin-bottom:.0001pt; mso-pagination:none; tab-stops:center 207.65pt right 415.3pt; layout-grid-mode:char; font-size:9.0pt; font-family:"Times New Roman"; mso-fareast-font-family:宋体; mso-font-kerning:1.0pt;}span.msoIns {mso-style-type:export-only; mso-style-name:""; text-decoration:underline; text-underline:single; color:teal;}span.msoDel {mso-style-type:export-only; mso-style-name:""; text-decoration:line-through; color:red;}span.msoChangeProp {mso-style-type:export-only; mso-style-name:""; color:black;} /* Page Definitions */@page {mso-page-border-surround-header:no; mso-page-border-surround-footer:no;}@page Section1 {size:515.95pt 728.6pt; margin:72.0pt 2.0cm 72.0pt 2.0cm; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-even-footer:url("./No33.files/header.htm") ef1; mso-footer:url("./No33.files/header.htm") f1; mso-paper-source:0;}div.Section1 {page:Section1;}--></style></head><body lang=ZH-CN style='tab-interval:21.0pt;text-justify-trim:punctuation' bgcolor="#e8ffe8"><div class=Section1><p class=MsoNormal align=left style='text-align:left;text-indent:112.0pt;mso-char-indent-count:7.0;mso-char-indent-size:16.0pt;mso-layout-grid-align:none;text-autospace:none'><span style='font-size:16.0pt;font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>第<span lang=EN-US> 3 章<spanstyle="mso-spacerun: yes"> </span>动态规划<o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:112.0pt;mso-char-indent-count:7.0;mso-char-indent-size:16.0pt;mso-layout-grid-align:none;text-autospace:none'><span lang=EN-US style='font-size:16.0pt;font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:none;text-autospace:none'><span lang=EN-US style='font-size:12.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:none;text-autospace:none'><span lang=EN-US style='font-size:12.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>3.1 </span><spanstyle='font-size:12.0pt;font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>算法思想<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:none;text-autospace:none'><span lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.1pt;mso-char-indent-count:2.0;mso-char-indent-size:10.05pt;mso-layout-grid-align:none;text-autospace:none'><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>例<span lang=EN-US>3</span></span></b><b><spanlang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-1 [</span></b><b><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>最短路经</span></b><b><span lang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>]</span></b><spanlang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'> </span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>考察图</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1 2 - 2</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中的有向图。假设要寻找一条从源节点</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>s</span></i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>到目的节点</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>d</span></i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 5</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>的最短路径，即选择此路径所经过的各个节点。第一步可选择节点</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>或</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>4</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。假设选择了节点</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，则此时所要求解的问题变成：选择一条从</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>到</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>5</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>的最短路径。如果</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>到</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>5</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>的路径不是最短的，则从</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>开始经过</span><span⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -