以旅行推销员问题为例浅谈如何利用计算机解题.ppt
以旅行推銷員問題為例，淺談 如何利用計算機解題,唐傳義 教授 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 Computer 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 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 幾何TSP（滿足三角不等式） 不對稱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 sequence來表達。 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,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. 將樹從一點開始，最經濟向外擴展,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 does 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 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. Let 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, go 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）,原則： 滿足遞迴關係 技巧： 利用空間換取時間 最簡單的例子： 算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參考值 理論分類 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-Annealing,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)比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 mechanisms 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,Yes,35,The Eugenic Genetic Algorithm for TSP Crossover Phase,Sequence preserving crossover (SPX) Schemata is preserved as more as possible.,A=123|5748|69 B=934|5678|21,A=234|5678|91 B=936|5748|21,1,2,9,3,8,4,7,5,6,1,2,9,3,8,4,7,5,6,1,2,9,3,8,4,7,5,6,1,2,9,3,8,4,7,5,6,(a) A,(a) A,(a) B,(a) B,Crossover,36,Point mutation Inversion mutation Shift mutation,The Eugenic Genetic Algorithm for TSP Mutation Phase,(a) Point mutation,(b) Inversion mutation,(c) Shift mutation (right shift),37,分子計算（Molecular Computation）,Use (DNA) molecules to represent the data instances. Put the molecules into a tube, control the environments. The molecules will bind with each other. The most tightly binging is the minimum cost solution. Massive parallelism since the large number of molecules. 一莫耳 = 6.02 * 1023 Ref. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, Vol. 266, 11, 1994, PP1021-1024.,38,以TSP的特例Hamiltonian Path為例（也是難題）,問題：有無從0 6，長度為6，各vertex 恰走一遍的path?,O2 TATCGGATCGGTATATCCGA O3 GCTATTCGAGCTTAAAGCTA O4 GGCTAGGTACCAGCATGCTT O23 GTATATCCGAGCTATTCGAG O34 CTTAAAGCTAGGCTAGGTAC O3 (bar) CGATAAGCTCGAATTTCGAT O23 O34 GTATATCCGAGCTATTCGA GCTTAAAGCTAGGCTACGA TAAGCTCGAATTTCGAT O3 (bar),Fig.1. Directed graph. When Vin = 0 and Vout = 6, unique Hamiltonian path exists: 0 1, 1 2, 2 3, 3 4, 4 5, 5 6.,1,6,5,4,3,0,2,39,計算做法 1產生一path 2檢查首尾 3檢查長度 4檢查每個 vertex都有 Yes No,分子做法 1-1 任意選vertex編碼 1-2 產生instance編碼 1-3 截取DNA 1-4 放入試管 2分子過濾 3分子過濾 4分子過濾 還有path存在,40,未來的計算機,生物計算機 量子計算機,
