北大日立マラソン1stで考えるマラソン入門

前提

https://beta.atcoder.jp/contests/hokudai-hitachi2017-1/tasks/hitachi2017_1_a

この問題を前提にして、他に

  • 山登り、焼きなましの概要は分かってる
  • マラソンに1度くらいは参加したことがある

を満たしていると、分かりやすいかもしれません。

80点を目指して

マラソンをやる上で、勝とうとした時に基本方針が違うと絶対に勝てません。
何で勝てないの、と問われると簡潔な答えは持っていなくて、経験則なやつです。
今回で言えば、山登り系は焼きなましに勝てない。

基本方針といっても膨大にある訳ではなく

  • 山登り系(ビームサーチ・chokudaiサーチ等)
  • 焼きなまし

の2択です。
ほとんどのマラソン問題が何れかの解法になります。(異論でそう)

まずこの2択を間違うと上位に入ることが難しいので、これを正しく選択するのがマラソンの入り口かなと思っています。
(自分もよく間違う)

型にはめる

!!!蛇足!!!

マラソンマッチにおける精神論 - chokudaiのブログ

chokudaiさんの記事より引用

今回は関係ないけどさ、これないとマラソンマッチは死ぬし、これがマラソンマッチで一番技術的に大切なことだと思うんだけど、みんな型にはめるの大好きだから、やれビームサーチだの、やれ焼きなましだの言うんだよね。そんなん最初覚えないでいいっつーの。最適化に必要なのは、「出来たものをちょっとだけ変える」とか、「出来るだけ小さい単位で構成していく」とかで、そこの一つの実装方法としてビームサーチやら焼きなましがあるだけなんだから、それに固執させるのは絶対良くないと思うんだよね。まぁそれで強い人が出てきちゃってるからきっとそれでもいいんだよね。うん。なんか気に食わないけど。

chokudaiさんの意図を正確に理解できているか謎だけど、自分の考え、この記事の目的と真っ向から反する感じで面白いので紹介。
マラソンの本質的なものという観点でいえば、chokudaiさんと何も相違がない。だけど、モチベーションの問題として基本方針を間違うと上位陣と必要以上に実力の差を感じるし、基本をおさえると序盤とかはとくに簡単に上位に入れるので、マラソンを続けるために型にはめた方が楽だと思います。

方針の見分け方

それぞれの方針には特性があって、それを正しく認識してるのが強いマラソンプレイヤーです。
そういう意味で、これは今自分が認識していることになるので、そのくらいのレベルと認識して下さい。

マラソン強い人は最初から正しい方針であることがすごい多い!

焼きなまし

初期状態がそのまま解になる

焼きなましをやるにはいくつかの必要条件があって、その1つがこれです。
適当な例が思いつかないのですが、将棋等のターンを含む問題は、焼きなましにするのは難しいです。
将棋は2人ゲームですが、1人ゲームでターンでゲームが進行しスコアを最大化するタイプの問題の場合は、大体ビームサーチです。

近傍がシンプル

今回の問題では、2頂点のswapが基本的な近傍だと思います。
これは極めてシンプルですが、近傍が複雑な適当な例が思いつかないので、思いついたら追記します。。。

何で、近傍がシンプルである必要があるかといえば、イテレーションを増やすためです。
焼きなましは、イテレーション=正義みたいなところがあり、複雑な近傍は計算が重くてイテレーションが減るため大抵うまくいかない印象です。

イテレーションは特に重要なので、実装をする前に処理が軽そうか考えると良いと思います。

解空間がそこまで大きくない

焼きなましは局所解に入ってからが本領発揮みたいなところがあるので、解空間が大きくて局所解にもなかなかならないような問題には向きません。

japljさんの画像がわかりやすいので使わせてもらうと、画像の横軸の1000~2000でイテレーションが終わってしまうような問題の場合は、劣化山登りになる場合があるので注意しましょう。

過去にTopCoderで出題されたMM 94で解空間について話題になりました。
この問題は焼きなましできるけど、ビームサーチが正解という問題でした。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678
MM 94 - Togetter


山登り系

山登り(Greedy)とビームサーチ等を、自分は特に区別してなく、同じ特性があると思います。

状態が進行していくような問題

焼きなましの「初期状態がそのまま解になる」と同じ内容ですが、ターンで進行するゲームの問題はほぼビームサーチです。
対戦ゲームのような複数プレイヤーがいる問題は、ゲーム木探索を勉強しましょう。

文脈とは

文脈要素が強い問題は焼きなましより、山登り系の方が良い可能性があります。
文脈とは、自分的理解だとこれまでの決定したきたものが評価する対象になること(自分でも微妙な表現)で、「Aが~こうなっているならば、Bにすると効率が良い」という感じです。
焼きなましはイテレーション内で完結し、それぞれが独立しているので文脈的な要素を受けるのが難しいです。

今回の問題でいえば、辺が極めて少ないテストケースは文脈要素が強そうでした。
極端な例ですが、頂点が2つで、辺が1つの問題の場合

焼きなましの場合
f:id:hoshi524:20171201032655p:plain
赤を緑に隣接させたい場合、かつランダムな頂点をswapするのが近傍だった時、赤がランダムで緑の隣に移動するのは無駄がありそう(全セル/2くらい遷移しないとダメそう)ですが、山登りの場合は赤か緑を置いた後、隣に残りを置くだけです。
ちょっとまった!これはランダムに頂点をswapするのが近傍だった場合の話で、上位の人がやっていたように辺に注目した近傍の場合は、辺が1つしかないので山登りと同様に効率が良いです。
なので今回の問題は、近傍をうまく設定すれば文脈の問題は回避できました。

上に例に出したMM 94は文脈要素も強く、今回の問題のように回避するのができなかったのもMM 94でビームサーチが正解だった要因だと思います。

山登りの欠点

山登りには明確な欠点というか、損をする箇所があります。

f:id:hoshi524:20171201035856p:plain

この中央の頂点を決める時に、評価の対象になるセルは赤、緑、青の3セルのみで、?のセルについては評価できません。
焼きなましは一応全ての周りのセルが評価できるので、その分だけ山登りは最適解がでにくいと考えられます。

今回は焼きなまし

考えてみると今回は焼きなましに都合が良い問題設定でした。
焼きなましの要件は満たしてます。問題の解空間の大きさについては、事前に、実装する前に把握するのは難しいです。
やってみると、そこまで解空間は大きくなくなかなか良いところまで焼き鈍せている印象でした。

焼きなましは要件が多く、適用できないこともあるので適用できそうな問題だったらとりやえずやってみると良いかもしれません。
上にも述べたように、適用できる=焼きなましが正解という訳でもないので、その辺は経験を積んで理解していくところかと思います。

焼きなましの詳細については

焼きなまし法のコツ Ver. 1.2 - じじいのプログラミング
焼きなまし法の真実 – システム工房コルン

焼きなましを主体に扱ったブログあるので、それを参照するのが良いかと思います。

あとがき

自分はそこそこマラソン強いつもりですが、中身は感覚的に理解してるものが多くふんわりしてます。
強い人ほど理論づけがしっかりしてると思いますが、そこそこレベルであればふんわりいけます。

それを超えて、1位になりたいとか、世界クラスと戦おうとする時、根気とか、泥臭さとかが重要になってくるので、そこまで戦うかはその人次第じゃないでしょうか。