《高級算法設(shè)計與分析》試卷4

PAGEPAGE6《高級算法設(shè)計與分析》期末試卷（試卷4）姓名：___________________學(xué)號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學(xué)號一、選擇題（每題3分，共42分）下列描述，錯誤的是：線性規(guī)劃可在多項式時間內(nèi)求解；0-1規(guī)劃可在多項式時間內(nèi)求解；整數(shù)規(guī)劃采用的算法是分支限界線性規(guī)劃具有強(qiáng)對偶性設(shè)X?是線性規(guī)劃模型的最優(yōu)解，Y?是其對偶線性規(guī)劃模型的最優(yōu)解，則X?與Y?的關(guān)系是：CX?>BY?B.CX?=BY?C.CX?<BTY?D.CX?=BTY?在用原始-對偶算法求解頂點覆蓋的近似解時，會隨機(jī)選擇一條邊，并增加此邊的y值，直到此邊兩個頂點中，某個頂點的約束條件等號約束成立，假設(shè)兩個頂點的約束條件的等號約束都成立，應(yīng)該選擇哪個頂點加入頂點覆蓋集：兩個頂點都加入頂點覆蓋集，且和這兩頂點相連的邊都需要從Ey中刪除第一個約束條件對應(yīng)的頂點加入頂點覆蓋集，且和這兩頂點相連的邊都需要從Ey中刪除第一個約束條件對應(yīng)的頂點加入頂點覆蓋集，但只和該頂點相連的邊從Ey中刪除第二個約束條件對應(yīng)的頂點加入頂點覆蓋集，且和這兩頂點相連的邊都需要從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ān)于規(guī)約有下面三種陳述，則：(b)對(a),(c)錯B.(a),(b)對，(c)錯C.(b),(c)對，(a)錯D.(a),(c)對，(b)錯以下問題不是NPC問題的是：團(tuán)問題B.子集和問題C.最大流問題D.0-1整數(shù)規(guī)劃在滿足三角不等式的情況下，設(shè)G為完全圖，G’也是完全圖，且是G的子圖，以下的描述錯誤的是：圖G的最小生成樹的權(quán)重小于其旅行商回路的權(quán)重。圖G的旅行商回路的權(quán)重大于對其最小生成樹按照先序遍歷形成的回路。圖G的旅行商回路的權(quán)重小于等于其最小生成樹權(quán)重的2倍圖G′上的旅行商回路小于等于圖G的旅行商回路請計算下圖兩個無權(quán)圖的模塊度：20/196,36/196B.24/196,40/196C.40/196,36/196D.24/196,36/196下面對集合覆蓋的近似算法描述錯誤的是：簡單集合覆蓋的近似算法是貪心算法。該不等式成立是因為最優(yōu)集合覆蓋R*中包含所有的元素，且有可能對某個（些）元素包含多次。該不等式成立是因為貪心選擇。該等式成立，說明近似算法覆蓋所有的元素一次且僅一次。對于最小圓覆蓋，以下說法錯誤的是：在最小圓覆蓋算法中，當(dāng)增加一個新的點pi時，如果點pi沒有被當(dāng)前圓所覆蓋，則可以通過增大最小圓，將這個點包含在圓的內(nèi)部。最小圓覆蓋的隨機(jī)算法是為了避免落入最差的情況。最小圓覆蓋的最差情況下，復(fù)雜度為n3。最小圓覆蓋的期望復(fù)雜度為n。對于弗里瓦德算法，下面描述錯誤的是：弗里瓦德算法是蒙特卡洛算法。弗里瓦德算法需要生成一個包含0,1元素的隨機(jī)向量，如果生成的是全1元素，判斷A*B*r=C*r重新變成了判斷A*B=C，所以結(jié)果一定是正確的弗里瓦德算法得出正確解的概率大于等于1/2.隨機(jī)算法輸出最小割的概率大于2/n2對外匯兌換問題的在線算法描述錯誤的是：當(dāng)Φ較大時（如>100）小數(shù)兌換能夠比整數(shù)兌換得到更好的競爭度（更好收益）；按照小數(shù)保守價格策略，如果第一天就達(dá)到最高的匯率，則收益最好；按照小數(shù)保守價格策略，最后一天之前兌換的比例是固定的（無論匯率如何變動）只要知道U和L的比值Φ，可得的在線算法在租賣問題的在線算法中，b=2為購買價格，l<=3為天數(shù)，則所有的確定性算法如下表，其中Ai為第i天購買，Ii為滑雪場最后一天開放為第i天，現(xiàn)有隨機(jī)實例概率（I2=1/3,I3=2/3），以及隨機(jī)算法概率（A2=2/3，A3=1/3），則在此隨機(jī)實例下A2的競爭度，以及此隨機(jī)算法在實例I3的競爭度分別為：（2/3,5/3）B.（4/3,4/3）C.（3/2,5/3）D.（5/3,5/3）二、計算、簡答題（共42分）求如下線性規(guī)劃的對偶問題(6分) 請用原始-對偶算法求圖中的頂點覆蓋近似解，寫出具體的流程，如流程中涉及隨機(jī)選擇某個節(jié)點或者某條邊，可做假設(shè)。（8分）LPA算法對圖進(jìn)行社群劃分，設(shè)節(jié)點的遍歷順序為v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假設(shè)，8分)裝箱問題:設(shè)有n個物品,其大小為a1,a2,a3,...,an(0<ai≤1),現(xiàn)需要將這n個物品裝入大小為1的箱子,求裝完物品最少箱子的個數(shù)。此問題為NPC問題，請設(shè)計一個近似算法求解此問題(給出算法的思路),并用算法來實現(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問題都認(rèn)為是已知的）；2）請設(shè)計一個近似算法求解集合對半分問題（給出思路和流程即可）。（10分）三、算法設(shè)計題（共16分）1.廣義旅行商問題：是指某些城市只要訪問其中任意一個即可。如有n個城市，某采購