?? no11.htm
字號:
mso-font-charset:136; mso-generic-font-family:modern; mso-font-format:other; 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; mso-gutter-position:top;}@page Section1 {size:515.95pt 728.6pt; margin:72.0pt 2.0cm 62.35pt 2.0cm; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-even-footer:url("./No11.files/header.htm") ef1; mso-footer:url("./No11.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:96.0pt;mso-char-indent-count:6.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><span lang=EN-US style='font-size:16.0pt;mso-fareast-font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>1 </span><spanstyle='font-size:16.0pt;font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>章<spanlang=EN-US><span style="mso-spacerun: yes"> </span>貪婪算法<o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:96.0pt;mso-char-indent-count:6.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'>雖然設(shè)計一個好的求解算法更像是一門藝術(shù)，而不像是技術(shù)，但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計方法，你可以使用這些方法來設(shè)計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調(diào)整。但是在某些情況下，算法經(jīng)過調(diào)整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。<spanlang=EN-US><o:p></o:p></span></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'>本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應(yīng)用該算法給出貨箱裝船問題、背包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。<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'>1.1 </span><spanstyle='font-size:12.0pt;font-family:仿宋_GB2312;color:blue;mso-font-kerning:0pt'>最優(yōu)化問題<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'>本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（ </span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>optimization problem</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），每個最優(yōu)化問題都包含一組限制條件（ </span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>c o n s t ra i n t</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）和一個優(yōu)化函數(shù)（ </span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>optimizationfunction</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），符合限制條件的問題求解方案稱為可行解（ </span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>feasible solution</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>optimal solution</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）。<span lang=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></b><b><span lang=EN-USstyle='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1-1 [ </span></b><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>渴嬰問題</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'>] </span></b><span lang=EN-USstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'><span style="mso-spacerun: yes"> </span>有一個非常渴的、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>種不同的飲料。根據(jù)以前關(guān)于這</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><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><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -