📄 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'>虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。<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'>本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。<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'>最优化问题<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'>本章及后续章节中的许多例子都是最优化问题（ </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'>），每个最优化问题都包含一组限制条件（ </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'>）和一个优化函数（ </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'>），使优化函数取得最佳值的可行解称为最优解（</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'>种不同的饮料。根据以前关于这</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;⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -