以旅行推销员问题为例浅谈如何利用计算机解题.ppt
《以旅行推销员问题为例浅谈如何利用计算机解题.ppt》由会员分享,可在线阅读,更多相关《以旅行推销员问题为例浅谈如何利用计算机解题.ppt(40页珍藏版)》请在三一文库上搜索。
1、以旅行推銷員問題為例,淺談 如何利用計算機解題,唐傳義 教授 cytangcs.nthu.edu.tw 國立清華大學資訊工程系,2,給定4個城市的相互距離,3,最小展開樹問題 尋找一個將四個城市最經濟的聯結,4,旅行推銷員問題 Traveling Salesman Problem (TSP) 尋找一個從(1)出發,回到(1)的最短走法,1,2,3,4,12,1,8,10,3,2,5,TSP是一個公認的難題 NP-Complete,意義:我們現在無法對所有輸入找到一個有效率的解法 避免浪費時間尋求更佳的解法 Ref: Horowitz & Sahni, Fundamentals of Compu
2、ter Algorithms, P528.,6,2n相當可怕,像satisfiabilibility problem 目前只有exponential algorithm,還沒有人找到polynomial algorithm (你也不妨放棄!) 這一類問題是NP-Complete Problem Garey & Johnson “Computers & Intractability”,7,生物應用的計算需求,數學問題,工具程式,Computational Biology,Database,Added Value Database,抽象化,算法設計,8,例 Physical Mapping of
3、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,C1,C2,C3,P1,P2,9,A clones x probes matrix with added column p6*.,P1,P6,P2,P5,P3,P4,2,2,0,3,1,2,2,2,2,2,4,4,3,4,3,TSP graph for matrix of Table,10,旅行推銷員問題是許多排程應用的 核心問題 (航運排程) 有許多變型 平面TSP 幾何TS
4、P(滿足三角不等式) 不對稱TSP,*,*,*,*,*,*,*,2,3,4,(1),(3),(2),(1),(2),2,4,11,窮舉法(Enumerating),(想想看什麼問題不能窮舉解?)加分題! 旅行推銷員問題: 3!走法 (n-1)! 最小展開樹問題: 16種樹 n(n-2) Cayleys Thm. Ref: Even, Graph Algorithms, PP2628,12,4,1,1,4,3,2,12,Labeled tree Number sequence One-to-One Mapping N個nodes的labeled tree可以用一個 長度N-2的number se
5、quence來表達。 Encoding: Data Compression.,13,Labeled treeNumber sequence,在每一個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,Number sequenceLabeled tree,Prune-sequence: 7,4,
6、4,7,5,每一個iteration裡,選擇degree為1且編號最小的node,連接prune-sequence中 相對的node,之後兩個nodes的degree均減1. Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 6 Iteration 5,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. 將樹從一點開始,最經濟向外擴
7、展,16,Minimal spanning tree Kruskala Algorithm,A,B,D,C,E,70,65,300,90,50,80,75,200,Begin T - null While T contains less than n-1 edges, the smallest 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 doe
8、s 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 edge,17,做priority queue可以用 heap operation,O(log n) Initial O(n) Tarjan: Union & Find可以almost linear (Amortized) Correctness 如果不選最小edge做tree而得到minimal 加入最小edge會有cycle
9、Delete cycle中最大的edge會得到更小cost之tree (矛盾!),1,2,4,3,7,5,6,18,建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),1,3,2,4,5,19,Prims Algorithm,A,B,D,C,E,70,65,300,90,50,80,75,200,Step 1: Let x be any vertex in V. Le
10、t 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 = B v. Step 4: If B is empty, terminate and the resulting tree is a minimal spanning tree. Otherwise, g
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 旅行 推销员 题为 浅谈 如何 利用 计算机 解题
链接地址:https://www.31doc.com/p-2842749.html