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

PAGEPAGE6《高級(jí)算法設(shè)計(jì)與分析》期末試卷答案（試卷1）姓名：___________________學(xué)號(hào)：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)一、選擇題（每題3分，共45分）BCBAB；DCAAD；BDACD二、計(jì)算、建模題（共40分）已知線性規(guī)劃問(wèn)題,其對(duì)偶問(wèn)題的最優(yōu)解為*=(y1,y2,y3,y4)=(0,0,4,4)，試用對(duì)偶的互補(bǔ)松弛性求原問(wèn)題的最優(yōu)解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0解：此問(wèn)題的對(duì)偶問(wèn)題為將(0,0,4,4)帶入約束條件，約束條件都為等式，無(wú)法得出解因y3和y4大于0，所以x1+x2=5x1+2x2=6解得x1=4；x2=1某市下設(shè)八個(gè)區(qū),下表給出救護(hù)車從一個(gè)區(qū)到另外一個(gè)區(qū)的車程時(shí)間(min)。該市擬建救護(hù)中心，要求各區(qū)離救護(hù)中心的車程時(shí)間必須在8min之內(nèi)（包括8min），問(wèn)至少建多少個(gè)救護(hù)中心，建于何處（只需要建立模型，無(wú)需計(jì)算）？（10分）解：參考答案1:根據(jù)上表，如救護(hù)中心建在某區(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設(shè)：其中1表示設(shè)在某區(qū)，0表示不設(shè)則建模為：參考答案2:建立圖：每個(gè)區(qū)域?yàn)橐粋€(gè)頂點(diǎn)，如果區(qū)域之間的車程小于等于8min，則兩個(gè)頂點(diǎn)之間有邊，否則無(wú)邊，建立圖如下則原問(wèn)題建模為求解最小覆蓋集問(wèn)題參考3合取范式歸約團(tuán)問(wèn)題的過(guò)程，證明最大獨(dú)立集問(wèn)題是NPC問(wèn)題。最大獨(dú)立集是給一無(wú)向圖，找出一個(gè)點(diǎn)集，使得任意兩點(diǎn)之間都沒(méi)有連邊，這個(gè)點(diǎn)集就是獨(dú)立集。而點(diǎn)最多的獨(dú)立集，就是最大獨(dú)立集。(10分)參考答案1:1..最大獨(dú)立集是NP問(wèn)題:給定某個(gè)獨(dú)立集，很容易在二項(xiàng)式時(shí)間內(nèi)驗(yàn)證獨(dú)立集合中的點(diǎn)是否在原圖中存在連接.2.規(guī)約：將每個(gè)子句對(duì)應(yīng)于一組節(jié)點(diǎn)組，其各個(gè)節(jié)點(diǎn)之間都有連線，而各組之間只有相互取反的節(jié)點(diǎn)有連線（剛好和團(tuán)的規(guī)約相反），如3合取范式規(guī)約為：則取使得3合取范式為1的一個(gè)解，則必然存在一組獨(dú)立集，如上例中（x反，z）使得3合取范式成立，則圖中存在（x反，z，z，x反）的4各元素獨(dú)立集。反之，如果圖中國(guó)存在4個(gè)元素的獨(dú)立集，對(duì)著4個(gè)元素對(duì)應(yīng)的變量賦值為1，則3合取范式成立。參考答案2（通過(guò)頂點(diǎn)覆蓋可歸約為最大獨(dú)立集問(wèn)題）設(shè)G=(V，E)為圖，k為頂點(diǎn)覆蓋集，則|V|-k為圖G的獨(dú)立集。對(duì)于任意兩個(gè)頂點(diǎn)不屬于頂點(diǎn)覆蓋集，則這兩個(gè)頂點(diǎn)必然沒(méi)有邊，所有這些頂點(diǎn)兩兩之間都沒(méi)有邊，所以這些頂點(diǎn)形成了獨(dú)立集(V-k)。同理，如果存在(V-k)的最大獨(dú)立集，取獨(dú)立集外的任意一個(gè)點(diǎn)，這個(gè)點(diǎn)至少存在一條邊和頂點(diǎn)覆蓋集中的一個(gè)點(diǎn)連接。所有的這些點(diǎn)將覆蓋:1.這些點(diǎn)和獨(dú)立集的邊(這些邊是獨(dú)立的，也就是說(shuō)不存在兩個(gè)頂點(diǎn)覆蓋同一條邊);2.所有的邊(因?yàn)楠?dú)立集沒(méi)有邊，顯然，所有獨(dú)立集外的點(diǎn)將覆蓋所有的獨(dú)立集外的邊，即所有的邊)4）簡(jiǎn)單描述如何用遺傳算法實(shí)現(xiàn)旅行商問(wèn)題的求解，描述要包含個(gè)體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）解：程序流程（參考答案）1、根據(jù)輸入的城市初始化個(gè)體（染色體），并生成n個(gè)個(gè)體，即初始種群；2、計(jì)算每個(gè)基因序列的適應(yīng)性，適應(yīng)性與路徑長(zhǎng)度成反比（這里我使用路徑長(zhǎng)度的倒數(shù)表示個(gè)體適應(yīng)性）；3、使用輪盤選擇方式選擇個(gè)體，形成父本；4、按照交叉概率，對(duì)父本兩兩進(jìn)行交叉生成n個(gè)個(gè)體；6、對(duì)這n個(gè)個(gè)體按照變異概率進(jìn)行變異；7、判斷是否達(dá)到迭代次數(shù)，是，結(jié)束，返回最優(yōu)解；否，轉(zhuǎn)到第2步。三、算法設(shè)計(jì)題（共15分）裝箱問(wèn)題:設(shè)有n個(gè)物品,其大小為a1,a2,a3,…,an(0<ai<=1),現(xiàn)需要將這n個(gè)物品裝入大小為1的箱子,求裝完物品最少的箱子個(gè)數(shù)。此問(wèn)題為NPC問(wèn)題，請(qǐng)用近似算法求解(給出此算法的思路,并用算法來(lái)實(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)參考答案:算法:將物品按順序放入箱子,具體放法如下:如果第一個(gè)箱子能夠放此物品,則放,否則考察一下一個(gè)箱子,如果已打開(kāi)的所有箱子都不能放,則新開(kāi)一個(gè)箱子.應(yīng)用