《高級算法設(shè)計(jì)與分析》試卷及答案 共4套

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