SimRoad(シムロード) - joi2010-day3 解説
筆者: qnighy
複雑な最適化問題である。盤面上の草をできるだけ少なく刈り取り、与えられたマスを全て連結させるのが目的である。
qnighyによる貪欲法(山登り法)を用いた解法
ここでは、qnighyによる貪欲法を用いた解法を提示しよう。
ここでの貪欲法のアイデアは以下のようである。
- 「一回の操作」は「何らかの方法で草を刈り取り、2つの繋がっていなかった町を繋げる」こととする。
- 「局所最適な操作」は「その場でできる一回の操作のうち、最も刈取る草の個数が少ないもの」とする。
- 「貪欲法」は「毎回、局所最適な操作を繰り返し、操作ができなくなったら終了。」とする。
ここでの「局所最適な操作」は、簡単なDijkstra法によって実装できる。(このときに用いる優先順位付キューはpriority_queueでも良いが、重さごとにキューを用意する方法で優先順位付キューを実装すると高速化が見込める。)
この方法をqnighyが実装したところ、以下のような成果を得た。(局所最適な操作が複数あるときの選択方法によって多少成績は変化する可能性がある。)
| probid | Basic Algorithm | qnighy’s Algorithm |
|---|---|---|
| 1 | 146 | 128 |
| 2 | 67 | 40 |
| 3 | 2195 | 368 |
| 4 | 5926 | 964 |
| 5 | 4088 | 643 |
この解法は、ありがちな局所改善法の1つ(ちょっと違うが…)なので、最もありがちな改善としては、擬似焼きなまし法(アニーリング)があるだろう。これは、隣接改善解を求めるさいに、最適解から一定の誤差の範囲内にある解のうちランダムなものを選び、許容する誤差をだんだん狭めていくことで、大域最適解とは遠い局所最適解に入り込むのを避ける方法である。
他にもいろいろあるので、試してみるとより改善できるだろう。
その他の解法: DP
テストケース1は横長であり、動的計画法により厳密解が得られると噂されている。ぜひとも実装方法を考えてみてほしい。