巡回セールスマン問題への招待 東京商船大学 久保 幹雄
Traveling Salesman Problem (TSP)
Icosian Game (Origin of Hamiltonian Circuit) Invented by W. R. Hamilton
Icosian Game (1) １ ２ ４ ３ ２０
Icosian Game (2) １ ２ ７ ６ ５ ４ ３ ２０
Icosian Game (3) １ ２ ７ ６ ５ ４ ３ ９ ８ ２０
Icosian Game (4) １ ２ ７ ６ ５ ４ ３ ９ ８ １４ １３ １２ １１ １０ ２０
Icosian Game (5) １ ２ ７ ６ ５ ４ ３ １９ ９ ８ １８ １７ １６ １５ １４ １３ １２ １１ １０ ２０
Knight Tour
Knight Tour (by Leonhard Euler)
Applications of TSP 基盤配線 配送計画 タンパク質構造解析
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
最も `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ナノ世紀
適当な点から出発し、まだ訪問していない最も近い点へ移動する Nearest Neighbor 全ての点を訪問したら出発点へもどる 適当な点から出発し、まだ訪問していない最も近い点へ移動する
Greedy （Multiple Fragment) 閉路ができたり、次数が２を超えないように、枝を短い順に加えていく
Convex Hull +Insertion 凸包で点を囲むように巡回路をつくる 巡回路に入っていない，最も遠い点へ移動する
Karp’s Partitioning Method (1) 各小領域に対する最適巡回路を求める 長方形で、p個の点が入るように分割する
Karp’s Partitioning Method (2) 長方体と交わる点の枝を非連結にならないようにたどる
Bucket 決められた順序（小領域内では任意）で点を訪問する 全ての点を含む単位正方形で小領域に分割し、適当な順序をつける
組合せ最適化問題(概念図) 大域的最適解 目的関数 f(x) 実行可能解の集合 F
山頂を目指す闇夜の登山者 解ｘ 近傍 N(x)
闇夜の登山者(ここが山頂?) 局所最適解
2-opt,3-opt neighborhood
Local Search
巡回セールスマン問題についてのより詳しい情報は．．． 山本芳嗣・久保幹雄 巡回セールスマン問題への招待 （朝倉書店） デモのソフトウェア（Windows 95,NT3.5+用）は http:://www.ipc.tosho-u.ac.jp/~kubo から入手可能，