《以「旅行推销员问题」为例,浅谈如何利用计算机解题》由会员分享，可在线阅读，更多相关《以「旅行推销员问题」为例,浅谈如何利用计算机解题（42页珍藏版）》请在金锄头文库上搜索。
1、以旅行推銷員問題為例，淺談 如何利用計算機解題,唐傳義 教授 cytangcs.nthu.edu.tw 國立清華大學資訊工程系,2,給定4個城市的相互距離,3,最小展開樹問題 尋找一個將四個城市最經濟的聯結,4,旅行推銷員問題 Traveling Salesman Problem (TSP) 尋找一個從(1)出發，回到(1)的最短走法,1,2,3,4,12,1,8,10,3,2,5,TSP是一個公認的難題 NP-Complete,意義：我們現在無法對所有輸入找到一個有效率的解法 避免浪費時間尋求更佳的解法 Ref: Horowitz & Sahni, Fundamentals of Compu
2、ter Algorithms, P528.,6,2n相當可怕,像satisfiabilibility problem 目前只有exponential algorithm，還沒有人找到polynomial algorithm (你也不妨放棄！) 這一類問題是NP-Complete Problem Garey & Johnson “Computers & Intractability”,7,生物應用的計算需求,數學問題,工具程式,Computational Biology,Database,Added Value Database,抽象化,算法設計,8,例 Physical Mapping of
3、DNA,P1 P2 P1 P2 C2 1 1 C1 1 0 C1 1 0 C2 1 1 C3 0 1 C3 0 1 consecutive 1 propety False negative False positive,C1,C2,C3,P1,P2,9,A clones x probes matrix with added column p6*.,P1,P6,P2,P5,P3,P4,2,2,0,3,1,2,2,2,2,2,4,4,3,4,3,TSP graph for matrix of Table,10,旅行推銷員問題是許多排程應用的 核心問題 （航運排程） 有許多變型 平面TSP 幾何TS
4、P（滿足三角不等式） 不對稱TSP,*,*,*,*,*,*,*,2,3,4,(1),(3),(2),(1),(2),2,4,11,窮舉法（Enumerating）,(想想看什麼問題不能窮舉解？)加分題! 旅行推銷員問題： 3!走法 (n-1)! 最小展開樹問題： 16種樹 n(n-2) Cayleys Thm. Ref: Even, Graph Algorithms, PP2628,12,4,1,1,4,3,2,12,Labeled tree Number sequence One-to-One Mapping N個nodes的labeled tree可以用一個 長度N-2的number se
5、quence來表達。 Encoding: Data Compression.,13,Labeled treeNumber sequence,在每一個iteration裡，切除目前所有leaves中 編號最小的node及其edges，記錄切點，切到 只剩一條edge為止。 例. Prune-sequence:7,4,4,7,5(切點) Label最大者必在最後的edge. 每個node原先的degree數=此node在 Prune-sqeuence中出現的次數+1.,2,3,4,7,1,5,6,14,Number sequenceLabeled tree,Prune-sequence: 7,4,
6、4,7,5,每一個iteration裡，選擇degree為1且編號最小的node，連接prune-sequence中 相對的node，之後兩個nodes的degree均減1. Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 6 Iteration 5,1,7,1,7,2,4,1,7,2,4,3,1,7,4,1,7,4,3,2,1,7,4,3,2,6,5,3,2,5,6,15,貪心法（Greedy）,旅行推銷員問題 x 最小展開樹問題 o 兩種貪心都成功： 1. 將邊由小到大加入，有迴圈即丟掉 2. 將樹從一點開始，最經濟向外擴
7、展,16,Minimal spanning tree Kruskala Algorithm,A,B,D,C,E,70,65,300,90,50,80,75,200,Begin T - null While T contains less than n-1 edges, the smallest weight, choose an edge (v, w) form E of smallest weight 【 Using priority queue, heap O (log n) 】, delete (v, w) form E. If the adding of (v, w) to T doe
8、s not create a cycle in T,【 Using union, find O (log m)】 then add (v, w) to T; else discard (v, w). Repeat. End. O (m log m) m = # of edge,17,做priority queue可以用 heap operation,O(log n) Initial O(n) Tarjan: Union & Find可以almost linear (Amortized) Correctness 如果不選最小edge做tree而得到minimal 加入最小edge會有cycle
9、Delete cycle中最大的edge會得到更小cost之tree (矛盾！),1,2,4,3,7,5,6,18,建spanning tree可以看做 spanning forest加link,1. 加 edge(2,3) 不合法 2. 加 edge(1,4) 合法 另一種看法： S1=1,2,3 S2=4,5 Edge的端點要在不同set Set的 Find, Union O(log n),1,3,2,4,5,19,Prims Algorithm,A,B,D,C,E,70,65,300,90,50,80,75,200,Step 1: Let x be any vertex in V. Le
10、t A = x and B = V - . Step 2: Select an edge (u, v) form E such that u in A, v in B and (u, v) has the smallest weight among edges between A and B. Step 3: Connect v to u in A. Let A = A + v and B = B v. Step 4: If B is empty, terminate and the resulting tree is a minimal spanning tree. Otherwise, g
11、o to Step 2. O(n2),20,考慮以下的城市做旅行推銷員問題,從(1)開始貪心 不成功！,1,4,2,3,100,1,15,2,3,8,1,2,3,4,1,2,3,100,21,一些常用的方法,貪 心 法（The Greedy Method） 各個擊破法（Divide-&-Conquer） 窮 舉 法（Enumerating） 樹狀搜尋法（Tree Searching Strategies） （Branch & Bound） 動態規畫法（Dynamic Programming） 近 似 法（Approximation）,22,動態規畫法 （Dynamic Programming）
12、,原則： 滿足遞迴關係 技巧： 利用空間換取時間 最簡單的例子： 算Fibonacci Number F (i) = F (i - 1) + F (i - 2) F (0) = F (1) = 1,23,樹狀搜尋法（Tree Searching Strategies） （Branch & Bound）,預估B, C, D以下的解，如果D的最樂觀 可能解，都比B以下的某解還差， 則D以下可以不搜尋 深藍！,A,B,C,D,24,近似解法（Approximation）,不期望最佳解 用效率高的方法去求合理解 該合理解與最佳解有可預期的倍數關係 可以做如模擬退火法的其它解法的初始解or參考值 理論分
13、類 NPO complete MAX SNP hard PTAS http:/web.informatik.unibonn.de/IV/ Mitarbeiter/rick/WS9687/approxvortr/approxvortr.html,25,以幾何TSP為例 先做最小展開樹,26,挑出所有奇數degree的點,27,對他們做matching (Euler Graph),28,一筆畫,Minimal spanning tree 3/2 TSP 時間 n2.5,29,模擬自然界一些其它的隨機方法,模擬退火 神經計算 基因演算,30,模擬退火 回火 策略 Simulated-Annealin
14、g,Local maximal global maximal,Local maximal 不是 global maximal,難 題 ！,31,模擬退火法 (Simulated Annealing),procedure SIMULATED-ANNEALING begin INITIALIZE ( i start, c0, L0); k := 0; i := i start; repeat for l := 1 to Lk do begin GENERATE (j form Si); Greedy if f (j) random 0, 1) then I := j end; f (i) f (j
15、)比ck愈小愈有機會反Greedy但不要太離譜！ k := k +1; CALCULATE_ LENGTH (Lk); CALCULATE_ CONTROL (Lk); until stop criterion end;,32,TSP如何做？,從一個tour裡任取兩個edge,決定到底要不要用,取代,原則：通常還是貪心，偶而讓它反其道一下,33,模擬退火是一種隨機方法， 只能預設一個停止時間， 看天吃飯。 模擬退火中有許多參數， 要靠經驗或實驗。,34,Introduction Genetic Algorithms（基因計算）,Genetic Algorithms Artificial mec
16、hanisms of natural evolution. A robust search procedures and solving complex search problems. Disadvantage Low efficient if large problem space. Population homogeneous.,End,Begin,Encoding,Initialize population,Reproduction & Selection,Crossover,Mutation,Evaluate population,Termination criterion,Evaluate population,No,Ye
