《以旅行推销员问题为例浅谈如何利用计算机解题.ppt》由会员分享，可在线阅读，更多相关《以旅行推销员问题为例浅谈如何利用计算机解题.ppt（40页珍藏版）》请在三一办公上搜索。
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 Computer Algorithms
2、,P528.,6,2n相當可怕,像satisfiabilibility problem目前只有exponential algorithm，還沒有人找到polynomial algorithm(你也不妨放棄！)這一類問題是NP-Complete ProblemGarey&Johnson“Computers&Intractability”,7,生物應用的計算需求,數學問題,工具程式,Computational Biology,Database,Added Value Database,抽象化,算法設計,8,例 Physical Mapping of DNA,P1P2 P1P2C2 11 C1 10
3、C1 10 C2 11C3 01C3 01consecutive 1 propetyFalse negativeFalse 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)
4、,(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 sequenceOne-to-One MappingN個nodes的labeled tree可以用一個長度N-2的number sequence來表達。Encoding:Data Compression.,13,Labeled treeNumber
5、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，之後兩
6、個nodes的degree均減1.Iteration 1 Iteration 2Iteration 3Iteration 4 Iteration 6Iteration 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 treeKruskala Algorithm,A,B,D,C,E,70,65,300,90,50,80,75,200
7、,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
8、(m log m)m=#of edge,17,做priority queue可以用heap operation,O(log n)InitialO(n)Tarjan:Union&Find可以almost linear(Amortized)Correctness如果不選最小edge做tree而得到minimal加入最小edge會有cycleDelete 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)合法另一種看
9、法：S1=1,2,3S2=4,5Edge的端點要在不同setSet的 Find,UnionO(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
10、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 Se
11、arching Strategies）（Branch&Bound）動態規畫法（Dynamic Programming）近似法（Approximation）,22,動態規畫法（Dynamic Programming）,原則：滿足遞迴關係技巧：利用空間換取時間最簡單的例子：算Fibonacci NumberF(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,近似解法（Appro
12、ximation）,不期望最佳解用效率高的方法去求合理解該合理解與最佳解有可預期的倍數關係可以做如模擬退火法的其它解法的初始解or參考值理論分類NPO completeMAX SNP hardPTAShttp:/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
13、,模擬自然界一些其它的隨機方法,模擬退火神經計算基因演算,30,模擬退火 回火 策略Simulated-Annealing,Local maximal global maximal,Local maximal 不是 global maximal,難題！,31,模擬退火法(Simulated Annealing),procedure SIMULATED-ANNEALINGbeginINITIALIZE(i start,c0,L0);k:=0;i:=i start;repeatfor l:=1 to Lk dobeginGENERATE(j form Si);Greedyif f(j)random
14、 0,1)then I:=jend;f(i)f(j)比ck愈小愈有機會反Greedy但不要太離譜！k:=k+1;CALCULATE_ LENGTH(Lk);CALCULATE_ CONTROL(Lk);until stop criterionend;,32,TSP如何做？,從一個tour裡任取兩個edge,決定到底要不要用,取代,原則：通常還是貪心，偶而讓它反其道一下,33,模擬退火是一種隨機方法，只能預設一個停止時間，看天吃飯。模擬退火中有許多參數，要靠經驗或實驗。,34,Introduction Genetic Algorithms（基因計算）,Genetic AlgorithmsArti
15、ficial mechanisms of natural evolution.A robust search procedures and solving complex search problems.DisadvantageLow efficient if large problem space.Population homogeneous.,End,Begin,Encoding,Initialize population,Reproduction&Selection,Crossover,Mutation,Evaluate population,Termination criterion,
16、Evaluate population,No,Yes,35,The Eugenic Genetic Algorithm for TSPCrossover Phase,Sequence preserving crossover(SPX)Schemata is preserved as more as possible.,A=123|5748|69B=934|5678|21,A=234|5678|91B=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
17、,(a)B,Crossover,36,Point mutationInversion mutationShift mutation,The Eugenic Genetic Algorithm for TSPMutation 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,
18、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*1023Ref.Adleman,Molecular Computation of Solutions to Combinatorial Problems,Science,Vol.266,11,1994,PP1021-1024.,38
19、,以TSP的特例Hamiltonian Path為例（也是難題）,問題：有無從0 6，長度為6，各vertex恰走一遍的path?,O2 TATCGGATCGGTATATCCGAO3 GCTATTCGAGCTTAAAGCTAO4 GGCTAGGTACCAGCATGCTTO23 GTATATCCGAGCTATTCGAGO34 CTTAAAGCTAGGCTAGGTACO3(bar)CGATAAGCTCGAATTTCGAT O23 O34GTATATCCGAGCTATTCGAGCTTAAAGCTAGGCTACGATAAGCTCGAATTTCGAT 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產生一path2檢查首尾3檢查長度4檢查每個 vertex都有YesNo,分子做法1-1 任意選vertex編碼1-2 產生instance編碼1-3 截取DNA1-4 放入試管2分子過濾3分子過濾4分子過濾還有path存在,40,未來的計算機,生物計算機量子計算機,
