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

PAGE6PAGE《高級(jí)算法設(shè)計(jì)與分析》期末試卷（試卷2）姓名：___________________學(xué)號(hào)：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)一、選擇題（每題3分，共45分）下面問(wèn)題不能用動(dòng)態(tài)規(guī)劃求解的是：A：0-1背包問(wèn)題B:矩陣連乘問(wèn)題C:兩點(diǎn)之間最長(zhǎng)路徑問(wèn)題D:最大子數(shù)組問(wèn)題貪心算法能夠獲得最優(yōu)解的是：A:旅行商問(wèn)題B:0-1背包問(wèn)題C:最大團(tuán)問(wèn)題D:最小生成樹(shù)問(wèn)題對(duì)如圖所示的旅行商問(wèn)題，用分支限界法求解時(shí)，其最優(yōu)下界為：A:16B:18C:13D:15將下面非標(biāo)準(zhǔn)型的線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型：B.C.D.線性規(guī)劃問(wèn)題如下，其對(duì)偶問(wèn)題為：B.D.對(duì)于隨機(jī)算法的描述，以下描述錯(cuò)誤的是:A.算法運(yùn)算很快B.算法有一定的概率產(chǎn)生錯(cuò)誤的結(jié)果C.算法的輸出是確定的D.隨機(jī)快速排序的期望時(shí)間復(fù)雜度為O(nlogn)在隨機(jī)快速排序算法中，設(shè)S(i)表示集合S中階為i的元素，下面描述錯(cuò)誤的是（注：j>i）:只有S(i)和S(j)這兩個(gè)元素其一被選為主元素的時(shí)候，他們才進(jìn)行比較當(dāng)元素S(k)(i<k<j)被選為主元素時(shí)，S(i)和S(j)肯定不會(huì)進(jìn)行比較S(i)和S(j)比較的概率為：pij=2/(j-i+1)當(dāng)元素S(k)(k>j)被選為主元素時(shí)，S(i)和S(j)肯定會(huì)進(jìn)行比較以下對(duì)規(guī)約的描述錯(cuò)誤的是：，如果B是P問(wèn)題，則A一定也是P問(wèn)題，如果A是NPC問(wèn)題，則B一定也是NPC問(wèn)題如果A問(wèn)題可以歸約為B問(wèn)題，則A問(wèn)題和B問(wèn)題必須是一一對(duì)應(yīng)關(guān)系規(guī)約函數(shù)必須是多項(xiàng)式時(shí)間復(fù)雜度的函數(shù)以下問(wèn)題不是NPC問(wèn)題的是：A.小數(shù)背包問(wèn)題B.最大團(tuán)問(wèn)題C.旅行商問(wèn)題D.整數(shù)規(guī)劃問(wèn)題在團(tuán)問(wèn)題的NP難證明過(guò)程中,以下說(shuō)法錯(cuò)誤的是：3合取范式可以歸約為團(tuán)問(wèn)題歸約的過(guò)程中，3合取范式會(huì)歸約為一個(gè)特殊的圖，所以我們只能說(shuō)明這個(gè)特殊的圖的團(tuán)問(wèn)題是NP難的，而無(wú)法證明所有的圖的團(tuán)問(wèn)題都是NP難的在規(guī)約的過(guò)程中,一個(gè)子句對(duì)應(yīng)一組頂點(diǎn)，對(duì)于任意兩個(gè)在不同組的頂點(diǎn)，如果滿足“這兩個(gè)頂點(diǎn)不是‘否’的關(guān)系”這一條件，就用一條邊連接如果3合取范式如果有k個(gè)子句，則需要證明圖中有規(guī)模為k的團(tuán)針對(duì)集合覆蓋問(wèn)題，設(shè)wi為子集Si的權(quán)重，xi=0表示沒(méi)有選中子集Si，xi=1表示選中子集Si。則集合覆蓋問(wèn)題建模成整數(shù)規(guī)劃形式為（注：n為元素的個(gè)數(shù)，m為子集的個(gè)數(shù)）：B.C.D.下面對(duì)旅行商問(wèn)題（滿足三角不等式）的近似算法描述錯(cuò)誤的是：算法的基本思想是：生成最小生成樹(shù)，按對(duì)樹(shù)進(jìn)行先序遍歷的順序訪問(wèn)節(jié)點(diǎn)。最小生成樹(shù)的總代價(jià)小于等于旅行商回路的總代價(jià)對(duì)T進(jìn)行按先序往返遍歷，其總代價(jià)小于等于2倍的旅行商回路的總代價(jià)算法的總代價(jià)大于等于對(duì)T進(jìn)行按先序往返遍歷的總代價(jià)下面對(duì)在線算法和離線算法比較，以下描述錯(cuò)誤的是：即使數(shù)據(jù)在計(jì)算時(shí)都已知，也可以采用在線算法來(lái)達(dá)到更好的結(jié)果在線算法通常是近似算法通常通過(guò)和離線最優(yōu)算法的比較來(lái)判斷在線算法的好壞，如果在線算法的代價(jià)Con和離線算法的代價(jià)Coff有關(guān)系，則稱在線算法在實(shí)例IA上為α競(jìng)爭(zhēng)度算法最小生成樹(shù)在線算法可通過(guò)貪心算法實(shí)現(xiàn)在租賣問(wèn)題的在線算法中，b=2為購(gòu)買價(jià)格，l<=3為天數(shù)，則所有的確定性算法如下表，其中Ai為第i天購(gòu)買，Ii為滑雪場(chǎng)最后一天開(kāi)放為第i天，其中錯(cuò)誤的是：最好的確定性算法為A2和A?，都是3/2競(jìng)爭(zhēng)度在線算法中，以1/3的概率執(zhí)行A1策略，2/3的概率執(zhí)行A2策略，可以實(shí)現(xiàn)競(jìng)爭(zhēng)度4/3在線算法中，以2/3的概率執(zhí)行A1策略，1/3的概率執(zhí)行A2策略，也可以實(shí)現(xiàn)競(jìng)爭(zhēng)度4/3本例子在線算法的最優(yōu)競(jìng)爭(zhēng)度為4/3下面對(duì)禁忌表搜索（Tabusearch）算法描述錯(cuò)誤的是：算法的基本思想是標(biāo)記已經(jīng)解得的局部最優(yōu)解或求解過(guò)程，并在進(jìn)一步的迭代中避開(kāi)這些局部最優(yōu)解或求解過(guò)程那些目前在禁忌表的解或者求解過(guò)程是無(wú)條件被禁止的進(jìn)入禁忌表的解或者求解過(guò)程在一定的時(shí)間后會(huì)被解禁禁忌表搜索每次迭代總是在前一次迭代的領(lǐng)域中進(jìn)行搜索二、計(jì)算、建模題（共40分）設(shè)某指派問(wèn)題的費(fèi)用矩陣為：其中第i行表示第i個(gè)人被指派各個(gè)任務(wù)的費(fèi)用，而第j列第j個(gè)任務(wù)被分配到各個(gè)人的費(fèi)用。試用匈牙利法求最優(yōu)指派，以及在最優(yōu)指派下的總費(fèi)用。（10分）已知下面的線性規(guī)劃問(wèn)題，其對(duì)偶問(wèn)題的最優(yōu)解為y*=(y1,y2)=(4,1)，試用對(duì)偶的互補(bǔ)松弛性求原問(wèn)題的最優(yōu)解（10分）集合覆蓋的問(wèn)題如下：X為元素的集合，Si為X的一個(gè)子集，F(xiàn)為Si的集合，集合覆蓋就是找到F的一個(gè)最小子集C，使得X中的所有元素都C覆蓋。試證明集合覆蓋是NPC問(wèn)題(10分)簡(jiǎn)單描述如何用遺傳算法實(shí)現(xiàn)廣義旅行商問(wèn)題的求解，描述要包含個(gè)體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）三、算法設(shè)計(jì)題（共15分）1.0-1背包問(wèn)題:設(shè)有n個(gè)物品,其重量為w1,w2,…,wn，價(jià)值為v1,v2,…,vn，背包的承重為C（wi<C）。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。請(qǐng)用近似算法求解此問(wèn)題(描述此算法的思路)，并計(jì)算此算法的復(fù)雜度和近似度。《高級(jí)算法設(shè)計(jì)與分析》期末試卷答案（答案）姓名：___________________學(xué)號(hào)：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)一、選擇題（每題3分，共45分）C，D，A，B，CC，D，C，A，BA，D，A，C，B二、計(jì)算、建模題（共40分）設(shè)某指派問(wèn)題的費(fèi)用矩陣為：其中第i行表示第i個(gè)人被指派各個(gè)任務(wù)的費(fèi)用，而第j列第j個(gè)任務(wù)被分配到各個(gè)人的費(fèi)用。試用匈牙利法求最優(yōu)指派，以及在最優(yōu)指派下的總費(fèi)用。解：將每行減去最小值得到：每列減去最小值得到：將所有還沒(méi)有被劃線覆蓋的元素減去最小值由以上矩陣可知：任務(wù)3指派給人員1；任務(wù)1指派給人員3；任務(wù)2指派給人員2；最下總費(fèi)用為：7+10+9=26已知下面的線性規(guī)劃問(wèn)題，其對(duì)偶問(wèn)題的最優(yōu)解為y*=(y1,y2)=(4,1)，試用對(duì)偶的互補(bǔ)松弛性求原問(wèn)題的最優(yōu)解解：原問(wèn)題的對(duì)偶問(wèn)題為將（4，1）帶入約束條件，1，2為嚴(yán)格不等式，所以X1=0,x2=0;有因?yàn)閥1，y2>0，故約束條件解得x3=4，x4=4.集合覆蓋的問(wèn)題如下：X為元素的集合，Si為X的一個(gè)子集，F(xiàn)為Si的集合，集合覆蓋就是找到F的一個(gè)最小子集C，使得X中的所有元素都C覆蓋。試證明集合覆蓋是NPC問(wèn)題(10分)參考答案:1.頂點(diǎn)覆蓋可歸約為集合覆蓋；2.頂點(diǎn)覆蓋是NP問(wèn)題。給定某個(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è)集合覆蓋問(wèn)題3.1圖G具有大小為k的一個(gè)頂點(diǎn)覆蓋P，因P中所有點(diǎn)覆蓋圖G中所有的邊，所以P中點(diǎn)對(duì)應(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所對(duì)應(yīng)的點(diǎn)集合P必然覆蓋G中所有的點(diǎn)，且S是一個(gè)規(guī)模為k的集合。4）簡(jiǎn)單描述如何用遺傳算法實(shí)現(xiàn)廣義旅行商問(wèn)題的求解，描述要包含個(gè)體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）參考答案：設(shè)有m個(gè)城市群，每個(gè)城市群只要訪問(wèn)其中一個(gè)城市即可，設(shè)T(i)代表第i個(gè)城市群中所有的城市1、染色體由頭部和身體組成，如下圖，其中頭部（從1到m）表示在訪問(wèn)第i個(gè)城市群訪問(wèn)的具體城市（如頭部的第i（1<=i<=m）個(gè)元素4，表示訪問(wèn)了第i個(gè)城市群中的第4個(gè)城市），身體（從m+1到2m）表示對(duì)城市群訪問(wèn)的順利。隨機(jī)初始化n個(gè)染色體。2、對(duì)n個(gè)染色體進(jìn)行局搜索，即針對(duì)每個(gè)染色體，改變頭部的值，使得在此染色體城市群訪問(wèn)順序下，對(duì)每個(gè)城市群選擇最優(yōu)的城市。計(jì)算局部搜索后每個(gè)染色體的適應(yīng)度值（這里我使用路徑長(zhǎng)度的倒數(shù)表示個(gè)體適應(yīng)性）；3、使用輪盤選擇方式選擇個(gè)體，形成父染色體；4、按照交叉概率，對(duì)父染色體的身體部分進(jìn)行兩兩交叉生成n個(gè)染色體；6、對(duì)這n個(gè)染色體的身體部分按照變異概率進(jìn)行變異；7、判斷是否達(dá)到迭代次數(shù)，是，結(jié)束，返回最優(yōu)解；否，轉(zhuǎn)到第2步。三、算法設(shè)計(jì)題（共15分）0-1背包問(wèn)題:設(shè)有n個(gè)物品,其重量為w1,w2,…,wn，價(jià)值為v1,v2,…,vn，背包的承重為C（wi<C）。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。請(qǐng)問(wèn)近似算法求解此問(wèn)題，(描述此算法的思路)，并計(jì)算此算法的復(fù)雜度和近似度.參考答案:算法:1.將所有的物品按照性價(jià)比排列2.按順序考察物品，只要能夠裝入背包裝入此物品，得總價(jià)值為V3.求vk=ma