《高級算法設(shè)計(jì)與分析》試卷2答案

PAGEPAGE6《高級算法設(shè)計(jì)與分析》期末試卷答案（答案）姓名：___________________學(xué)號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學(xué)號一、選擇題（每題3分，共45分）C，D，A，B，CC，D，C，A，BA，D，A，C，B二、計(jì)算、建模題（共40分）設(shè)某指派問題的費(fèi)用矩陣為：其中第i行表示第i個(gè)人被指派各個(gè)任務(wù)的費(fèi)用，而第j列第j個(gè)任務(wù)被分配到各個(gè)人的費(fèi)用。試用匈牙利法求最優(yōu)指派，以及在最優(yōu)指派下的總費(fèi)用。解：將每行減去最小值得到：每列減去最小值得到：將所有還沒有被劃線覆蓋的元素減去最小值由以上矩陣可知：任務(wù)3指派給人員1；任務(wù)1指派給人員3；任務(wù)2指派給人員2；最下總費(fèi)用為：7+10+9=26已知下面的線性規(guī)劃問題，其對偶問題的最優(yōu)解為y*=(y1,y2)=(4,1)，試用對偶的互補(bǔ)松弛性求原問題的最優(yōu)解解：原問題的對偶問題為將（4，1）帶入約束條件，1，2為嚴(yán)格不等式，所以X1=0,x2=0;有因?yàn)閥1，y2>0，故約束條件解得x3=4，x4=4.集合覆蓋的問題如下：X為元素的集合，Si為X的一個(gè)子集，F(xiàn)為Si的集合，集合覆蓋就是找到F的一個(gè)最小子集C，使得X中的所有元素都C覆蓋。試證明集合覆蓋是NPC問題(10分)參考答案:1.頂點(diǎn)覆蓋可歸約為集合覆蓋；2.頂點(diǎn)覆蓋是NP問題。給定某個(gè)圖G=（V，E）以及一個(gè)點(diǎn)集P，很容易在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)集合P是否覆蓋圖G中的所有邊；3.歸約證明：設(shè)G=（V，E）為圖，另X=E，Si為頂點(diǎn)i所覆蓋邊的集合，F(xiàn)為Si的集合，則形成（X，F(xiàn)）的一個(gè)集合覆蓋問題3.1圖G具有大小為k的一個(gè)頂點(diǎn)覆蓋P，因P中所有點(diǎn)覆蓋圖G中所有的邊，所以P中點(diǎn)對應(yīng)的Si必然覆蓋X中的所有元素，也就是Si成的集合S必然會(huì)覆蓋X中的所有邊，所以S是（X，F(xiàn)）的一個(gè)大小為k的集合覆蓋。3.2設(shè)S是（X，F(xiàn)）的一個(gè)大小為k的集合覆蓋，則S中所有的集合必然覆蓋X中的所有點(diǎn)，所以S所對應(yīng)的點(diǎn)集合P必然覆蓋G中所有的點(diǎn)，且S是一個(gè)規(guī)模為k的集合。4）簡單描述如何用遺傳算法實(shí)現(xiàn)廣義旅行商問題的求解，描述要包含個(gè)體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）參考答案：設(shè)有m個(gè)城市群，每個(gè)城市群只要訪問其中一個(gè)城市即可，設(shè)T(i)代表第i個(gè)城市群中所有的城市1、染色體由頭部和身體組成，如下圖，其中頭部（從1到m）表示在訪問第i個(gè)城市群訪問的具體城市（如頭部的第i（1<=i<=m）個(gè)元素4，表示訪問了第i個(gè)城市群中的第4個(gè)城市），身體（從m+1到2m）表示對城市群訪問的順利。隨機(jī)初始化n個(gè)染色體。2、對n個(gè)染色體進(jìn)行局搜索，即針對每個(gè)染色體，改變頭部的值，使得在此染色體城市群訪問順序下，對每個(gè)城市群選擇最優(yōu)的城市。計(jì)算局部搜索后每個(gè)染色體的適應(yīng)度值（這里我使用路徑長度的倒數(shù)表示個(gè)體適應(yīng)性）；3、使用輪盤選擇方式選擇個(gè)體，形成父染色體；4、按照交叉概率，對父染色體的身體部分進(jìn)行兩兩交叉生成n個(gè)染色體；6、對這n個(gè)染色體的身體部分按照變異概率進(jìn)行變異；7、判斷是否達(dá)到迭代次數(shù)，是，結(jié)束，返回最優(yōu)解；否，轉(zhuǎn)到第2步。三、算法設(shè)計(jì)題（共15分）0-1背包問題:設(shè)有n個(gè)物品,其重量為w1,w2,…,wn，價(jià)值為v1,v2,…,vn，背包的承重為C（wi<C）。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。請問近似算法求解此問題，(描述此算法的思路)，并計(jì)算此算法的復(fù)雜度和近似度.參考答案:算法:1.將所有的物品按照性價(jià)比排列2.按順序考察物品，只要能夠裝入背包裝入此物品，得總價(jià)值為V3.求vk=max{vi:foralli}，如vk>V，則將背包內(nèi)的物品替換成物品k精確度:設(shè)最優(yōu)算法得出的總價(jià)值為Vopt，貪心算法得出的總價(jià)值為Vgreedy，設(shè)l為第一件未裝入背包的物品，因物品按照性價(jià)比排序，所以：Vopt<=Vgreedy+v