工作總結(jié)與計劃西安交通大學(xué)計算機(jī)教學(xué)試驗中心

1、HPM&S活動活動14 Tourist Town 高效能建模與仿真研究小組2011年10本PPT的材料改編自Really Hard Problems-IntractabilityHPM&S 主要內(nèi)容主要內(nèi)容l旅行城鎮(zhèn)問題描述l一般解決方案l計算思維及問題擴(kuò)展l計算機(jī)求解復(fù)雜性及研究進(jìn)展l結(jié)論l對問題的進(jìn)一步思考l參考文獻(xiàn)HPM&S1. 1. 旅游城鎮(zhèn)問題描述旅游城鎮(zhèn)問題描述l問題右圖是旅游城市的地圖。冰激凌銷售車停在街道的拐角處出售冰激凌給游客。 我們想放置一些銷售車，使得每個人可以至多走一個街道的距離，通過走到街道的終端來到達(dá)一個銷售點。

2、 l目標(biāo)問題是需要多少個銷售車，以及這些銷售車應(yīng)該放在哪些十字路口？HPM&S2. 2. 一般解決方案一般解決方案l嘗試法隨機(jī)的放置一個空心籌碼在一個交叉路口，代表冰激凌銷售車，然后放置實心籌碼在附近的交叉路口，這樣游客就能買到冰激凌不斷的重復(fù)上述過程就能找到一種配置方案l分解組合法把旅游城鎮(zhèn)圖拆分成若干個小地圖，分解的原則是保證每個小地圖只需要一個冰激凌銷售車，同時將小地圖用連線拼在一起構(gòu)成旅游城鎮(zhèn)圖不斷的重復(fù)上述過程就能找到一種配置方案l問題安置油箱、井、救火中心等等HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“窮舉”算法思路考慮所有的放置冰激凌銷售車的可能

3、情況，然后檢驗?zāi)姆N是最好的過程。 1.如果有1個冰激凌車，在26個交叉路口放置一個冰激凌銷售車有26種放置方法，然后驗證，將有26種可能性要驗證。 2.如果有2個冰激凌車，先放置第一輛，然后在剩余的25個地方放置第二輛，將有26*25種可能性要驗證。 3.同理，如果有三輛，將有26*25*24種可能性要驗證。 4.同理，如果有優(yōu)點：問題規(guī)模不是很大時，很快的找出配置方案缺點：花費(fèi)大量的時間,效率低 HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“窮舉”算法偽代碼 Exhaustion()/狀態(tài)A(a1,a2,a26)代表每個交叉路口是否放置冰激凌/銷售車，如果為1代表放置

4、，如果為0代表沒有放置 for A(a1,a2,a26) from 00000 to 111.111 If 狀態(tài)A(a1,a2,a26) 滿足檢驗條件then 輸出問題的解； HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“窮舉”算法算法應(yīng)用 一名貨運(yùn)司機(jī)要把貨物從甲地運(yùn)往加乙地，從甲地到乙地公路從橫交錯，那么如何選擇行走路線，才能最快將貨物運(yùn)到目的地呢？一名銷售員要到若干個城市去洽談業(yè)務(wù)，已知任兩個城市之間的距離，請為其設(shè)計一個旅行線路，使得他從某一城市出發(fā)恰好經(jīng)過每個城市一次，最后回到出發(fā)城市。要求所走的路線最短。給定圖G=（V，E），找頂點數(shù)最少的V的子集C， 使得

