《以旅行推销员问题为例浅谈如何利用计算机解题课件》由会员分享，可在线阅读，更多相关《以旅行推销员问题为例浅谈如何利用计算机解题课件（40页珍藏版）》请在金锄头文库上搜索。
1、以旅行推销员问题为例浅谈如何利用计算机解题课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望給定4個城市的相互距離1234121810322最小展開樹問題尋找一個將四個城市最經濟的聯結1234121810323旅行推銷員問題Traveling Salesman Problem (TSP)尋找一個從(1)出發，回到(1)的最短走法1234121810324TSP是一個公認的難題NP-Completen意義：我們現在現在無法對所有輸入所有輸入找到一個有有效率效率的解法n避免避免浪費時間
2、尋求更佳的解法nRef: Horowitz & Sahni,Fundamentals of Computer Algorithms, P528.5n2n相當可怕103050N0.00001 s0.00003 s0.00005 sN20.0001 s0.0009 s0.0025 s2n0.001 s17.9 min35.7 yearn像satisfiabilibility problemn目前只有exponential algorithm，還沒有人找到polynomial algorithm (你也不妨放棄！)這一類問題是NP-Complete ProblemnGarey & Johnson “
3、Computers & Intractability”6生物應用的計算需求數學問題工具程式Computational BiologyDatabaseAdded Value Database抽象化算法設計7例 Physical Mapping of DNAP1P2 P1P2C2 11 C1 10C1 10 C2 11C3 01C3 01consecutive 1 propetynFalse negativenFalse positiveC1C2C3P1P28A clones x probes matrix with added column p6*.P1P2P3P4P5P6C1111000C20
4、11100C2100110C4111100P1P6P2P5P3P4220312222244343TSP graph for matrix of Table9n旅行推銷員問題是許多排程排程應用的核心問題（航運排程）n有許多變型n平面TSPn幾何TSP（滿足三角不等式）n不對稱TSP*234(1)(3)(2)(1)(2)2410窮舉法（Enumerating）(想想看什麼問題不能窮舉解？)加分題!n旅行推銷員問題：旅行推銷員問題：3!走法 (n-1)!n最小展開樹問題：最小展開樹問題：16種樹n(n-2) Cayleys Thm.Ref: Even, Graph Algorithms, PP262
5、81241143211nLabeled tree Number sequenceOne-to-One MappingnN個nodes的labeled tree可以用一個長度N-2的number sequence來表達。nEncoding: Data Compression.12Labeled treeNumber sequencen在每一個iteration裡，切除目前所有leaves中編號最小的node及其edges，記錄切點，切到只剩一條edge為止。例.Prune-sequence:7,4,4,7,5(切點)nLabel最大者必在最後的edge.n每個node原先的degree數=此no
6、de在Prune-sqeuence中出現的次數+1.234715613Number sequenceLabeled treePrune-sequence: 7,4,4,7,5k1234567deg(k)1113213Iteration 10113212Iteration 20012212Iteration 30001212Iteration 40000211Iteration 50000101Iteration 60000000n每一個iteration裡，選擇degree為1且編號最小的node，連接prune-sequence中相對的node，之後兩個nodes的degree均減1.Ite
7、ration 1 Iteration 2Iteration 3Iteration 4 Iteration 6Iteration 517172417243174174321743265325614貪心法（Greedy）n旅行推銷員問題 xn最小展開樹問題 o兩種貪心都成功：1. 將邊由小到大加入，有迴圈即丟掉2. 將樹從一點開始，最經濟向外擴展15Minimal spanning treeKruskala AlgorithmABDCE706530090508075200Begin T - null While T contains less than n-1 edges, the smalles
8、t 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 edge16做priorit
9、y queue可以用heap operationO(log n)InitialO(n)nTarjan: Union & Find可以almost linear (Amortized)nCorrectnessn如果不選最小edge做tree而得到minimaln加入最小edge會有cyclenDelete cycle中最大的edge會得到更小cost之tree (矛盾！)124375617建spanning tree可以看做spanning forest加link1. 加 edge(2,3)不合法2. 加 edge(1,4)合法n另一種看法：S1=1,2,3S2=4,5Edge的端點要在不同se
10、tSet的 Find, UnionO(log n)1324518Prims AlgorithmABDCE706530090508075200Step 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
11、 = 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)19考慮以下的城市做旅行推銷員問題n從(1)開始貪心不成功！1423100115238123412310020一些常用的方法n貪心法（The Greedy Method）n各個擊破法（Divide-&-Conquer）n窮舉法（Enumerating）n樹狀搜尋法（Tree Searching Strategies）（Branch & Bound）n動態規畫法
12、（Dynamic Programming）n近似法（Approximation）21動態規畫法（Dynamic Programming）原則：n滿足遞迴關係技巧：n利用空間換取時間最簡單的例子：n算Fibonacci NumberF (i) = F (i - 1) + F (i - 2)F (0) = F (1) = 122樹狀搜尋法（Tree Searching Strategies）（Branch & Bound）n預估B, C, D以下的解，如果D的最樂觀可能解，都比B以下的某解還差，則D以下可以不搜尋深藍！ABCD23近似解法（Approximation）n不期望最佳解n用效率高的方法
13、去求合理解n該合理解與最佳解有可預期的倍數關係n可以做如模擬退火法的其它解法的初始解or參考值n理論分類nNPO completenMAX SNP hardnPTAShttp:/web.informatik.unibonn.de/IV/Mitarbeiter/rick/WS9687/approxvortr/approxvortr.html24以幾何TSP為例先做最小展開樹25挑出所有奇數degree的點26對他們做matching (Euler Graph)27一筆畫Minimal spanning tree TSPMinimal matching 3/2 TSP時間 n2.528模擬自然界一
14、些其它的隨機方法n模擬退火n神經計算n基因演算29模擬退火 回火 策略Simulated-AnnealingnLocal maximal global maximalnLocal maximal 不是 global maximal難題！30模擬退火法 (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) ran
15、dom 0, 1) then I := jend;f (i) f (j)比ck愈小愈有機會反Greedy但不要太離譜！k := k +1;CALCULATE_ LENGTH (Lk);CALCULATE_ CONTROL (Lk);until stop criterionend;31TSP如何做？從一個tour裡任取兩個edge決定到底要不要用取代原則：通常還是貪心，偶而讓它反其道一下32n模擬退火是一種隨機方法，只能預設一個停止時間，看天吃飯。n模擬退火中有許多參數，要靠經驗或實驗。33Introduction Genetic Algorithms（基因計算）nGenetic Algorit
16、hmsnArtificial mechanisms of natural evolution.nA robust search procedures and solving complex search problems.nDisadvantagenLow efficient if large problem space.nPopulation homogeneous.EndBeginEncodingInitialize populationReproduction & SelectionCrossoverMutationEvaluate populationTermination crite
17、rionEvaluate populationNoYes34The Eugenic Genetic Algorithm for TSPCrossover PhasenSequence preserving crossover (SPX)nSchemata is preserved as more as possible.A=123|5748|69B=934|5678|21A=234|5678|91B=936|5748|21129384756129384756129384756129384756(a) A(a) A(a) B(a) BCrossover35nPoint mutationnInve
18、rsion mutationnShift mutationThe Eugenic Genetic Algorithm for TSPMutation Phase(a) Point mutation(b) Inversion mutation(c) Shift mutation (right shift)36分子計算（Molecular Computation）nUse (DNA) molecules to represent the data instances. Put the molecules into a tube, control the environments.nThe mole
19、cules will bind with each other. The most tightly binging is the minimum cost solution.nMassive 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.37以TSP的特例Hamiltonian P
20、ath為例（也是難題）n問題：有無從0 6，長度為6，各vertex恰走一遍的path?O2 TATCGGATCGGTATATCCGAO3 GCTATTCGAGCTTAAAGCTAO4 GGCTAGGTACCAGCATGCTTO23 GTATATCCGAGCTATTCGAGO34 CTTAAAGCTAGGCTAGGTACO3 (bar) CGATAAGCTCGAATTTCGAT O23 O34GTATATCCGAGCTATTCGAGCTTAAAGCTAGGCTACGATAAGCTCGAATTTCGAT O3 (bar) nFig.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.165430238計算做法1產生一path2檢查首尾3檢查長度4檢查每個 vertex都有YesNo分子做法1-1 任意選vertex編碼1-2 產生instance編碼1-3 截取DNA1-4 放入試管2分子過濾3分子過濾4分子過濾還有path存在39未來的計算機n生物計算機n量子計算機40
