以旅行推销员问题为例浅谈如何利用计算机解题市公开课金奖市赛课一等奖课件.pptx

以「旅行推銷員問題」為例，淺談如何利用計算機解題給定4個都市互相距離最小展開樹問題尋找一個將四個都市最經濟聯結旅行推銷員問題TravelingSalesmanProblem(TSP)尋找一個從(1)出發，回到(1)最短走法TSP是一個公認難題NP-Complete2n相當可怕生物應用計算需求例PhysicalMappingofDNAAclonesxprobesmatrixwithaddedcolumnp6*.旅行推銷員問題是許多排程應用关键問題（航運排程）有許多變型平面TSP幾何TSP（滿足三角不等式）不對稱TSP窮舉法（Enumerating）LabeledtreeNumbersequenceOne-to-OneMappingN個nodeslabeledtree能够用一個長度N-2numbersequence來表達。Encoding:DataCompression.LabeledtreeNumbersequenceNumbersequenceLabeledtree貪心法（Greedy）MinimalspanningtreeKruskal’aAlgorithm做priorityqueue能够用heapoperation建spanningtree能够看做spanningforest加linkPrim’sAlgorithm考慮下列都市做旅行推銷員問題一些惯用办法動態規畫法（DynamicProgramming）樹狀搜尋法（TreeSearchingStrategies）（Branch&Bound）近似解法（Approximation）以幾何TSP為例先做最小展開樹挑出所有奇數degree點對他們做matching(EulerGraph)一筆畫模擬自然界一些其它隨機办法模擬退火回火策略Simulated-Annealing模擬退火法(SimulatedAnnealing)TSP如何做？模擬退火是一種隨機办法，只能預設一個停止時間，看天吃飯。模擬退火中有許多參數，要靠經驗或實驗。IntroductionGeneticAlgorithms（基因計算）PointmutationInversionmutationShiftmutation分子計算（MolecularComputation）以TSP特例HamiltonianPath為例（也是難題）計算做法1．產生一path2．檢查首尾3．檢查長度4．檢查每個vertex都有YesNo未來計算機