以「旅行推销员问题」为例-浅谈如何利用计算机解题PPT课件.ppt

以 旅行推銷員問題 為例 淺談如何利用計算機解題 唐傳義教授cytang cs nthu edu tw國立清華大學資訊工程系 1 2 給定4個城市的相互距離 3 最小展開樹問題尋找一個將四個城市最經濟的聯結 4 旅行推銷員問題TravelingSalesmanProblem TSP 尋找一個從 1 出發 回到 1 的最短走法 1 2 3 4 12 1 8 10 3 2 5 TSP是一個公認的難題NP Complete 意義 我們現在無法對所有輸入找到一個有效率的解法避免浪費時間尋求更佳的解法Ref Horowitz Sahni FundamentalsofComputerAlgorithms P528 6 2n相當可怕 像satisfiabilibilityproblem目前只有exponentialalgorithm 還沒有人找到polynomialalgorithm 你也不妨放棄 這一類問題是NP CompleteProblemGarey Johnson Computers Intractability 7 生物應用的計算需求 數學問題 工具程式 ComputationalBiology Database AddedValueDatabase 抽象化 算法設計 8 例PhysicalMappingofDNA P1P2P1P2C2 11 C1 10 C1 10 C2 11 C3 01 C3 01 consecutive1propetyFalsenegativeFalsepositive C1 C2 C3 P1 P2 9 Aclonesxprobesmatrixwithaddedcolumnp6 P1 P6 P2 P5 P3 P4 2 2 0 3 1 2 2 2 2 2 4 4 3 4 3 TSPgraphformatrixofTable 10 旅行推銷員問題是許多排程應用的核心問題 航運排程 有許多變型平面TSP幾何TSP 滿足三角不等式 不對稱TSP 2 3 4 1 3 2 1 2 2 4 11 窮舉法 Enumerating 想想看什麼問題不能窮舉解 加分題 旅行推銷員問題 3 走法 n 1 最小展開樹問題 16種樹n n 2 Cayley sThm Ref Even GraphAlgorithms PP26 28 12 4 1 1 4 3 2 12 Labeledtree NumbersequenceOne to OneMappingN個nodes的labeledtree可以用一個長度N 2的numbersequence來表達 Encoding DataCompression 13 Labeledtree Numbersequence 在每一個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 Numbersequence Labeledtree Prune sequence 7 4 4 7 5 每一個iteration裡 選擇degree為1且編號最小的node 連接prune sequence中相對的node 之後兩個nodes的degree均減1 Iteration1Iteration2Iteration3Iteration4Iteration6Iteration5 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 MinimalspanningtreeKruskal aAlgorithm A B D C E 70 65 300 90 50 80 75 200 BeginT nullWhileTcontainslessthann 1edges thesmallestweight chooseanedge v w formEofsmallestweight Usingpriorityqueue heap O logn delete v w formE Iftheaddingof v w toTdoesnotcreateacycleinT Usingunion find O logm thenadd v w toT elsediscard v w Repeat End O mlogm m ofedge 17 做priorityqueue可以用heapoperation O logn InitialO n Tarjan Union Find可以almostlinear Amortized Correctness如果不選最小edge做tree而得到minimal加入最小edge會有cycleDeletecycle中最大的edge會得到更小cost之tree 矛盾 1 2 4 3 7 5 6 18 建spanningtree可以看做spanningforest加link 1 加edge 2 3 不合法2 加edge 1 4 合法另一種看法 S1 1 2 3 S2 4 5 Edge的端點要在不同setSet的Find UnionO logn 1 3 2 4 5 19 Prim sAlgorithm A B D C E 70 65 300 90 50 80 75 200 Step1 LetxbeanyvertexinV LetA x andB V Step2 Selectanedge u v formEsuchthatuinA vinBand u v hasthesmallestweightamongedgesbetweenAandB Step3 ConnectvtouinA LetA A v andB B v Step4 IfBisempty terminateandtheresultingtreeisaminimalspanningtree Otherwise gotoStep2 O n2 20 考慮以下的城市做旅行推銷員問題 從 1 開始貪心不成功 1 4 2 3 100 1 15 2 3 8 1 2 3 4 1 2 3 100 21 一些常用的方法 貪心法 TheGreedyMethod 各個擊破法 Divide Conquer 窮舉法 Enumerating 樹狀搜尋法 TreeSearchingStrategies Branch Bound 動態規畫法 DynamicProgramming 近似法 Approximation 22 動態規畫法 DynamicProgramming 原則 滿足遞迴關係技巧 利用空間換取時間最簡單的例子 算FibonacciNumberF i F i 1 F i 2 F 0 F 1 1 23 樹狀搜尋法 TreeSearchingStrategies Branch Bound 預估B C D以下的解 如果D的最樂觀可能解 都比B以下的某解還差 則D以下可以不搜尋深藍 A B C D 24 近似解法 Approximation 不期望最佳解用效率高的方法去求合理解該合理解與最佳解有可預期的倍數關係可以做如模擬退火法的其它解法的初始解or參考值理論分類NPOcompleteMAXSNPhardPTAShttp web informatik uni bonn de IV Mitarbeiter rick WS9687 approxvortr approxvortr html 25 以幾何TSP為例先做最小展開樹 26 挑出所有奇數degree的點 27 對他們做matching EulerGraph 28 一筆畫 Minimalspanningtree 3 2TSP時間n2 5 29 模擬自然界一些其它的隨機方法 模擬退火神經計算基因演算 30 模擬退火回火策略Simulated Annealing Localmaximal globalmaximal Localmaximal不是globalmaximal 難題 31 模擬退火法 SimulatedAnnealing procedureSIMULATED ANNEALINGbeginINITIALIZE istart c0 L0 k 0 i istart repeatforl 1toLkdobeginGENERATE jformSi Greedyiff j random 0 1 thenI jend f i f j 比ck愈小愈有機會反Greedy但不要太離譜 k k 1 CALCULATE LENGTH Lk CALCULATE CONTROL Lk untilstopcriterionend 32 TSP如何做 從一個tour裡任取兩個edge 決定到底要不要用 取代 原則 通常還是貪心 偶而讓它反其道一下 33 模擬退火是一種隨機方法 只能預設一個停止時間 看天吃飯 模擬退火中有許多參數 要靠經驗或實驗 34 IntroductionGeneticAlgorithms 基因計算 GeneticAlgorithmsArtificialmechanismsofnaturalevolution Arobustsearchproceduresandsolvingcomplexsearchproblems DisadvantageLowefficientiflargeproblemspace Populationhomogeneous End Begin Encoding Initializepopulation Reproduction Selection Crossover Mutation Evaluatepopulation Terminationcriterion Evaluatepopulation No Yes 35 TheEugenicGeneticAlgorithmforTSPCrossoverPhase Sequencepreservingcrossover SPX Schemataispreservedasmoreaspossible 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 a B Crossover 36 PointmutationInversionmutationShiftmutation TheEugenicGeneticAlgorithmforTSPMutationPhase a Pointmutation b Inversionmutation c Shiftmutation rightshift 37 分子計算 MolecularComputation Use DNA moleculestorepresentthedatainstances Putthemoleculesintoatube controltheenvironments Themoleculeswillbindwitheachother Themosttightlybingingistheminimumcostsolution Massiveparallelismsincethelargenumberofmolecules 一莫耳 6 02 1023Ref Adleman MolecularComputationofSolutionstoCombinatorialProblems Science Vol 266 11 1994 PP1021 1024 38 以TSP的特例HamiltonianPath為例 也是難題 問題 有無從0 6 長度為6 各vertex恰走一遍的path O2TATCGGATCGGTATATCCGAO3GCTATTCGAGCTTAAAGCTAO4GGCTAGGTACCAGCATGCTTO2 3GTATATCCGAGCTATTCGAGO3 4CTTAAAGCTAGGCTAGGTACO3 bar CGATAAGCTCGAATTTCGATO2 3O3 4 GTATATCCGAGCTATTCGAGCTTAAAGCTAGGCT