探索問題

特に難しい話ではないんだけれども。復習を兼ねて。


こんな問題を考える。

横Wマス縦Hマスのフィールドがあります。
フィールド上には床マスと岩マスの2種類のマスがあります。

岩があるマスは通り抜けることが出来ません。
ただし、岩の移動先が床マスである場合、岩を押すことが出来ます。

床マスのうち、1箇所をスタート地点、別の1箇所をゴール地点とします。
スタート地点からゴール地点に到達できるでしょうか?

…どこかで似たようなコンテストがあった気がしますが。

入力はこんな感じ。期待される答えはYES。
外周2マスは岩マスであることが保証されている。つまり、ちゃんと実装すれば外枠判定を実装しなくても良い。
12 10
@@@@@@@@@@@@
@@@@@@@@@@@@
@@....@..@@@
@@.S.@.@.@@@
@@...@@@@@@@
@@..@@.@..@@
@@@@.@@.G.@@
@@...@....@@
@@@@@@@@@@@@
@@@@@@@@@@@@


2016/10/25 修正



状態遷移っぽく書きたいので、クラスを幾つか定義した。



普通の迷路探索問題は、フィールドが変化しない。なので、今キャラクタがどこに居るか、を状態として把握すれば良いはず。
状態数のオーダーは%$O(wh)$%。

しかしこの問題は、岩を押すことによってフィールドが変化するので、現在座標の他に現在のフィールドを状態として持つ必要がある。大変。
実装を確認するとStateクラスでは、フィールドの情報を保持しているのが分かる。

『フィールドを状態として持つ必要がある』と言っているが、フィールドって何パターン存在するだろうか。
簡単のため、周囲の固定岩マスを除いた岩マスの数を%$n_r$%とすると、大雑把に計算して
%$\binom {(w-4)(h-4)} {n_r} \lt O(w h ^ {n_r}) \lt O(w h ^ {w h})$%
ものパターンが考えられる。計算合ってるか不安になるレベル。

幅優先探索


理論上、普通の幅優先探索やら深さ優先探索やらで求めることができる。

幅優先探索の実装を示します。



最良優先探索


queueやstackの代わりにheapを使う探索。優先度付きキューとも呼ばれている。

heapは、適当に要素をpushして適当にpopすると、計算量%$O(\rm log(n))$%で要素が昇順に出てくるという、高専レベルのデータ構造。
つまり、Stateにゴールまでの距離を比較できるよう実装しておき、heapに投げ込めば、ゴールに近いStateから順にpopされる。

という訳で実装……と思ったらRubyの標準ライブラリにHeap無いじゃないですかやだー

かなり遅いですね…
とりあえず、これを使って最良優先探索を実装します。



優良優先探索(good-first search)


というものがあるらしい。へー知らなかった。
迷路で眺める探索アルゴリズム
http://spheresofa.net/blog/?p=1044

最良優先探索では1つずつpopしていましたが、複数個取り出しましょう、ということですね。

実装



(最良優先)ビームサーチ改良最良優先探索


2016/10/25追記:ビームサーチと説明していましたが、間違っていました。ごめんなさい。
最良優先探索の安価バージョン。
「ヒープの前の方しか使ってないじゃん!後ろの方無駄!」ということで、後ろの方をがっつり削り前だけ残す。
捨ててしまっているので、完全な探索は出来ない。





ビームサーチ(本物)


2016/10/25追記
現在の状態から遷移できる状態の寄せ集めの中から、最大%$k$%個良いものを選ぶ。
そして、選んだ最大k個の状態を現在の状態とする。

ビームサーチが優先探索と異なるのは、キューが持つk個の状態は初期状態からの遷移回数がすべて同じであるということ。

この例題では、遷移回数が評価関数に影響することは少ないけれども、問題内容によっては、遷移回数が同じもの同士で比較することがより良い結果を得るケースもある。ゲームAIがその例。



おわり


自分が一番書きたかった探索法が無いです。ちょっとこの問題は不向きだった。

次の記事で書きます。


テストケース


トップ含め3つしか無いのは作り飽きたからです。
6 8
@@@@@@
@@@@@@
@@S.@@
@@.@@@
@@@G@@
@@@.@@
@@@@@@
@@@@@@
YES
12 10
@@@@@@@@@@@@
@@@@@@@@@@@@
@@S.......@@
@@........@@
@@..@@@@..@@
@@........@@
@@.......@@@
@@......@G@@
@@@@@@@@@@@@
@@@@@@@@@@@@
NO

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : アルゴリズムとデータ構造 Ruby

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>