マラソン勉強するぞ!~アルゴリズム編~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
本記事が初投稿になります。
自己紹介
名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/02時点でAtCoder緑です。
AHC001が開催されるぞ~!!!
今週の土曜日、3/6から3/14まで、「AtCoder Heuristic Contest 001」が開催されます。マラソン用の新しいレーティングも整備されるということで、とても楽しみです(*゚▽゚*)
ところで、僕はあまりマラソンの経験がありません。ずっと面白そうだなとは思っていたのですが、AtCoderではあまりマラソンコンテストが開催されてこなかったので、本格的にやる機会がありませんでした。
そこで、AHC001を楽しむためにもある程度勉強をすることにしました。本記事は、その過程の記録です。僕と同じように、ほとんど初めてマラソンをするという方の参考になればいいなと思っています。
tardigradeの対マラソン戦績
大した数は出ていませんが、一応書いておきます。
2020/06/28 Introduction to Heuristics Contest 1654位(1点)
2020/09/27 Chokudai Contest 005 291位(49654250点)
2020/11/07 HACK TO THE FUTURE 2021 予選 463位(144006点)
2020/12/17 Hitachi Hokudai Lab. & Hokkaido University Contest 2020 67位(435756208236756点)
ちなみに、一番最後のコンテストはサンプルコードを投げただけなので、誰でも取れる点数です。これまでのマラソンコンテストは参加者が少なく、順位が高くなりがちなので、どのコンテストも見た目ほどいい成績を残しているわけではありません。
マラソンの勉強をする
どんな勉強をすればいいのかわからなかったので、とりあえず競プロを始めたときにしたことと同じことをします。具体的には
- 頻出のアルゴリズムを勉強する
- 過去問を解いてみる
- 知らない知識がでてきたらそのたびに勉強する
といった感じです。他になにかいい方法を知っている方がいたら教えてください。
頻出のアルゴリズム
まずはアルゴリズムです。ビームサーチや山登り法といったものが存在することは知っているので、その辺を重点的に調べてみます。
貪欲法
これはABCなどでも頻出ですので、あまり説明はいらないかと思います。その時その時で最善の手を選び続ける方法です。マラソンでも、最初は貪欲法で組んでそこから改善出来るところを探す、ということをよく行うみたいです。
ビームサーチ
ビームサーチは、貪欲法の考え方を発展させたアルゴリズムのようです。貪欲法が最善を選び続けるのに対し、ビームサーチは上からk番目までの手を選んだときの遷移を考えます。図にするとわかりやすいです。
黄色い部分(選んでいる手)がビームに見えるのでビームサーチと呼ばれるみたいです。また、kのことをビームの幅と言います。ビーム幅を広げると、遷移に多様性が生まれますが、その分計算量やメモリは食うので注意です。
chokudaiサーチ
個人的に一番気になっていたアルゴリズムです。詳しい説明はchokudaiさん本人がブログで書いていらっしゃったので、そちらをどうぞ。
個人的な感想としては、BFSとDFSの関係に近いかなぁと思いました。ビームサーチがBFSでchokudaiサーチがDFSです。もちろん得られる遷移もその多様性も違うので、全然正しい表現ではないんですけどね。
山登り法
調べてみると、イメージ通りというか言葉通りというか、結構シンプルな方法でした。
山登り法ではとりあえず何でもいいので一個解とそれに対するスコアを算出しておきます。そして、「解を少し変えたとき、スコアが良くなるのであればそちらを採用する」ということを延々と繰り返します。これだけです。
山登り法のメリットは、実装が単純であること。対してデメリットは、局所解に陥りやすいということです。
デメリットの部分を少し補足します。前述した山登り法の説明を「登山」に置き換えてみると、「解を変えること」と「場所を移動すること」、「スコア」と「標高」がそれぞれ対応します。山が一個しかない場合、登山をしていればいずれ一番標高の高い場所に移動できます。一方で山が複数ある場合は、登り切った山の標高が存在する山の中で一番高いとは限りません。そして、「登山」は下ることを考えないので、その場所から移動できなくなってしまうのです。この状態を、山登り法では「局所解に陥る」と表現します。
焼き鈍し法
これは、山登り法を調べていく中で知ったアルゴリズムです。山登り法のデメリットとして局所解に陥ってしまうことを挙げましたが、ここではそれを回避することについて考えてみましょう。
山登り法で局所解から抜け出せない原因は、「スコアを上げる方向にしか移動できない」という点にあります。もともとはより良い解を出すために課した制限のはずなのに、今度はそれがあだとなってしまっているわけです。
それなら、ある程度スコアが悪化することを許容しちゃえばいいんじゃね?というのが焼き鈍し法の考え方です。より具体的には、
- スコアが低いうちは改悪をがんがん許容
- スコアが良くなってきたらちょっとずつ許容しなくなる
- 最終的には山登りとおんなじことをして解を求める
ということを行います。山登り法では単純にスコアが良くなる方に遷移していけばよかったのですが、焼き鈍し法では「どの程度の改悪を許容するのか」や「どの程度の確率で新しい遷移をするのか」といったことも決定する必要があります。実装は少し複雑になりそうですが、この辺のパラメーターの調整作業ってとても楽しそうですね(*´▽`*)
少し発展的な話になりますが、山登り法や焼き鈍し法は、多点スタートにしたり、複数の状態を保持(状態プール)したりすることもできるようです。オプションまでたくさんつけられるなんてめっちゃ面白そう!
粒子群最適化
英語名の頭文字をとってPSOとも呼ばれます。これ、僕は初耳だったのですが、焼き鈍し法を調べているときに見つけて面白そうと思ったので共有します。
粒子群最適化は、その名の通りたくさんの粒子(スコアを計算する解、標高を調べる場所)が必要になります。粒子群最適化は鳥の群れが餌を探す様子に着想を得た手法であるようなので、ここではその粒子を鳥に、スコアを餌の多さに例えて説明します。
まず重要なポイントとして、各鳥は速度を持っています。飛んでいるから当然と言えば当然かもしれません。そして、各鳥は今まで自分が通った場所の中でもっとも餌の多かった場所と、群れに属する鳥のいずれかが通った場所の中で最も餌の多かった場所の情報を常に保持しています。それらをもとに鳥の位置を修正する作業を繰り返していくと、最終的にすべて鳥の位置が一点に収束するようです(最適解が複数ある場合は収束しないっぽい)。
具体的な式だったり初速度の与え方だったりとかは、ぱっと調べた感じ難しくてよくわからなかったので、ここでは省略させてください<(_ _)>
感想
当初思ってたよりいろんな方法がありました。調べている最中に、「焼き鈍し法とビームサーチは二項対立の構図は適切でない」という記事を見かけて、とても興味深かったので共有させていただきます。
次回予告
本当は過去問演習までで一つの記事にしたかったのですが、思ったより長くなってしまったので二つに分けたいと思います。
次回の記事では、実際に過去問を解きながら、着眼点とか考え方とか発想の様子とかを共有できたらと思います。