貪心算法習(xí)題解析

背包問題定義如下：輸入：正數(shù)輸出：，使得：最大；給出一個求解背包問題的貪心算法，并證明其正確性。解：貪心思想：首先計算每種物品單位重量的價值，并進行由大到小的排序，然后依據(jù)貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包，若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超出，則選擇單位重量價值次高的物品，以此類推，每次都是選擇當(dāng)前未放入背包的單位重量價值最高的物品，直到總重量大于或等于。優(yōu)化子結(jié)構(gòu)：設(shè)A是此背包問題的優(yōu)化解，且A包含物品j，其中j的重量為w，則A’=A-{}是剩余的n-1個原重物品1,2,…,j-1,j+1,n以及重為的物品j中可裝入容量為M-w的背包問題的優(yōu)化解。證明：利用反證法。假設(shè)A’不是該子問題的優(yōu)化解，則存在B’是該子問題的優(yōu)化解，由此可知B'的價值大于A'的價值，令B=B'+{}，則B的價值大于A的價值，這與A是此問題的優(yōu)化解相矛盾。所以此問題具有優(yōu)化子結(jié)構(gòu)。貪心選擇性：計算每種物品單位重量的價值，并進行由大到小的排序。若，則存在背包問題的一個最優(yōu)解使得。證明：設(shè)A是一個優(yōu)化解，設(shè)其第一個物品的選擇為(1)如果，則命題成立。(2)如果，則X1在全部放入背包總價值不會超過M的情況下，并沒有全部放入，設(shè)B滿足，(i=2,3,...,n)與A相同，且調(diào)整最終的價值不會超過M，則B是一個優(yōu)化解且滿足正確性證明：因為算法處理過程按照最有子結(jié)構(gòu)和貪心選擇性依次處理背包問題，則此算法具有正確性。2.寫出分支界限的一般算法。（利用爬山算法）解：1)構(gòu)造由根組成的單元素棧S，根節(jié)點的權(quán)值初始化為0；2)將可行解初始化為cost=；3)計算當(dāng)前棧頂?shù)臋?quán)值=父節(jié)點的權(quán)值+該擴展分支的權(quán)值；4)IfTop(S)是目標(biāo)節(jié)點then根據(jù)該節(jié)點計算當(dāng)前可行解cost，cost=新的可行解；5)If當(dāng)前棧頂Top(S)的cost’>cost，則Pop(S)，且不再將其子節(jié)點入棧；6)將S的子節(jié)點按照其啟發(fā)式測度由大到小的順序壓入S；7)IfS空且cost=，then失敗;8)IfS空且cost!=，returncost;9)Elsegoto3.3.是一個可能解，當(dāng)且僅當(dāng)必是一個拓?fù)湫蛄?。證明：=>是一個可能解，而每個人的工作能力符合關(guān)系，則對于，若滿足偏序關(guān)系，則有；若不滿足偏序關(guān)系，則的分配無所謂順序，所以，必是一個拓?fù)湫蛄校?lt;=是一個拓?fù)湫蛄校瑢τ?，若滿足偏序關(guān)系，則有，其分配滿足；若不滿足偏序關(guān)系，則的分配無所謂順序，不妨使得分配情況滿足，于是將所有的工作分配完成之后，使得成立，則是一個分配任務(wù)的可能解。4.修改拓?fù)渑判蛩惴ǎ瑢懗鰢?yán)格的分支界限算法。（使用爬山法）解：1)生成樹根root，其權(quán)值為解代價下界；2)將可行解的代價初始化為cost=；3)選擇偏序集中沒有前序元素的所有元素，根據(jù)加工后的代價矩陣元素，按權(quán)值由大到小依次入棧，作為root的子節(jié)點；4)Forroot的每個子節(jié)點v，其權(quán)值為加工后的代價矩陣元素加其父節(jié)點權(quán)值；5)如果此節(jié)點為目標(biāo)節(jié)點，且權(quán)值不大于cost，則令cost=當(dāng)前節(jié)點的權(quán)值，作為界限；6)如果此節(jié)點權(quán)值大于cost，則將此分支剪掉，其子節(jié)點不再入棧；7)S=S-{v};8)把v作為根，遞歸地處理S.5.給出求解旅行商問題的詳細(xì)算法。解：1)根據(jù)各邊之間的權(quán)值，列出此問題的初始代價矩陣；2)將代價矩陣進行處理，每行（列）減去減去該行(列)的最小值，使得每行(列)至少有一個零，其余各元素非負(fù)，每行（列）所減去所有數(shù)的和即為解的代價下界；3)選擇滿足下列條件的邊(i,j)，使得，，所有包含(i,j)的解集合作為左子樹，所有不包含(i,j)的解集合作為右子樹；4)左子樹的代價下界不變，計算右子樹的代價：分別從變換后的代價矩陣的第i行第j列中找到具有最小代價的從i出發(fā)的邊(i,k)和進入j邊(r,j)，將這兩條邊的代價與其父節(jié)點的解的代價下界求和，即為右子樹節(jié)點的代價下界；5)構(gòu)造左子樹根對應(yīng)的代價矩陣：矩陣中的第i行第j列應(yīng)該被刪除，并且代價矩陣的(j,i)元素的位置應(yīng)該被置為；6)計算左子樹的代價下界：此時左子樹的代價矩陣中可能出現(xiàn)某行或某列沒有0的情況，則需相應(yīng)的減去一個對應(yīng)行或列的最小數(shù)，于是可以獲得左子樹的新代價下界；7)構(gòu)造右子樹根對應(yīng)的代價矩陣：把代價矩陣的(j,i)元素的位置置為；8)計算右子樹的代價下界：此時右子樹的代價矩陣中可能出現(xiàn)某行或某列沒有