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

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