雖然設計一個好的求解算法更像是一門藝術而不像是技術但仍然存在一些行之有效的能夠用於解決許多問題的算法設計方法你可以使用這些方法來設計算法並觀察這些算法是如何工作的一般情況下為了獲得較好的性能必須對算法進行細致的調整但是在某些情況下算法經過調整之後性能仍無法達到要求這時就必須尋求另外的方法來求解該問題
本章首先引入最優化的概念然後介紹一種直觀的問題求解方法貪婪算法最後應用該算法給出貨箱裝船問題背包問題拓撲排序問題二分覆蓋問題最短路徑問題最小代價生成樹等問題的求解方案
最優化問題
本章及後續章節中的許多例子都是最優化問題( optimization problem)每個最優化問題都包含一組限制條件( c o n s t r a i n t)和一個優化函數( optimization function)符合限制條件的問題求解方案稱為可行解( feasible solution)使優化函數取得最佳值的可行解稱為最優解(optimal solution)
例 [ 渴嬰問題] 有一個非常渴的聰明的小嬰兒她可能得到的東西包括一杯水一桶牛奶多罐不同種類的果汁許多不同的裝在瓶子或罐子中的蘇打水即嬰兒可得到n 種不同的飲料根據以前關於這n 種飲料的不同體驗此嬰兒知道這其中某些飲料更合自己的胃口因此嬰兒采取如下方法為每一種飲料賦予一個滿意度值飲用盎司第i 種飲料對它作出相對評價將一個數值si 作為滿意度賦予第i 種飲料
通常這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要但是不幸的是具有最大滿意度值的飲料有時並沒有足夠的量來滿足此嬰兒解渴的需要設ai是第i 種飲料的總量(以盎司為單位)而此嬰兒需要t 盎司的飲料來解渴那麼需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢?
設各種飲料的滿意度已知令xi 為嬰兒將要飲用的第i 種飲料的量則需要解決的問題是
找到一組實數xi(≤i≤n)使n ?i = si xi 最大並滿足n ?i=xi =t 及≤xi≤ai
需要指出的是如果n ?i = ai < t則不可能找到問題的求解方案因為即使喝光所有的飲料也不能使嬰兒解渴
對上述問題精確的數學描述明確地指出了程序必須完成的工作根據這些數學公式可以對輸入/ 輸出作如下形式的描述
輸入ntsi ai(其中≤i≤nn 為整數tsi ai 為正實數)
輸出實數xi(≤i≤n)使n ?i= si xi 最大且n ?i=xi =t(≤xi≤ai)如果n ?i = ai
在這個問題中限制條件是n ?i= xi =t 且≤xi≤ai≤i≤n而優化函數是n ?i= si xi 任何滿足限制條件的一組實數xi 都是可行解而使n ?i= si xi 最大的可行解是最優解
例 [裝載問題] 有一艘大船准備用來裝載貨物所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣但貨箱的重量都各不相同設第i 個貨箱的重量為wi(≤i≤n)而貨船的最大載重量為c我們的目的是在貨船上裝入最多的貨物
這個問題可以作為最優化問題進行描述設存在一組變量xi 其可能取值為或如xi 為則貨箱i 將不被裝上船;如xi 為則貨箱i 將被裝上船我們的目的是找到一組xi 使它滿足限制條件n ?i = wi xi ≤c 且x i ? { } ≤i≤n相應的優化函數是n ?i= xi
滿足限制條件的每一組xi 都是一個可行解能使n ?i= xi 取得最大值的方案是最優解
例 [最小代價通訊網絡] 城市及城市之間所有可能的通信連接可被視作一個無向圖圖的每條邊都被賦予一個權值權值表示建成由這條邊所表示的通信連接所要付出的代價包含圖中所有頂點(城市)的連通子圖都是一個可行解設所有的權值都非負則所有可能的可行解都可表示成無向圖的一組生成樹而最優解是其中具有最小代價的生成樹
在這個問題中需要選擇一個無向圖中的邊集合的子集這個子集必須滿足如下限制條件所有的邊構成一個生成樹而優化函數是子集中所有邊的權值之和
From:http://tw.wingwit.com/Article/program/sjjg/201311/23602.html
