《高級算法設計與分析》試卷及答案 共4套

PAGEPAGE4《高級算法設計與分析》期末試卷（試卷1）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）目前比較排序所能夠達到的最優(yōu)計算復雜度為：A：Θ(n)B:Θ(nlogn)C:Θ(n2)D:Θ(n2logn)哪兩個算法需要最優(yōu)子結構性質A:分治和動態(tài)規(guī)劃B:分治和貪心C:動態(tài)規(guī)劃和貪心D:動態(tài)規(guī)劃和回溯線性規(guī)劃的標準形式是：B.C.D.下列標準型化轉化為松弛型:B.C.D.對于隨機快速排序,以下描述錯誤的是:A.隨機快速排序消除或減少了一般快速排序的最壞時間復雜度B.隨機快速排序屬于舍伍德算法C.隨機快速排序的時間復雜度一定比一般快速排序的時間復雜度好D.隨機快速排序的期望時間復雜度為O(nlogn)對于拉斯維加斯和蒙特卡洛算法描述錯誤的是:A.拉斯維加斯算法不一定獲得解,但如果獲得解一定是正確的B.蒙特卡洛算法可能給出錯誤解C.拉斯維加斯算法找到解得概率與算法執(zhí)行時間成正比D.隨機選擇屬于蒙特卡洛算法以下對規(guī)約的描述錯誤的是：，如果B是P問題，則A一定也是P問題，如果A是NPC問題，則B一定也是NPC問題，如果B是NP問題，則A一定也是NP問題L1代表A的算法,L2代表B的算法,則L1(x)=L2(f(x)),其中f為規(guī)約函數(shù)對NPC問題,以下說法正確的是：A.這個問題是一定是NP問題B.這個問題一定不是NP問題C.已經(jīng)證明這個問題一定是P問題D.已經(jīng)證明這個問題一定不是P問題以下問題不是NPC問題的是：A.歐拉回路問題B.最大團問題C.3合取范式D.0-1背包問題在團問題(圖G)規(guī)約為頂點覆蓋問題(圖)中,以下說法錯誤的是：設（u,v）為的任意邊，則（u，v）其中至少一個點不屬于G的團設（u,v）為的任意邊，則（u，v）其中至少一個點屬于的頂點覆蓋如果有兩個頂點u,v都不屬于的頂點覆蓋，則這兩個頂點一定屬于G的團圖G中有規(guī)模為k的團，當且僅當圖有規(guī)模為k的頂點覆蓋在旅行商問題的NP難證明過程中,以下說法錯誤的是：通常通過哈密頓回路來規(guī)約旅行商問題在規(guī)約的過程中,目的是找一條成本為n(n為邊數(shù))的旅行線路在規(guī)約的過程中,需要將原圖擴展成一個完全圖擴展成完全圖后,原來的邊設成本為0,擴展的邊設成本為1下面對子集和的近似算法描述錯誤的是：如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，則{x1,x2,x3,…,xi,xi+1}所有的子集和為。在計算過程中，為了減少子集和的規(guī)模，算法通過去除大于目標值的子集和，以及刪除相似子集和的方法實現(xiàn)如果算法過程中，不刪除相似的子集和（僅僅去除大于目標值的子集和），是可以得到精確的結果的子集和的近似算法只是一個多項式時間近似算法，而不是一個完全多項式時間的近似算法下面對在線算法和離線算法比較，以下描述錯誤的是：即使數(shù)據(jù)在計算時都已知，也可以采用在線算法來達到更好的結果在線算法通常是近似算法通常通過和離線最優(yōu)算法的比較來判斷在線算法的好壞，如果在線算法的代價Con和離線算法的代價Coff有關系，則稱在線算法在實例IA上為α競爭度算法最小生成樹在線算法可通過貪心算法實現(xiàn)下面對最小生成樹在線算法描述錯誤的是：最小生成樹在線算法是一種貪心算法算法復雜度為O（n2）算法競爭度為O（n）生成樹在線算法生成樹中第k長的邊長度小于等于2l/k，其中l(wèi)為最小生成樹的代價下面對模擬退火描述錯誤的是：Greedy算法，但是加入隨機因素若目標函數(shù)在第i+1步移動后比第i步更優(yōu)，則總是被接受以一定的概率來接受一個比當前解要差的解，用于跳出局部最優(yōu)解這個概率隨著溫度的降低，變的更大，以便更快的跳出局部最優(yōu)解二、計算、建模題（共40分）已知線性規(guī)劃問題,其對偶問題的最優(yōu)解為*=(y1,y2,y3,y4)=(0,0,4,4)，試用對偶的互補松弛性求原問題的最優(yōu)解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0某市下設八個區(qū),下表給出救護車從一個區(qū)到另外一個區(qū)的車程時間(min)。該市擬建救護中心，要求各區(qū)離救護中心的車程時間必須在8min之內(nèi)（包括8min），問至少建多少個救護中心，建于何處（只需要建立模型，無需計算）？（10分）參考3合取范式歸約團問題的過程，證明最大獨立集問題是NPC問題。最大獨立集是給一無向圖，找出一個點集，使得任意兩點之間都沒有連邊，這個點集就是獨立集。而點最多的獨立集，就是最大獨立集。(10分)4）簡單描述如何用遺傳算法實現(xiàn)旅行商問題的求解，描述要包含個體（染色體）設置，適應度函數(shù)定義，選擇算子，交叉和變異操作（10分）三、算法設計題（共15分）裝箱問題:設有n個物品,其大小為a1,a2,a3,…,an(0<ai<=1),現(xiàn)需要將這n個物品裝入大小為1的箱子,求裝完物品最少的箱子個數(shù)。此問題為NPC問題，請用近似算法求解(給出此算法的思路,并用算法來實現(xiàn)如下具體例子)，還需要計算此算法的精確度（α）.例子:10個物品其大小分別為(0.4,0.8,0.5,0.1,0.7,0.6,0.1,0.4,0.2,0.2)，這十個物品的標號分別為1，2，3…10，按照你設計的算法將這個10個物品放入箱子?！陡呒壦惴ㄔO計與分析》期末試卷答案（試卷1）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）BCBAB；DCAAD；BDACD二、計算、建模題（共40分）已知線性規(guī)劃問題,其對偶問題的最優(yōu)解為*=(y1,y2,y3,y4)=(0,0,4,4)，試用對偶的互補松弛性求原問題的最優(yōu)解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0解：此問題的對偶問題為將(0,0,4,4)帶入約束條件，約束條件都為等式，無法得出解因y3和y4大于0，所以x1+x2=5x1+2x2=6解得x1=4；x2=1某市下設八個區(qū),下表給出救護車從一個區(qū)到另外一個區(qū)的車程時間(min)。該市擬建救護中心，要求各區(qū)離救護中心的車程時間必須在8min之內(nèi)（包括8min），問至少建多少個救護中心，建于何處（只需要建立模型，無需計算）？（10分）解：參考答案1:根據(jù)上表，如救護中心建在某區(qū)，其能覆蓋的區(qū)域如下：1：1，2，72：1，23：3，4，5，64：3，4，5，65：3，4，5，66：3，4，5，6，87：1，78：6，8設：其中1表示設在某區(qū)，0表示不設則建模為：參考答案2:建立圖：每個區(qū)域為一個頂點，如果區(qū)域之間的車程小于等于8min，則兩個頂點之間有邊，否則無邊，建立圖如下則原問題建模為求解最小覆蓋集問題參考3合取范式歸約團問題的過程，證明最大獨立集問題是NPC問題。最大獨立集是給一無向圖，找出一個點集，使得任意兩點之間都沒有連邊，這個點集就是獨立集。而點最多的獨立集，就是最大獨立集。(10分)參考答案1:1..最大獨立集是NP問題:給定某個獨立集，很容易在二項式時間內(nèi)驗證獨立集合中的點是否在原圖中存在連接.2.規(guī)約：將每個子句對應于一組節(jié)點組，其各個節(jié)點之間都有連線，而各組之間只有相互取反的節(jié)點有連線（剛好和團的規(guī)約相反），如3合取范式規(guī)約為：則取使得3合取范式為1的一個解，則必然存在一組獨立集，如上例中（x反，z）使得3合取范式成立，則圖中存在（x反，z，z，x反）的4各元素獨立集。反之，如果圖中國存在4個元素的獨立集，對著4個元素對應的變量賦值為1，則3合取范式成立。參考答案2（通過頂點覆蓋可歸約為最大獨立集問題）設G=(V，E)為圖，k為頂點覆蓋集，則|V|-k為圖G的獨立集。對于任意兩個頂點不屬于頂點覆蓋集，則這兩個頂點必然沒有邊，所有這些頂點兩兩之間都沒有邊，所以這些頂點形成了獨立集(V-k)。同理，如果存在(V-k)的最大獨立集，取獨立集外的任意一個點，這個點至少存在一條邊和頂點覆蓋集中的一個點連接。所有的這些點將覆蓋:1.這些點和獨立集的邊(這些邊是獨立的，也就是說不存在兩個頂點覆蓋同一條邊);2.所有的邊(因為獨立集沒有邊，顯然，所有獨立集外的點將覆蓋所有的獨立集外的邊，即所有的邊)4）簡單描述如何用遺傳算法實現(xiàn)旅行商問題的求解，描述要包含個體（染色體）設置，適應度函數(shù)定義，選擇算子，交叉和變異操作（10分）解：程序流程（參考答案）1、根據(jù)輸入的城市初始化個體（染色體），并生成n個個體，即初始種群；2、計算每個基因序列的適應性，適應性與路徑長度成反比（這里我使用路徑長度的倒數(shù)表示個體適應性）；3、使用輪盤選擇方式選擇個體，形成父本；4、按照交叉概率，對父本兩兩進行交叉生成n個個體；6、對這n個個體按照變異概率進行變異；7、判斷是否達到迭代次數(shù)，是，結束，返回最優(yōu)解；否，轉到第2步。三、算法設計題（共15分）裝箱問題:設有n個物品,其大小為a1,a2,a3,…,an(0<ai<=1),現(xiàn)需要將這n個物品裝入大小為1的箱子,求裝完物品最少的箱子個數(shù)。此問題為NPC問題，請用近似算法求解(給出此算法的思路,并用算法來實現(xiàn)如下具體例子)，還需要計算此算法的精確度（α）.例子:10個物品其大小分別為(0.4,0.8,0.5,0.1,0.7,0.6,0.1,0.4,0.2,0.2)參考答案:算法:將物品按順序放入箱子,具體放法如下:如果第一個箱子能夠放此物品,則放,否則考察一下一個箱子,如果已打開的所有箱子都不能放,則新開一個箱子.應用算法得出結果如下:精確度:設C*為最優(yōu)個數(shù),此算法得出的箱子個數(shù)為C則至少C-1個箱子是超過一半容量的(因算法不可能會得出同時兩個箱子少于一半容量,否則算法會將這兩個箱子合并)所以為2近似算法?！陡呒壦惴ㄔO計與分析》期末試卷（試卷2）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題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ī)劃轉化為標準型：B.C.D.線性規(guī)劃問題如下，其對偶問題為：B.D.對于隨機算法的描述，以下描述錯誤的是:A.算法運算很快B.算法有一定的概率產(chǎn)生錯誤的結果C.算法的輸出是確定的D.隨機快速排序的期望時間復雜度為O(nlogn)在隨機快速排序算法中，設S(i)表示集合S中階為i的元素，下面描述錯誤的是（注：j>i）:只有S(i)和S(j)這兩個元素其一被選為主元素的時候，他們才進行比較當元素S(k)(i<k<j)被選為主元素時，S(i)和S(j)肯定不會進行比較S(i)和S(j)比較的概率為：pij=2/(j-i+1)當元素S(k)(k>j)被選為主元素時，S(i)和S(j)肯定會進行比較以下對規(guī)約的描述錯誤的是：，如果B是P問題，則A一定也是P問題，如果A是NPC問題，則B一定也是NPC問題如果A問題可以歸約為B問題，則A問題和B問題必須是一一對應關系規(guī)約函數(shù)必須是多項式時間復雜度的函數(shù)以下問題不是NPC問題的是：A.小數(shù)背包問題B.最大團問題C.旅行商問題D.整數(shù)規(guī)劃問題在團問題的NP難證明過程中,以下說法錯誤的是：3合取范式可以歸約為團問題歸約的過程中，3合取范式會歸約為一個特殊的圖，所以我們只能說明這個特殊的圖的團問題是NP難的，而無法證明所有的圖的團問題都是NP難的在規(guī)約的過程中,一個子句對應一組頂點，對于任意兩個在不同組的頂點，如果滿足“這兩個頂點不是‘否’的關系”這一條件，就用一條邊連接如果3合取范式如果有k個子句，則需要證明圖中有規(guī)模為k的團針對集合覆蓋問題，設wi為子集Si的權重，xi=0表示沒有選中子集Si，xi=1表示選中子集Si。則集合覆蓋問題建模成整數(shù)規(guī)劃形式為（注：n為元素的個數(shù)，m為子集的個數(shù)）：B.C.D.下面對旅行商問題（滿足三角不等式）的近似算法描述錯誤的是：算法的基本思想是：生成最小生成樹，按對樹進行先序遍歷的順序訪問節(jié)點。最小生成樹的總代價小于等于旅行商回路的總代價對T進行按先序往返遍歷，其總代價小于等于2倍的旅行商回路的總代價算法的總代價大于等于對T進行按先序往返遍歷的總代價下面對在線算法和離線算法比較，以下描述錯誤的是：即使數(shù)據(jù)在計算時都已知，也可以采用在線算法來達到更好的結果在線算法通常是近似算法通常通過和離線最優(yōu)算法的比較來判斷在線算法的好壞，如果在線算法的代價Con和離線算法的代價Coff有關系，則稱在線算法在實例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)解或求解過程那些目前在禁忌表的解或者求解過程是無條件被禁止的進入禁忌表的解或者求解過程在一定的時間后會被解禁禁忌表搜索每次迭代總是在前一次迭代的領域中進行搜索二、計算、建模題（共40分）設某指派問題的費用矩陣為：其中第i行表示第i個人被指派各個任務的費用，而第j列第j個任務被分配到各個人的費用。試用匈牙利法求最優(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ù)定義，選擇算子，交叉和變異操作（10分）三、算法設計題（共15分）1.0-1背包問題:設有n個物品,其重量為w1,w2,…,wn，價值為v1,v2,…,vn，背包的承重為C（wi<C）。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大。請用近似算法求解此問題(描述此算法的思路)，并計算此算法的復雜度和近似度?！陡呒壦惴ㄔO計與分析》期末試卷答案（答案）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）C，D，A，B，CC，D，C，A，BA，D，A，C，B二、計算、建模題（共40分）設某指派問題的費用矩陣為：其中第i行表示第i個人被指派各個任務的費用，而第j列第j個任務被分配到各個人的費用。試用匈牙利法求最優(yōu)指派，以及在最優(yōu)指派下的總費用。解：將每行減去最小值得到：每列減去最小值得到：將所有還沒有被劃線覆蓋的元素減去最小值由以上矩陣可知：任務3指派給人員1；任務1指派給人員3；任務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.歸約證明：設G=（V，E）為圖，另X=E，Si為頂點i所覆蓋邊的集合，F(xiàn)為Si的集合，則形成（X，F(xiàn)）的一個集合覆蓋問題3.1圖G具有大小為k的一個頂點覆蓋P，因P中所有點覆蓋圖G中所有的邊，所以P中點對應的Si必然覆蓋X中的所有元素，也就是Si成的集合S必然會覆蓋X中的所有邊，所以S是（X，F(xiàn)）的一個大小為k的集合覆蓋。3.2設S是（X，F(xiàn)）的一個大小為k的集合覆蓋，則S中所有的集合必然覆蓋X中的所有點，所以S所對應的點集合P必然覆蓋G中所有的點，且S是一個規(guī)模為k的集合。4）簡單描述如何用遺傳算法實現(xiàn)廣義旅行商問題的求解，描述要包含個體（染色體）設置，適應度函數(shù)定義，選擇算子，交叉和變異操作（10分）參考答案：設有m個城市群，每個城市群只要訪問其中一個城市即可，設T(i)代表第i個城市群中所有的城市1、染色體由頭部和身體組成，如下圖，其中頭部（從1到m）表示在訪問第i個城市群訪問的具體城市（如頭部的第i（1<=i<=m）個元素4，表示訪問了第i個城市群中的第4個城市），身體（從m+1到2m）表示對城市群訪問的順利。隨機初始化n個染色體。2、對n個染色體進行局搜索，即針對每個染色體，改變頭部的值，使得在此染色體城市群訪問順序下，對每個城市群選擇最優(yōu)的城市。計算局部搜索后每個染色體的適應度值（這里我使用路徑長度的倒數(shù)表示個體適應性）；3、使用輪盤選擇方式選擇個體，形成父染色體；4、按照交叉概率，對父染色體的身體部分進行兩兩交叉生成n個染色體；6、對這n個染色體的身體部分按照變異概率進行變異；7、判斷是否達到迭代次數(shù)，是，結束，返回最優(yōu)解；否，轉到第2步。三、算法設計題（共15分）0-1背包問題:設有n個物品,其重量為w1,w2,…,wn，價值為v1,v2,…,vn，背包的承重為C（wi<C）。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大。請問近似算法求解此問題，(描述此算法的思路)，并計算此算法的復雜度和近似度.參考答案:算法:1.將所有的物品按照性價比排列2.按順序考察物品，只要能夠裝入背包裝入此物品，得總價值為V3.求vk=max{vi:foralli}，如vk>V，則將背包內(nèi)的物品替換成物品k精確度:設最優(yōu)算法得出的總價值為Vopt，貪心算法得出的總價值為Vgreedy，設l為第一件未裝入背包的物品，因物品按照性價比排序，所以：Vopt<=Vgreedy+vl<=Vgreedy+vmax<=2Vgreedy所以為2近似算法。復雜度：第一步排序的復雜度為nlogn第二步裝物品的復雜度為n第三步的復雜度為n總復雜度為nlogn《高級算法設計與分析》期末試卷（試卷3）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）求解整數(shù)規(guī)劃，可通過先將整數(shù)規(guī)劃進行松弛，之后采用下面的哪種算法：動態(tài)規(guī)劃B.分支限界C.回溯D.貪心在近似算法中，可采用以下哪種算法：動態(tài)規(guī)劃B.分治C.回溯D.貪心對于弱若對偶性,以下表達正確的是，x為原問題（最大化）的解，y為對偶問題（最小化）的解：B.D.以上都不對線性規(guī)劃問題如下，其對偶問題為：B.D.下面描述正確的是：整數(shù)規(guī)劃問題是NPC問題，線性規(guī)劃問題是NP問題整數(shù)規(guī)劃問題是NPC問題，線性規(guī)劃問題是NPC問題整數(shù)規(guī)劃問題是NP問題，線性規(guī)劃問題是NPC問題整數(shù)規(guī)劃問題是NP問題，線性規(guī)劃問題是NP問題設A問題可以歸約到B問題，則以下說法錯誤的是：如果A問題為NPC問題，則B問題必為NPC問題A問題的任何一個實例x可以通過函數(shù)f轉化為B問題的一個實例，且f為多項式時間B問題的任何一個實例x也可以通過函數(shù)f’轉化為A問題的一個實例，且f’為多項式時間algoA代表A的算法，algoB代表B的算法，則algoB(f(x))=algoA(x)在團問題(圖G)規(guī)約為頂點覆蓋問題(圖)中,以下說法錯誤的是：設（u,v）為的任意邊，則（u，v）其中至少一個點不屬于G的團設（u,v）為的任意邊，則（u，v）其中至少一個點屬于的頂點覆蓋如果有兩個頂點u,v都不屬于的頂點覆蓋，則這兩個頂點一定屬于G的團圖G中有規(guī)模為k的團，當且僅當圖有規(guī)模為k的頂點覆蓋下面對子集和的近似算法描述錯誤的是：如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，則{x1,x2,x3,…,xi,xi+1}所有的子集和為。在計算過程中，為了減少子集和的規(guī)模，算法通過去除大于目標值的子集和，以及刪除相似子集和的方法實現(xiàn)如果算法不刪除相似的子集和，是可以得到精確的結果的子集和的近似算法只是一個多項式時間近似算法，而不是一個完全多項式時間的近似算法下面對旅行商問題（滿足三角不等式）的近似算法描述錯誤的是：算法的基本思想是：生成最小生成樹，按對樹進行后序遍歷的順序訪問節(jié)點。最小生成樹的總代價小于等于旅行商回路的總代價旅行商回路的總代價小于等于最小生成樹代價的2倍此近似算法是近似因子為2的近似算法隨機快速排序算法中，元素S(i)和元素S(j)進行比較的概率是多少（注：S為排序好的元素序列）？B.C.D.對于拉斯維加斯和蒙特卡洛算法描述錯誤的是:拉斯維加斯算法不一定獲得解,但如果獲得解一定是正確的蒙特卡洛算法可能給出錯誤解拉斯維加斯算法找到解得概率與算法執(zhí)行時間成正比隨機選擇屬于蒙特卡洛算法G=(V，E)為多重圖，C是最小割且|C|=k，以下描述錯誤的是：G中任意頂點的度大于等于k最小割即為最少的變數(shù)集合，除去這些邊數(shù)，原圖變成不連通隨機算法輸出最小割的概率大于2/n2下面對最小生成樹在線算法描述錯誤的是：最小生成樹在線算法是一種貪心算法算法復雜度為O（n2）算法競爭度為O（n）生成樹在線算法生成樹中第k長的邊長度小于等于2l/k，其中l(wèi)為最小生成樹的代價在租賣問題的在線算法中，b=2為購買價格，l<=3為天數(shù)，則所有的確定性算法如下表，其中Ai為第i天購買，Ii為滑雪場最后一天開放為第i天，現(xiàn)有隨機實例概率（I1=1/3,I2=2/3），以及隨機算法概率（A2=2/3，A3=1/3），則在此隨機實例下A2的競爭度，以及此隨機算法在實例I2的競爭度分別為：（4/3,5/3）B.（4/3,4/3）C.（5/3,4/3）D.（5/3,5/3）下面對蟻群系統(tǒng)算法（AntColonySystem）描述錯誤的是：采用利用和探索相結合，在利用時，選擇最優(yōu)路徑，探索時，按選擇概率選擇路徑全局更新只更新最優(yōu)路徑上的信息素局部更新時，信息素并不揮發(fā)在路徑選擇時，即考慮信息素，也考慮路徑長度二、計算、建模題（共40分）設某指派問題的效率矩陣為：其中第i行表示第i個人被指派各個任務的效率，而第j列第j個任務被分配到各個人的效率。試用匈牙利法求最大效率指派，以及在最大效率指派下的總費用。（10分）某市下設八個區(qū),下表給出救護車從一個區(qū)到另外一個區(qū)的車程時間(min)。該市擬建救護中心，要求各區(qū)離救護中心的車程時間必須在8min之內(nèi)（包括8min），問至少建多少個救護中心，建于何處？（只需要建立模型，不需要計算）證明0-1整數(shù)規(guī)劃問題是NPC問題（提示可以用3合取范式的可滿足性問題歸約為0-1整數(shù)規(guī)劃問題），需要描述一個具體的3合取范式實例轉換為具體的0-1整數(shù)規(guī)劃問題實例。（10分）簡單描述如何用遺傳算法對下面優(yōu)化問題進行求解，要求精度達到小數(shù)點后5位，描述要包含個體（染色體）設置，適應度函數(shù)定義，選擇算子，交叉和變異操作（10分）三、算法設計題（共15分）1.斯坦納最小樹的定義如下：給定無向連通圖G=(V,E)和邊的權重w:E→R。同時，給出集合R為V的子集，R?V，要求在圖中尋找一棵子樹T=(V′,E′)，其中V′?V，E′?E，使得R?V′，且∑e∈E′w(e)最小。在下面的左圖中，頂點（a,b,c,d）的斯坦納最小樹如右圖所示。斯坦納最小樹是NP難問題，請設計一個近似算法求解（10分），并計算近似因子（5分）?！陡呒壦惴ㄔO計與分析》期末試卷答案（試卷3）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）BDAAACDDADDBCBC二、計算、建模題（共40分）設某指派問題的效率矩陣為：其中第i行表示第i個人被指派各個任務的效率，而第j列第j個任務被分配到各個人的效率。試用匈牙利法求最大效率指派，以及在最大效率指派下的總費用。（10分）解：某市下設八個區(qū),下表給出救護車從一個區(qū)到另外一個區(qū)的車程時間(min)。該市擬建救護中心，要求各區(qū)離救護中心的車程時間必須在8min之內(nèi)（包括8min），問至少建多少個救護中心，建于何處？解：參考答案1:根據(jù)上表，如救護中心建在某區(qū)，其能覆蓋的區(qū)域如下：1：1，2，72：1，23：3，4，5，64：3，4，5，65：3，4，5，66：3，4，5，6，87：1，78：6，8設：其中1表示設在某區(qū)，0表示不設則建模為：參考答案2:建立圖：每個區(qū)域為一個頂點，如果區(qū)域之間的車程小于等于8min，則兩個頂點之間有邊，否則無邊，建立圖如下則原問題建模為求解最小覆蓋集問題證明0-1整數(shù)規(guī)劃問題是NPC問題（提示可以用3合取范式的可滿足性問題歸約為0-1整數(shù)規(guī)劃問題，需要描述一個具體的3合取范式實例轉換為具體的0-1整數(shù)規(guī)劃問題實例）。（10分）證:1.0-1整數(shù)規(guī)劃是NP問題:給定某個0-1整數(shù)規(guī)劃的解，很容易在二項式時間內(nèi)驗證這個解是否是0-1整數(shù)規(guī)劃的解，即只要驗證每個限制條件即可.2.歸約證明簡單描述如何用遺傳算法對下面優(yōu)化問題進行求解，要求精度達到小數(shù)點后5位，描述要包含個體（染色體）設置，適應度函數(shù)定義，選擇算子，交叉和變異操作（10分）解：a)需要將區(qū)間[-2,2]劃分4×105等份，因為218<4×105<219，所以編碼的長度應該設置為m=19比特，染色體x如下所示：b)適應度函數(shù)f(x)為目標函數(shù)c)采用輪盤的方式進行選擇，即pd)單點交叉和隨機選擇一個基因進行變異即可，但可能會產(chǎn)生非法解，對非法解可以直接去除。三、算法設計題（共15分）1.斯坦納最小樹的定義如下：給定無向連通圖G=(V,E)和邊的權重w:E→R。同時，給出集合R為V的子集，R?V，要求在圖中尋找一棵子樹T=(V′,E′)，其中V′?V，E′?E，使得R?V′，且∑e∈E′w(e)最小。在下面的左圖中，頂點（a,b,c,d）的斯坦納最小樹如右圖所示。斯坦納最小樹是NP難問題，請設計一個近似算法求解（10分），并計算近似因子（5分）。解：近似算法：1）基于原圖G，生成R={a,b,c,d}的一個完全圖GR，其中任意一條邊的權重為原圖G中的最短路徑；2）基于GR，生成最小生成樹TMST3）將TMST中的邊替換成原來的最短路徑T’MST4）如果替換成最短路徑后生成的圖不是樹，則需進一步生成最小生成樹，結果為近似算法的斯坦納樹TSMT。上面得出的近似算法是2-近似算法。由上面的流程可得：TSMT<T’MST<TMST<GR上的旅行商回路；設T*SMT是最優(yōu)斯坦納樹，根據(jù)此樹生成完全圖GSMT，則：GR上的旅行商回路<GSMT上的旅行商回路且GSMT上的旅行商回路<2*T*SMT（旅行商回路<先序回路<2*T*SMT）所以TSMT<2*T*SMT《高級算法設計與分析》期末試卷（試卷4）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共42分）下列描述，錯誤的是：線性規(guī)劃可在多項式時間內(nèi)求解；0-1規(guī)劃可在多項式時間內(nèi)求解；整數(shù)規(guī)劃采用的算法是分支限界線性規(guī)劃具有強對偶性設X?是線性規(guī)劃模型的最優(yōu)解，Y?是其對偶線性規(guī)劃模型的最優(yōu)解，則X?與Y?的關系是：CX?>BY?B.CX?=BY?C.CX?<BTY?D.CX?=BTY?在用原始-對偶算法求解頂點覆蓋的近似解時，會隨機選擇一條邊，并增加此邊的y值，直到此邊兩個頂點中，某個頂點的約束條件等號約束成立，假設兩個頂點的約束條件的等號約束都成立，應該選擇哪個頂點加入頂點覆蓋集：兩個頂點都加入頂點覆蓋集，且和這兩頂點相連的邊都需要從Ey中刪除第一個約束條件對應的頂點加入頂點覆蓋集，且和這兩頂點相連的邊都需要從Ey中刪除第一個約束條件對應的頂點加入頂點覆蓋集，但只和該頂點相連的邊從Ey中刪除第二個約束條件對應的頂點加入頂點覆蓋集，且和這兩頂點相連的邊都需要從Ey中刪除下圖從s到t的最大流是多少：A.8B.7C.6D.5下圖節(jié)點1，2,3,4，的中介中心性：1，2.5，2，1.5;1，1.5，2，1;0，1.5，3，1;0，2.5，3，1.5;關于規(guī)約有下面三種陳述，則：(b)對(a),(c)錯B.(a),(b)對，(c)錯C.(b),(c)對，(a)錯D.(a),(c)對，(b)錯以下問題不是NPC問題的是：團問題B.子集和問題C.最大流問題D.0-1整數(shù)規(guī)劃在滿足三角不等式的情況下，設G為完全圖，G’也是完全圖，且是G的子圖，以下的描述錯誤的是：圖G的最小生成樹的權重小于其旅行商回路的權重。圖G的旅行商回路的權重大于對其最小生成樹按照先序遍歷形成的回路。圖G的旅行商回路的權重小于等于其最小生成樹權重的2倍圖G′上的旅行商回路小于等于圖G的旅行商回路請計算下圖兩個無權圖的模塊度：20/196,36/196B.24/196,40/196C.40/196,36/196D.24/196,36/196下面對集合覆蓋的近似算法描述錯誤的是：簡單集合覆蓋的近似算法是貪心算法。該不等式成立是因為最優(yōu)集合覆蓋R*中包含所有的元素，且有可能對某個（些）元素包含多次。該不等式成立是因為貪心選擇。該等式成立，說明近似算法覆蓋所有的元素一次且僅一次。對于最小圓覆蓋，以下說法錯誤的是：在最小圓覆蓋算法中，當增加一個新的點pi時，如果點pi沒有被當前圓所覆蓋，則可以通過增大最小圓，將這個點包含在圓的內(nèi)部。最小圓覆蓋的隨機算法是為了避免落入最差的情況。最小圓覆蓋的最差情況下，復雜度為n3。最小圓覆蓋的期望復雜度為n。對于弗里瓦德算法，下面描述錯誤的是：弗里瓦德算法是蒙特卡洛算法。弗里瓦德算法需要生成一個包含0,1元素的隨機向量，如果生成的是全1元素，判斷A*B*r=C*r重新變成了判斷A*B=C，所以結果一定是正確的弗里瓦德算法得出正確解的概率大于等于1/2.隨機算法輸出最小割的概率大于2/n2對外匯兌換問題的在線算法描述錯誤的是：當Φ較大時（如>100）小數(shù)兌換能夠比整數(shù)兌換得到更好的競爭度（更好收益）；按照小數(shù)保守價格策略，如果第一天就達到最高的匯率，則收益最好；按照小數(shù)保守價格策略，最后一天之前兌換的比例是固定的（無論匯率如何變動）只要知道U和L的比值Φ，可得的在線算法在租賣問題的在線算法中，b=2為購買價格，l<=3為天數(shù)，則所有的確定性算法如下表，其中Ai為第i天購買，Ii為滑雪場最后一天開放為第i天，現(xiàn)有隨機實例概率（I2=1/3,I3=2/3），以及隨機算法概率（A2=2/3，A3=1/3），則在此隨機實例下A2的競爭度，以及此隨機算法在實例I3的競爭度分別為：（2/3,5/3）B.（4/3,4/3）C.（3/2,5/3）D.（5/3,5/3）二、計算、簡答題（共42分）求如下線性規(guī)劃的對偶問題(6分) 請用原始-對偶算法求圖中的頂點覆蓋近似解，寫出具體的流程，如流程中涉及隨機選擇某個節(jié)點或者某條邊，可做假設。（8分）LPA算法對圖進行社群劃分，設節(jié)點的遍歷順序為v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假設，8分)裝箱問題:設有n個物品,其大小為a1,a2,a3,...,an(0<ai≤1),現(xiàn)需要將這n個物品裝入大小為1的箱子,求裝完物品最少箱子的個數(shù)。此問題為NPC問題，請設計一個近似算法求解此問題(給出算法的思路),并用算法來實現(xiàn)如下具體例子，最后計算算法的近似因子(ρ)。例子:10個物品其大小分別為{0.4,0.8,0.5,0.1,0.7,0.6,0.1,0.4,0.2,0.2}（10分）集和對半分問題：給出一個正整數(shù)的集合{a1,a2,…,an}，問是否可以將集合的元素分成兩部分P和Q，使得P集合中所有元素之和等于Q集合中所有元素之和。1）請證明該問題是NPC問題（注：PPT上的所有NPC問題都認為是已知的）；2）請設計一個近似算法求解集合對半分問題（給出思路和流程即可）。（10分）三、算法設計題（共16分）1.廣義旅行商問題：是指某些城市只要訪問其中任意一個即可。如有n個城市，某采購員需要采購m(m<n)件物品，每個城市剛好提供一件物品，所以存在某些城市提供相同的物品，因此，采購員只要訪問這些城市中的一個即可。請用遺傳算法實現(xiàn)廣義旅行商問題的求解，算法設計要包含個體(染色體)設置，適應度函數(shù)定義，選擇算子，交叉和變異操作。。《高級算法設計與分析》期末試卷答案（試卷4）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，