巡回セールスマン問題 (TSP)

巡回セールスマン問題（TSP）とは、複数の都市とその都市間の移動コスト（距離や時間など）が与えられたとき、全ての都市をちょうど一度ずつ訪問し、出発地に戻る巡回路のうち、総移動コストが最小となる経路を求める組合せ最適化問題です。

この問題は、一見単純に見えますが、都市の数が増えるにつれて計算量が爆発的に増加するNP困難な問題として知られています。

巡回セールスマン問題の例

巡回セールスマン問題はNP困難な問題であるため、厳密な最適解を求めるには膨大な計算時間が必要となります。そのため、現実的な時間で解を得るために、様々な近似解法が用いられます。

代表的な解法は以下のとおりです。

総当たり法（厳密解法）: すべての可能な巡回路を計算し、その中で最もコストの低いものを選択します。都市数が増えると計算時間が指数関数的に増加するため、現実的な時間で解ける都市数は限られます。
貪欲法（近似解法）: 現在地から最も近い未訪問の都市を順に選択していく方法です。計算時間は短いですが、必ずしも最適解が得られるとは限りません。
局所探索法（近似解法）: 現在の巡回路から少しだけ変更した巡回路を生成し、よりコストの低い巡回路が見つかれば更新していく方法です。局所最適解に陥る可能性があります。
遺伝的アルゴリズム（近似解法）: 生物の進化の過程を模倣したアルゴリズムです。複数の巡回路を個体として扱い、選択、交叉、突然変異などの操作を繰り返すことで、より良い解を探索します。
焼きなまし法（近似解法）: 金属の焼きなまし過程を模倣したアルゴリズムです。局所最適解から脱出し、より良い解を探索する能力に優れています。

巡回セールスマン問題は、様々な分野で応用される重要な問題です。効率的な配送ルートの最適化は、物流コストの削減や配送時間の短縮に繋がり、企業の競争力強化に貢献します。また、プリント基板の穴あけや遺伝子配列の決定など、製造業やバイオテクノロジー分野でも重要な役割を果たします。

巡回セールスマン問題（TSP）は、組合せ最適化問題の代表的な問題の一つであり、多くの応用分野で重要な役割を果たしています。厳密解を求めることが難しいNP困難な問題であるため、様々な近似解法が研究されています。