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

以「旅行推銷員問題」為例，淺談如何利用計算機解題給定4個城市的相互距離最小展開樹問題尋找一個將四個城市最經濟的聯結旅行推銷員問題TravelingSalesmanProblem(TSP)尋找一個從(1)出發，回到(1)的最短走法TSP是一個公認的難題NP-Complete2n相當可怕
生物應用的計算需求例PhysicalMappingofDNAAclonesxprobesmatrixwithaddedcolumnp6*.旅行推銷員問題是許多排程應用的核心問題 （航運排程）
有許多變型
平面TSP
幾何TSP（滿足三角不等式）
不對稱TSP窮舉法（Enumerating）LabeledtreeNumbersequenceOne-to-OneMapping
N個nodes的labeledtree可以用一個長度N-2的numbersequence來表達。
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（基因計算）TheEugenicGeneticAlgorithmforTSPCrossoverPhasePointmutation
Inversionmutation
Shiftmutation
分子計算（MolecularComputation）以TSP的特例HamiltonianPath為例（也是難題）計算做法
1．產生一path
2．檢查首尾
3．檢查長度
4．檢查每個vertex都有
Yes
No
未來的計算機