cplib-cpp TSP

TSP

Open hitonanode opened this issue 3 years ago • 1 comments

問題例
厳密解
- 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/

Nov 08 '22 14:11 hitonanode

まあまあ https://atcoder.jp/contests/tessoku-book/submissions/38355569

Jan 27 '23 12:01 hitonanode