【要約】巡回セールスマン問題をいろいろな手法で解いてみる③：タブーサーチ [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
- ・山登り法では、近傍解が全て現状より悪化すると探索が停止する。
- ・これにより、厳密解に到達できない「局所最適解」に陥る。
- ・探索が停滞し、最適解への遷移が不可能になる。
// Approach
1.タブーリストを導入。一定期間、過去の移動を禁止しループを回避。
2.解の改悪を許容。未知の領域への探索を強制。
3.
tabu_search 関数で近傍操作を抽象化。4.吸引基準を適用。最良解更新時はタブーを無視。
// Result
- ・都市数40、イテレーション300で検証。
- ・交換近傍：コスト627。
- ・2-opt近傍：コスト534。
- ・2-optの方が強力な探索能力を持つことを実証。
Senior Engineer Insight
>
メタヒューリスティクスとしての実装が極めて実戦的。特に、近傍操作を関数引数として受け取る設計は、問題定義の変更に強く、開発効率が高い。実運用では、タブーリストの管理対象（解か、操作ペアか）や、タブー期間の調整が鍵。大規模データへの適用には、近傍サンプリングの効率化が必須。