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

PAGEPAGE6《高級(jí)算法設(shè)計(jì)與分析》期末試卷答案（試卷3）姓名：___________________學(xué)號(hào)：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)一、選擇題（每題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.歸約證明簡單描述如何用遺傳算法對(duì)下面優(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)生非法解，對(duì)非法解可以直接去除。三、算法設(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難問題，請(qǐng)?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，則