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

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