巡回セールスマン問題への招待 東京商船大学 久保 幹雄.

Presentation on theme: "巡回セールスマン問題への招待 東京商船大学 久保 幹雄."— Presentation transcript:

1 巡回セールスマン問題への招待 東京商船大学 久保 幹雄

2 Traveling Salesman Problem (TSP)

3 Icosian Game (Origin of Hamiltonian Circuit) Invented by W. R. Hamilton

4 Icosian Game (1) １ ２ ４ ３ ２０

5 Icosian Game (2) １ ２ ７ ６ ５ ４ ３ ２０

6 Icosian Game (3) １ ２ ７ ６ ５ ４ ３ ９ ８ ２０

7 Icosian Game (4) １ ２ ７ ６ ５ ４ ３ ９ ８ １４ １３ １２ １１ １０ ２０

8 Icosian Game (5) １ ２ ７ ６ ５ ４ ３ １９ ９ ８ １８ １７ １６ １５ １４ １３ １２ １１ １０ ２０

9 Knight Tour

10 Knight Tour (by Leonhard Euler)

11 Applications of TSP 基盤配線 配送計画 タンパク質構造解析

12 10 P Applications clustering a data array circuit board assembly
2 circuit board assembly computer wiring 3 circuit board drilling vehicle routing 4 protein conformations x-ray crystallography 5 VLSI Scan Chain Optimization 6 VLSI fabrication 7

13 最も `naïve’ な解法（全列挙法） (n-1)×(n-2)×…×3×2×1=(n-1)!
某新聞曰く：３０都市の巡回セールスマン問題になると総あたり法は高性能計算機でも約３日かかる! (n-1)×(n-2)×…×3×2×1=(n-1)! 計算機の限界 10 GIPS (Giga Instruction Per Second) 29!/1010 　（秒）　≧ π×1019 （秒） ≒ 1010 （世紀） James Stiringの公式 n! ≒2√πn(n/e)n Tom Duffの格言 π秒は1ナノ世紀

14 適当な点から出発し、まだ訪問していない最も近い点へ移動する
Nearest Neighbor 全ての点を訪問したら出発点へもどる 適当な点から出発し、まだ訪問していない最も近い点へ移動する

15 Greedy （Multiple Fragment)
閉路ができたり、次数が２を超えないように、枝を短い順に加えていく

16 Convex Hull +Insertion
凸包で点を囲むように巡回路をつくる 巡回路に入っていない，最も遠い点へ移動する

17 Karp’s Partitioning Method (1)
各小領域に対する最適巡回路を求める 長方形で、p個の点が入るように分割する

18 Karp’s Partitioning Method (2)
長方体と交わる点の枝を非連結にならないようにたどる

19 Bucket 決められた順序（小領域内では任意）で点を訪問する 全ての点を含む単位正方形で小領域に分割し、適当な順序をつける

20 組合せ最適化問題(概念図) 大域的最適解 目的関数 f(x) 実行可能解の集合 F

21 山頂を目指す闇夜の登山者 解ｘ 近傍 N(x)

22 闇夜の登山者(ここが山頂?) 局所最適解

23 2-opt,3-opt neighborhood

24 Local Search

25 巡回セールスマン問題についてのより詳しい情報は．．．
山本芳嗣・久保幹雄 巡回セールスマン問題への招待 （朝倉書店） デモのソフトウェア（Windows 95,NT3.5+用）は から入手可能，