マラソン勉強するぞ！~過去問演習編2~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
前回の記事の続き
↓前回に続いてchokudaiコン004の問題を解いていきたいと思います。
chokudaiコン004を解く！
前回の考察の続き
前回は、確か焼き鈍し法で点数上げられそう、みたいなところまで書いたと思います。とりあえず、そこから温めてきた考察と実装方法について、述べていきます。
正しいかどうかはわかりませんが、僕はこの問題の評価関数は↓このような形をしていると考えています。
お椀型ではなく、つんつんしている山が乱立しているイメージです。
たくさんある山の中で、最も標高が高いところを目指したいわけですが、普通の山登りでやろうとするとすぐに局所解に陥ってしまいます。焼き鈍しでやろうにも、何回も登ったり下ったりというのはなかなか大変ですし、それで良い解が得られるとも考えにくいです。
そこでやってみたいのが、計算点を増やしてみる、いわゆる多点スタート焼き鈍しです。一人で登るのが大変なら人数を増やしてしまえば、誰かしら最も高い場所にいってくれるのではないでしょうか。
手順としては、まず乱択でいろんな場所について考えてみて、そのうち点数がよかった状態を上から適当な数保持しておきます。そして、各状態に焼き鈍し法を適用して、頂点を探させます。
いきなり焼き鈍しをしようとすると実装がめちゃめちゃ大変になりそうなので、とりあえず多点スタート山登りを実装していきたいと思います。山登りでは、時間に応じて値を変化させるマス目の数を減らしていくような形で実装してみます。
実装終わりました。山登りの辺りの実装これでいいのかとても不安ですが、とりあえず出してみます。1164836点。なんか時間ミスってるっぽいのでもう一度。
うーん、乱択貪欲を超えられず、1165492点。値をいじりながらもう少し粘ってみます。
いろいろいじってみましたが、1168961点が最高で、順位は146位です。
点数が伸び悩んでいる原因について考える
現状、乱択貪欲で出したスタート地点がほぼそのまま解になってしまっています。すなわち、山登りでの改善がほとんどできていないということです。その原因について考えてみたいと思います。
ぱっと思いつくのは、乱択貪欲で作成した盤面の性質です。貪欲というのは、あるルールに則ったときの最適解なので、そのルールから外れる(マス目の値を変える)ことは、点数を悪化させやすいのでしょう。今回の場合の貪欲はほぼ局所解に等しいのかもしれません。
他には、山が想定より高くない可能性です。高い点数を出せる山の数が全体の山に対してかなり少ないという可能性もあります。この場合、なんとかして乱択の回数を増やして、アタリの山にたどり着かなければなりません。
このまま焼き鈍しに移ったとしても、きちんとした関数定義ができず、大してスコアが伸びないような予感がします。
貪欲を改善してみる
一旦初心に帰って貪欲を整理してみたいと思います。今まで横オンリーで考えていましたが、縦の情報も加えたいです。前回の記事で、「実装重そう」とか言いましたが、よくよく考えたら全然そんなことはなかったので、ぱっぱと実装します。
まだ実装途中ですが、最初に書いた貪欲の部分でミスを見つけたので修正して投げます。なんとびっくり1184980点！139位です。最初のミス痛すぎる…。
そして縦方向の実装も終わりました。手元だとなかなかいい記録が出ているので楽しみです。はい！1362148点！！！順位は64位！！！貪欲実装し直してよかったです(´▽｀)
点数計算の高速化
今までの感じを見てみると、あんまり多くの値をいっぺんに変化させるのは良くないようです(1~10個くらいが良さげ)。また、今回縦も考慮して実装したことで、貪欲がより局所解に近づいたような気がします。そこで、値を変化させる場所を一点に絞り、点数計算を高速化して、試行回数を増やすことを試すことにしました。
変化させるマス目が1個であれば、その行と列だけ見れば差分計算ができるので、点数計算にかかる計算量がO(N^2)からO(N)に改善されます。
提出しました。1378183点！59位まで浮上しました！
焼き鈍しを行う
自分的にはそこそこ納得のいく形で山登りが書けたので、これをなましていきたいと思います。どれくらいの悪化をどれくらいの割合で許容すればいいのかあまり見当がつかなかったので、実験してみます。具体的には、ランダムで値を一つ変更したときの、全体の点数の上下を見てみます。
赤丸がexample1、青丸がexample2、黄丸がexample3です。縦軸が点数の変化量、横軸に変化させた回数を示しています。
マイナスになるような変化が圧倒的に多いことから、最初から既に局所解に近い位置にいることが想像できます。
結局どうすべきかよくわからなかったので、
- 点数がより良くなった場合は常に遷移
- 点数が悪くなった場合でもある確率で遷移(確率は以下のように定める)
- 序盤(時刻t=0に近いとき)ほど高確率で、終盤(t=3000に近いとき)ほど低確率
- スコアが悪くなった量が大きければ大きいほど、低確率
という感じで実装してみます。ずっと言っていますが、この問題の評価関数は、山の麓が広く、頂点のほうが急激にとんがっているようなグラフになる予感がするので、指数関数っぽい感じで遷移を絞ってみたいです。
実装しましたが、手元では全然いい結果が出ないです。
提出しましたが微妙ですね…。1374506点です。
まとめ
焼き鈍しの関数何入れていいのかわからないです。いろいろ考えてみましたが、さすがに疲れてきたので、今までの流れをまとめて「マラソン勉強するぞ！~過去問演習編~」を終わりにします。
書いてきたプログラムとその順番は、早い方から
- 貪欲
- 乱択貪欲
- 多点スタート山登り
- 多点スタート山登り(貪欲改)
- 多点スタート山登り(貪欲改・点数計算コスト減)
- 多点スタート焼き鈍し(貪欲改・点数計算コスト減)
です。ベストスコアは5つ目で、1378183点でした。
初めてまともに取り組んだ割には、いい点数を残すことができたかなと思います(好きなだけ時間をかけれたので当然かも)。このコンテストは公式解説が無いので、twwiterで他の方の解法を見て、気づいたことや改善案が見つかれば、そちらを~復習編~と題してまとめるかもしれません。個人的には、焼き鈍しの温度関数・遷移確率関数の設定の仕方が全然わかっていないので、もっと勉強したいです。
AHC001のマイ解法も、コンテストが終わり次第記事を通して共有したいと思っているので、そちらも読んでいただけると嬉しいです。最後まで読んでいただきありがとうございました。