5、E中每條邊的兩端至少有一個屬于與C。 HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“貪婪”算法思路考慮把第一輛銷售車放在連接最多街道數(shù)目的交叉點處，第二輛放在下一個類似的交叉點處，如此類推。缺點：不能保證得到最優(yōu)解優(yōu)點：效率高 HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“貪婪”算法偽代碼Greedy(C) /C是問題的輸入集合即候選集合 S=; /初始解集合為空集While(not solution(S) /集合S沒有構(gòu)成問題的一個解 X=select(C); /在候選集合中做貪心選擇If feasible(S,x) /判斷集合S中加入x后的解

6、是否可行S=S+x;C=C-x;Return S;HPM&S3. 3. 計算思維及問題擴(kuò)展計算思維及問題擴(kuò)展l“貪婪”算法算法應(yīng)用工作人員去做 n 件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？給定一個載重為M的背包，及N個重量為wi、價值為Pi的物體，1=i=n,要求把物體裝滿背包，且使得背包內(nèi)的物體價值最大，這類問題稱為背包問題。某地區(qū)有若干主要城市，現(xiàn)在要修建一些高速公路將它們連起來，使得從任一城市可經(jīng)過高速公路直接或間接地到達(dá)另一城市。假定已經(jīng)知道任兩城市間修建成本，那么如何修建高速公路網(wǎng)，才能使得總的成本最小？HPM&am

7、p;S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l計算機(jī)求解復(fù)雜性復(fù)雜性問題支配集問題是一個NP完全問題（non-eterministic polynomial-time complete）-多項式復(fù)雜程度的非確定性問題。這類問題出現(xiàn)在不同領(lǐng)域：布爾邏輯，圖論，算術(shù)，網(wǎng)絡(luò)設(shè)計，集合與劃分，排序與調(diào)度，數(shù)學(xué)程序設(shè)計，代數(shù)與數(shù)論，自動機(jī)與語言理論，程序優(yōu)化，生物學(xué)，化學(xué)，物理。HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l計算機(jī)求解復(fù)雜性多項式時間復(fù)雜度經(jīng)典P問題，一般復(fù)雜度為O(nK)一個圖中任意兩點最短距離的 Dijkstra算法指派

8、問題（賦權(quán)匹配問題）Kuhn算法；排序、查找問題HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l計算機(jī)求解復(fù)雜性NP問題NP是一大類判定問題，其準(zhǔn)確含義是可在一種假想的機(jī)器非確定型Turing機(jī)上在多項式時間內(nèi)可求解的問題，或者說可由非確定型算法在多項式時間可解。NP完全問題（NPC）最難的NP問題（超級NP問題）所有NP問題都可規(guī)約為NP完全問題HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l計算機(jī)求解復(fù)雜性NP完全問題（NPC）如果解決了此類問題，則所有NP問題都可以被解決1972年 karp給出了標(biāo)準(zhǔn)化的驗證方式，證

9、明21個NP完全問題是同復(fù)雜度，包括哈密頓回路問題，經(jīng)銷商問題NP-hard尋找國際象棋或圍棋最佳走法 一些指數(shù)級問題HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l計算機(jī)求解復(fù)雜性可能的關(guān)系HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展1970年左右,Cook發(fā)現(xiàn)了一些組合優(yōu)化問題可在多項式時間內(nèi)相互轉(zhuǎn)化,如果其中一個是P問題,那么其他問題也屬于P問題,反之亦然. 目前已證明有幾千個組合優(yōu)化問題包含在其中。近年，任意大數(shù)質(zhì)數(shù)判斷問題被證明為一個多項式問題HP LAB的 Vinay Deolalikar 教授宣布

10、于公元2010年8月6日證明了P!=NP，在他的主頁上，證明過程已經(jīng)公布。HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展盡管目前沒人能給出一個令人信服的證明，但人們普遍傾向于認(rèn)為 P!=NP.主要原因 ?（1）基于NP-完全理論，人們發(fā)現(xiàn)大量的組合優(yōu)化問題（幾千個?。┯兄粯拥碾y解性，一個可以多項式求解，則所有的問題可多項式求解。而沒人能給出任一個NP-完全問題的多項式時間算法；（2）如果P=NP， 這個世界與我們所想象的大不一樣！ 當(dāng)然，P是否等于NP尚沒有最后定論，需要解決它需要新的重大的突破。HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研

11、究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展近似算法如何求解NPC，NP-hard問題：對小規(guī)模問題，利用指數(shù)時間復(fù)雜性算法限制于一些特殊情況，求子問題的最優(yōu)解。譬如對最大獨(dú)立集問題， 如果限制考慮平面圖（或二部圖）的話,可以在多項式時間內(nèi)求解利用啟發(fā)式算法（heuristic），求問題的一個可行解。如貪婪算法，遺傳算法、模擬退火、Local search、分支定界等等。(參考文獻(xiàn)6)設(shè)計多項式時間近似算法（Approximation Algorithms）。（參考文獻(xiàn)1，pp：633-652）HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展近似算法對

12、于NPC， NP-hard問題，啟發(fā)式算法與近似算法（Approximation Algorithm）的主要區(qū)別在于： 前者無法在理論上給出所求的解與真正最優(yōu)解的差距（即算法有多好，或多壞），一般僅通過數(shù)值模擬來判定算法好壞。后者強(qiáng)調(diào)對所給問題的任一實例，在多項式時間內(nèi)求出一個可行解，該解所對應(yīng)的目標(biāo)函數(shù)值與最優(yōu)值的偏差在理論上有充分的保證（需要給出理論上嚴(yán)格的證明）HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展啟發(fā)式算法根據(jù)定理，圖的每個極大獨(dú)立集均為一個極小支配集，而根據(jù)定義，圖的最小支配集也是極小支配集，故可以把圖的極大獨(dú)立集中基數(shù)最少的點集

13、近似作為圖的最小支配集，而要找出極大獨(dú)立集中基數(shù)最少的點集，可以按啟發(fā)式規(guī)則實現(xiàn)。HPM&S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展啟發(fā)式算法對于圖G=，逆序啟發(fā)式算法可描述為：步驟步驟1 1：將V中的頂點按頂點度數(shù)從大到小逆序排列成點集V，全部頂點設(shè)置為未標(biāo)號；步驟步驟2 2：取中V第一個頂點，若該點已經(jīng)標(biāo)號，則在V刪除該點，轉(zhuǎn)至步驟3:否則，將該點標(biāo)號為1，并將與之相關(guān)聯(lián)且未標(biāo)號的頂點標(biāo)號為0，在V刪除該點；步驟步驟3 3：若V為空，轉(zhuǎn)至步驟4；否則，轉(zhuǎn)至步驟2；步驟步驟4 4：取標(biāo)號為1的頂點作為支配點，把這些點組成的點集為最小支配集。HPM&a

14、mp;S4. 4. 計算機(jī)求解復(fù)雜性及研究進(jìn)展計算機(jī)求解復(fù)雜性及研究進(jìn)展l研究進(jìn)展啟發(fā)式算法禁忌搜索(Tabu Search，TS)是另一個著名的啟發(fā)式搜索算法，在搜索過程中可以接受劣解，使得Ts在搜索過程中能夠跳出局部最優(yōu)解，進(jìn)而轉(zhuǎn)向其他區(qū)域進(jìn)行搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，從而高優(yōu)化效率，獲得更好的解或全局最優(yōu)解的概率也大大增加。 HPM&S5. 5. 結(jié)論結(jié)論l主要結(jié)論存在一類不能用常規(guī)數(shù)學(xué)方法求解的問題計算機(jī)求解這類問題的局限性HPM&S6. 6. 對問題的進(jìn)一步思考對問題的進(jìn)一步思考l如果P=NP被證明正確或者錯誤，將對計算機(jī)研究應(yīng)用領(lǐng)域帶來什么樣的

15、沖擊？l啟發(fā)式算法求解思路HPM&S7. 7. 參考文獻(xiàn)參考文獻(xiàn)lThomas H.Cormen Charles E.Leiserson著 潘金貴 顧鐵成 李成法 葉懋 譯，算法導(dǎo)論，機(jī)械工業(yè)出版，2006.l M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, San Francisco, W.H. Freedman and Co., 1979.lD. S. Hochbaum (eds) , Approximation Algorithms for NP-hard Problems, 世界圖書出版社（影印），1995.l V. V. Vazirani，Approximation Algorithms, Springer, 2002.l謝政，李建平，網(wǎng)絡(luò)算法與復(fù)雜性