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

PAGEPAGE6《高級算法設計與分析》期末試卷答案（試卷4）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共42分）B，D，A，A，C；D，C，B，B，D；A，B，D，C二、計算、簡答題（共42分）求如下線性規(guī)劃的對偶問題(6分) 請用原始-對偶算法求圖中的頂點覆蓋近似解，寫成具體的流程，如流程中涉及隨機選擇某個節(jié)點或者某條邊，可做假設。（8分）解：答案做參考，隨機選擇的邊不一樣，導致過程不相同和結果不一致。LPA算法對圖進行社群劃分，設節(jié)點的遍歷順序為v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假設，8分)答：各個節(jié)點v4，v6，v1，v3，v7，v10，v8，v2，v9，v5的標簽為第一輪后：5，5，3，3，9，9，9，3，9，5第二輪后：5，5，3，3，9，9，9，3，9，5結束裝箱問題:設有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分）參考答案:算法:將物品按順序放入箱子,具體放法如下:如果第一個箱子能夠放此物品,則放,否則考察一下一個箱子,如果已打開的所有箱子都不能放,則新開一個箱子。應用算法得出結果如下:?箱子1:0.4，0.5，0.1?箱子2:0.8，0.1?箱子3:0.7，0.2?箱子4:0.6，0.4?箱子5:0.2設C?為最優(yōu)個數(shù),此算法得出的箱子個數(shù)為C。則至少C?1個箱子是超過一半容量的(因算法不可能會得出同時兩個箱子少于一半容量,否則算法會將這兩個箱子合并)，可得:集和對半分問題：給出一個正整數(shù)的集合{a1,a2,…,an}，問是否可以將集合的元素分成兩部分P和Q，使得P集合中所有元素之和等于Q集合中所有元素之和。1）請證明該問題是NPC問題（注：PPT上的所有NPC問題都認為是已知的）；2）請設計一個近似算法求解集合對半分問題。（10分）答：1）集合對半分問題就是求子集和問題，即求（a1+a2+…+an）/2的子集和。因子集和是NPC問題，所以集合對半分也是NPC問題。2）可以按照ppt上的消除相近元素的方法求解近似結三、算法設計題（共16分）1.廣義旅行商問題：是指某些城市只要訪問其中任意一個即可。如有n個城市，某采購員需要采購m(m<n)件物品，每個城市剛好提供一件物品，所以存在某些城市提供相同的物品，因此，采購員只要訪問這些城市中的一個即可。請用遺傳算法實現(xiàn)廣義旅行商問題的求解，算法社交要包含個體(染色體)設置，適應度函數(shù)定義，選擇算子，交叉和變異操作。參考答案:設有m個城市群，每個城市群只要訪問其中一個城市即可，設T(i)代表第i個城市群中所有的城市。1)染色體由頭部和身體組成，如圖20，其中頭部(從1到m)表示在訪問第i個城市群具體城市(如頭部的第i(1≤i≤m)個元素4，表示訪問了第i個城市群中的第4個城市)，身體(從m+1到2m)表示對城市群訪問的順利。隨機初始化n個染色體。圖：廣義旅行商遺傳算法2)對n個染色體進行局搜索，即針對每個染色體，改變頭部的值，使得在此染色體城市群訪問順序下，對每個城市群選擇最優(yōu)的城市。計算局部搜索后每個染色體的適應度值(這里使用路徑長度的倒數(shù)表示個體適應性)。3)使用輪盤選擇方式選擇個體，形成父染色體。4)按照交叉概率