?? 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 + -