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

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