巡回セールスマン問題への招待 東京商船大学 久保 幹雄 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 基盤配線 配送計画 タンパク質構造解析 Applications clustering a data array 10 P p= 2 circuit board assembly computer wiring 3 circuit board drilling 4 vehicle routing 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)! 計算機の限界 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 から入手可能，
© Copyright 2024 ExpyDoc
