TSPにおける最適解の特徴とそれに基づく三角化グラフ
TSPにおける最適解の特徴とそれに基づく三角化グラフ
カテゴリ: 部門大会
論文No: GS18-3
グループ名: 【C】平成17年電気学会電子・情報・システム部門大会講演論文集
発行日: 2005/09/06
タイトル(英語): The Characterics of the Edges on the Optimum Tour in Traveling Salesman Problem and the Triangulation Graph Based on the Relationship between the Location of Cities
著者名: 竇心潔 (千葉大学),荒井 幸代(千葉大学),須貝 康雄(千葉大学)
著者名(英語): Xinjie Dou(Chiba University),Sachiyo Arai(Chiba University),Yasuo Sugai(Chiba University)
キーワード: 巡回セールスマン問題|三角化グラフ|ドロネー図|凸包|組合せ最適化問題|traveling salesman problem|the triangulation graph|Delaunay graph|convex hull|combinatorial optimization problem
要約(日本語): 組合せ最適化問題の典型例である巡回セールスマン問題を対象として、最適解が既知である問題について、最適巡回路の性質を調べた結果を報告する。また、その性質に基づいて、巡回セールスマン問題を効率的に解くための三角化グラフを提案する。
最適巡回路には長さの短い枝が採用されている一方、巡回路という制約を満たすためには、長い枝を採用されている。どのような枝か採用されるのは都市間の相対的位置関係に基づいている。提案する三角化グラフはその性質を利用して作成するため、各枝の長さは相対的に短い。従って、三角化グラフ上で巡回路を求められれば、その解の精度は高いことが期待でき、また、様々な手法を三角化グラフに適用できる可能性がある。
PDFファイルサイズ: 2,736 Kバイト
受取状況を読み込めませんでした
