hitonanode
commented
2 years ago - 問題例
- DMOPC '21 Contest 5 P5 - Permutations & Primes - DMOJ: Modern Online Judge
- A46 - Heuristic 1
- 変形版 A - ツーリストXの旅行計画
- 厳密解
- Held–Karp algorithm $O(n 2^n)$
- Symmetric TSP の有名ヒューリスティクス
- 2-opt
- Or-opt
- 3-opt
- Lin–Kernighan heuristic
- Lin–Kernighan–Helsgaun
- http://webhotel4.ruc.dk/~keld/research/LKH/LKH-1.3/DOC/LKH_REPORT.pdf が非常に詳しい
- やってみるかも
- 割当近傍 http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/localsearch/handout09.pdf
- Asymmetric でも symmetric に帰着できる https://en.wikipedia.org/wiki/Travelling_salesman_problem#Asymmetric
- 下界
- Held–Karp lower bound
- その他リンク
- https://future-architect.github.io/articles/20211201a/