巡回セールスマン
- 2. 問題 ? 頂点数1000の有向完全グラフが与えられます（辺の情報は見る ことができます）。頂点0から始めて全ての頂点を一度だけ通 り頂点０に戻ってくる経路のうち、できるだけ短いものを求め よ。 ? つまり、巡回セールスマン問題 ? 以下のリンクにジャッジ用のコードとサンプルのコードがある ので、始めたい人は始めてください ? https://github.com/gasin/procon1
- 3. 巡回セールスマン問題とは ? NP困難と呼ばれるクラスに含まれる問題。 ? 僕もよく理解していないが、とにかく効率的なアルゴリズムが 存在しない問題。 ? 頂点数が1000などというサイズの問題が解けるわけがない ? 競プロなどにおいて巡回セールスマン問題が出るときの頂点数 はせいぜい12ぐらい。
- 4. 巡回セールスマン問題（n<=12のとき） ? bitDPというテクニックを使うことで解くことができる。（詳 しくは蟻本を参照） ? 計算量はO(n*2^n) ? アイディアとしては、今いる頂点と、それまでに訪れた頂点の 情報が分かっていれば十分なので、経路を全て記憶している必 要がないということを利用してうまくDPをする。
- 7. 山登り法 ? その場その場でより良いスコアへの改善を探索し、良いスコアを見 つけたらそれを採用するという操作を繰り返す。 ? しかし、局所解に陥りやすいので工夫が必要になる。（しかし、そ こそこのコンテストだとこれだけでなんとかなったりする） ? 今回の場合に適用すると、適当に経路を定め、その頂点を適当に swapするなどして、もとの経路よりもコストが小さくなればそれを 採用するということを繰り返すなどの方法が考えられる。 ? 上位互換として、焼きなまし法という方法があり、これは局所解に 陥りにくくしたもの。（温度という概念を導入し、現在の解よりも 悪くてもそれをある確率で採用するという操作を行う）
- 8. ビームサーチ ? マラソン系のコンテストにおいて、最も使われている手法（多 分）。派生系もたくさんある（chokudai searchなど）。 ? 探索をするときに、全探索をするとメモリや時間が足りなくな るので、そこを工夫しようというもので、よさそうな解をいく つかだけ採用して他の場合を切り捨てるという考え方。 ? いくつ採用するのか（ビームの幅）、よさそうとはなんなのか （評価関数）など、考えることは多いので扱いが難しいといえ ば難しい。 ? 今回の問題で言えば、i頂点からなる経路のうち、短い経路を10 個だけ採用するなど。
- 9. 頑張りましょう ? これらのテクニックはもちろん、複合することもできたりする ので色々と工夫してみましょう。 ? どの方法をとるにしても、試行回数は多ければ多い方が良いに 決まっているので、高速化や自動化は実装したほうが結果的に はよいです。 ? また、数字が大きいので基本的にlong long型を使ったほうがい です。 ? 経路の候補は1000!（2568桁らしい）もあり、最適解なんか求 まるわけもないので良い解が出ても、もっと良い解があるはず だと思って改善を続けましょう。