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

PAGEPAGE6《高級(jí)算法設(shè)計(jì)與分析》期末試卷（試卷2）姓名：___________________學(xué)號(hào)：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)一、選擇題（每題3分，共45分）下面問題不能用動(dòng)態(tài)規(guī)劃求解的是：A：0-1背包問題B:矩陣連乘問題C:兩點(diǎn)之間最長路徑問題D:最大子數(shù)組問題貪心算法能夠獲得最優(yōu)解的是：A:旅行商問題B:0-1背包問題C:最大團(tuán)問題D:最小生成樹問題對(duì)如圖所示的旅行商問題，用分支限界法求解時(shí)，其最優(yōu)下界為：A:16B:18C:13D:15將下面非標(biāo)準(zhǔn)型的線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型：B.C.D.線性規(guī)劃問題如下，其對(duì)偶問題為：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問題，則A一定也是P問題，如果A是NPC問題，則B一定也是NPC問題如果A問題可以歸約為B問題，則A問題和B問題必須是一一對(duì)應(yīng)關(guān)系規(guī)約函數(shù)必須是多項(xiàng)式時(shí)間復(fù)雜度的函數(shù)以下問題不是NPC問題的是：A.小數(shù)背包問題B.最大團(tuán)問題C.旅行商問題D.整數(shù)規(guī)劃問題在團(tuán)問題的NP難證明過程中,以下說法錯(cuò)誤的是：3合取范式可以歸約為團(tuán)問題歸約的過程中，3合取范式會(huì)歸約為一個(gè)特殊的圖，所以我們只能說明這個(gè)特殊的圖的團(tuán)問題是NP難的，而無法證明所有的圖的團(tuán)問題都是NP難的在規(guī)約的過程中,一個(gè)子句對(duì)應(yīng)一組頂點(diǎn)，對(duì)于任意兩個(gè)在不同組的頂點(diǎn)，如果滿足“這兩個(gè)頂點(diǎn)不是‘否’的關(guān)系”這一條件，就用一條邊連接如果3合取范式如果有k個(gè)子句，則需要證明圖中有規(guī)模為k的團(tuán)針對(duì)集合覆蓋問題，設(shè)wi為子集Si的權(quán)重，xi=0表示沒有選中子集Si，xi=1表示選中子集Si。則集合覆蓋問題建模成整數(shù)規(guī)劃形式為（注：n為元素的個(gè)數(shù)，m為子集的個(gè)數(shù)）：B.C.D.下面對(duì)旅行商問題（滿足三角不等式）的近似算法描述錯(cuò)誤的是：算法的基本思想是：生成最小生成樹，按對(duì)樹進(jìn)行先序遍歷的順序訪問節(jié)點(diǎn)。最小生成樹的總代價(jià)小于等于旅行商回路的總代價(jià)對(duì)T進(jìn)行按先序往返遍歷，其總代價(jià)小于等于2倍的旅行商回路的總代價(jià)算法的總代價(jià)大于等于對(duì)T進(jìn)行按先序往返遍歷的總代價(jià)下面對(duì)在線算法和離線算法比較，以下描述錯(cuò)誤的是：即使數(shù)據(jù)在計(jì)算時(shí)都已知，也可以采用在線算法來達(dá)到更好的結(jié)果在線算法通常是近似算法通常通過和離線最優(yōu)算法的比較來判斷在線算法的好壞，如果在線算法的代價(jià)Con和離線算法的代價(jià)Coff有關(guān)系，則稱在線算法在實(shí)例IA上為α競(jìng)爭度算法最小生成樹在線算法可通過貪心算法實(shí)現(xiàn)在租賣問題的在線算法中，b=2為購買價(jià)格，l<=3為天數(shù)，則所有的確定性算法如下表，其中Ai為第i天購買，Ii為滑雪場(chǎng)最后一天開放為第i天，其中錯(cuò)誤的是：最好的確定性算法為A2和A?，都是3/2競(jìng)爭度在線算法中，以1/3的概率執(zhí)行A1策略，2/3的概率執(zhí)行A2策略，可以實(shí)現(xiàn)競(jìng)爭度4/3在線算法中，以2/3的概率執(zhí)行A1策略，1/3的概率執(zhí)行A2策略，也可以實(shí)現(xiàn)競(jìng)爭度4/3本例子在線算法的最優(yōu)競(jìng)爭度為4/3下面對(duì)禁忌表搜索（Tabusearch）算法描述錯(cuò)誤的是：算法的基本思想是標(biāo)記已經(jīng)解得的局部最優(yōu)解或求解過程，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解或求解過程那些目前在禁忌表的解或者求解過程是無條件被禁止的進(jìn)入禁忌表的解或者求解過程在一定的時(shí)間后會(huì)被解禁禁忌表搜索每次迭代總是在前一次迭代的領(lǐng)域中進(jìn)行搜索二、計(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)用。（10分）已知下面的線性規(guī)劃問題，其對(duì)偶問題的最優(yōu)解為y*=(y1,y2)=(4,1)，試用對(duì)偶的互補(bǔ)松弛性求原問題的最優(yōu)解（10分）集合覆蓋的問題如下：X為元素的集合，Si為X的一個(gè)子集，F(xiàn)為Si的集合，集合覆蓋就是找到F的一個(gè)最小子集C，使得X中的所有元素都C覆蓋。試證明集合覆蓋是NPC問題(10分)簡單描述如何用遺傳算法實(shí)現(xiàn)廣義旅行商問題的求解，描述要包含個(gè)體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）三、算法設(shè)計(jì)題（共15分）1.0-1背包問題:設(shè)有n個(gè)