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

以「旅行推銷員問題」為例，淺談如何利用計算機解題 唐傳義 教授 cytang@.tw 國立清華大學資訊工程系 給定4個城市的相互距離 最小展開樹問題尋找一個將四個城市最經濟的聯結 旅行推銷員問題Traveling Salesman Problem (TSP)尋找一個從(1)出發，回到(1)的最短走法 TSP是一個公認的難題NP-Complete 意義：我們現在無法對所有輸入找到一個有效率的解法 避免浪費時間尋求更佳的解法 Ref: Horowitz Sahni,Fundamentals of Computer Algorithms, P528. 2n相當可怕 Computational Biology 例 Physical Mapping of DNA P1　P2 P1 　P2 　C2 [1　　1] C1 [1　　0] 　C1 [1　　0] C2 [1　　1] 　C3 [0　　1] C3 [0　　1] consecutive 1 propety False negative False positive 旅行推銷員問題是許多排程應用的核心問題 　（航運排程） 有許多變型 平面TSP 幾何TSP（滿足三角不等式） 不對稱TSP 窮舉法（Enumerating） (想想看什麼問題不能窮舉解？)－加分題! 旅行推銷員問題： 3!走法 (n-1)! 最小展開樹問題： 16種樹 n(n-2) Cayley’s Thm. Ref: Even, Graph Algorithms, PP26~28 Labeled tree ? Number sequenceOne-to-One Mapping N個nodes的labeled tree可以用一個長度N-2的number sequence來表達。 Encoding: Data Compression. Labeled tree?Number sequence 在每一個iteration裡，切除目前所有leaves中編號最小的node及其edges，記錄切點，切到只剩一條edge為止。 例. Prune-sequence:7,4,4,7,5(切點) Label最大者必在最後的edge. 每個node原先的degree數=此node在Prune-sqeuence中出現的次數+1. 貪心法（Greedy） 旅行推銷員問題 x 最小展開樹問題 o 兩種貪心都成功： 1. 將邊由小到大加入，有迴圈即丟掉 2. 將樹從一點開始，最經濟向外擴展 Minimal spanning treeKruskal’a Algorithm 做priority queue可以用heap operation O(log n) Initial O(n) Tarjan: Union Find可以almost linear (Amortized) Correctness 如果不選最小edge做tree而得到minimal 加入最小edge會有cycle Delete cycle中最大的edge會得到更小cost之tree ??(矛盾！) 建spanning tree可以看做spanning forest加link 1. 加 edge(2,3) 不合法 2. 加 edge(1,4) 合法 另一種看法： S1={1,2,3} S2={4,5} Edge的端點要在不同set Set的 Find, Union O(log n) Prim’s Algorithm 考慮以下的城市做旅行推銷員問題 從(1)開始貪心 不成功！ 一些常用的方法 貪　心　法（The Greedy Method） 各個擊破法（Divide--Conquer） 窮　舉　法（Enumerating） 樹狀搜尋法（Tree Searching Strategies）　　　　　（Branch Bound） 動態規畫法（Dynamic Programming） 近　似　法（Approximation） 動態規畫法（Dynamic Programming） 原則： 滿足遞迴關係 技巧： 利用空間換取時間 最簡單的例子： 算Fibonacci Number F (i) = F (i - 1) + F (i - 2) F (0) = F (1) = 1 樹狀搜尋法（Tree Searching Strategies）　　　　　（Branch Bound） 預估B, C, D以下的解，如果D的最樂觀可能解，都比B以下的某解還差，則D以下可以不搜尋 深藍！ 近似解法（Approximation） 不期望最佳解 用效率高的方法去求合理解 該