color:black;mso-font-kerning:0pt'>i</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><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='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.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><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>都是一個可行解，能使</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-USstyle='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='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-3 [</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><spanstyle='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]>&nbsp;<![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.2 </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]>&nbsp;<![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><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>greedy method</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'>greedy criterion</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-4 [</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><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'>1</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><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2 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 0</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'>美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。<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'>假設需要找給小孩</span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>6 7</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'>2 5</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'>2 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'>6 7</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 0</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 lang=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'>貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明采用上述貪婪算法找零錢時所用的硬幣數目的確最少（見練習</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 lang=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'><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-5 [</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><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>現有</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><spanstyle='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'>s</span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，完成時間為</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>f</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><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'>s</span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&lt; <i>f</i></span><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><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'>[<i>s</i></span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>, <i>f</i></span><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>] </span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>為處理任務</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>的時間范圍。兩個任務</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</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'>j </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'>i</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'>j </span></i><span style='font