巡回セールスマン問題(Traveling Salesman Problem, TSP)とは、セールスマンが複数の都市を訪問して出発地に戻る際、総移動距離が最小となる経路を求める問題です。都市の数が増えると、可能な経路の数が爆発的に増加するため、最適解を求めることが非常に難しい問題(NP困難)として知られています。 巡回セールスマン問題とは 問題の構成要素 問題の難しさ 補足: NP困難とは 巡回セールスマン問題の解法 解法1: 厳密解法 解法2: 近似解法 解法3: メタヒューリスティクス 具体例:6都市の巡回セールスマン問題 まとめ 巡回セールスマン問題とは 巡回セールスマン問題は、以下のよ…