【要約】巡回セールスマン問題をいろいろな手法で解いてみる②：山登り法 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
TSPはNP困難な問題であり、規模拡大に伴い厳密解の計算コストが爆発する。主な課題は以下の通り。
- ・計算時間の増大。
- ・近似解の精度不足。
- ・局所最適解へのトラップ。
// Approach
局所探索の枠組みに基づき、以下の手順で実装。
1.初期解の生成。
2.近傍解の生成（1回につき30個をランダムサンプリング）。
3.近傍操作による評価。
4.最良の近傍解への更新。
具体的な近傍操作として以下を実装。- ・交換近傍（
exchange_neighbor）: 2つの要素を入れ替える。 - ・2-opt近傍（
two_opt_neighbor）: 指定区間の要素順序を反転させる。
// Result
実装した手法の評価結果は以下の通り。
- ・交換近傍: コスト526。
- ・2-opt近傍: コスト450。
Senior Engineer Insight
> 実装の簡潔さと計算コストの制御性に優れる。近傍生成数を制限できるため、リアルタイム性が求められる現場での利用に適する。ただし、単一の山登り法では局所最適解を回避できない。実戦投入には、2-optのような強力な近傍操作の採用が必須。さらに、タブーサーチ等の脱出機構を組み合わせ、探索範囲を広げる設計が求められる。