E = mc2（イー・イコール・エム・シー2じょう、英: E equals m c squared）とは、
の物理学的関係式を指し、「質量とエネルギーの等価性」とその定量的関係を表している。アルベルト・アインシュタインにより、特殊相対性理論の帰結として、1905年の論文『物体の慣性はその物体の含むエネルギーに依存するであろうか』 内で発表された。
この等価性の帰結として、質量の消失はエネルギーの発生を、エネルギーの消失は質量の発生をそれぞれ意味する。したがってエネルギーを転換すれば無から質量が生まれる。
という、謎多き式の画像で始まりましたが、今回の話とは一切関係ないことを反省いたしますです...どうもボクです。
ヒューリスティック探索って何ぞや～？
⇧ 上記サイト様が詳しいです。
というわけで、今回は、ヒューリスティック探索にレッツトライ。
A*（A-star, エースター）探索アルゴリズムって？
さっそくWikipediaさんに頼りますか。
A*（A-star, エースター）探索アルゴリズムは、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」gと「ゴールまでの推定値」hの和を採用したもの。h は ヒューリスティック関数と呼ばれる。
う～ん...この状態じゃまだわけ分からんですね。
A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。
グラフ探索って何よ？
⇧ 上記サイト様が説明してくれています。
カーナビです。つまり、まず、今居る所「スタート」と、目的地「ゴール」があります。通ることの出来る「道路」があって、その途中に沢山「交差点」があります。あなたは一番短い時間、距離でゴールにたどり着きたいと思っています。グラフ探索問題とは、与えられた地図上で、スタートとゴールがあるときに、ゴールまでの最短の行き方を調べるための問題です。
そういうことらしく、
例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。
⇧ この最適なhを見つけることが 重要であると。
⇧ 限りなく0に近づけば近づくほど理想的ということですかね？（<= そういうわけではないようです。）
A*の探索効率はhの正確さに左右される。 もしもhがまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内 --- 一時間、一週間、一年 --- では解を発見できない場合がある。
⇧ さらっと怖いこと言ってますね...。
しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある(完全性)。
⇧ いや、いつかって全然保証になってないですね....。
一方、hが常に正しい値h*を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ。
⇧ パーフェクト・ヒューリスティック！
現実に用いられる有用なhは、これらの中間の位置にある。A*の性質はhの性質によって大きく左右される。関数h(n) は常に非負でなくてはならない。
⇧ 現実の厳しさ...。 要するに、h(n)>=0 が絶対条件ということらしいっすね。
ヒューリスティック探索って?
どうやら、A* == ヒューリスティック探索ってことみたいですかね。
A*は「ヒューリスティック探索」とか「発見的探索」と呼ばれます。この名前が悪くて、おかげで、酷い誤解を受けています。例えばあるスライドでは、A*は「近そうなところから探索」と書かれています。なんか適当に探索するかのような印象ですね。A*は、ダイクストラ法を拡張し、 理論的裏付けを持った下界を用いてグラフを探索するための手法 です。
⇧ 上記サイト様が詳しいです。
探索するグラフによって最適なh（ヒューリスティック）を見つけて行きましょう、ヒューリスティックを探索していきましょうってことで、 ヒューリスティック探索ってことですかね？
もしくは、理想的なヒューリスティックを使って探索するということで、ヒューリスティック探索ですかね？
つまりは、まずは、問題となるグラフありきということになりますかね。
ヒューリスティック探索で15パズル
せっかくなんで、15パズルというものをJavaで実装してみたいと思います。
その前に、15パズルって何ぞ？
15パズルは、スライディングブロックパズル（Sliding puzzle）のひとつである。4×4のボードの上に4×4-1すなわち15枚の駒があり、1駒ぶんの空きを利用して駒をスライドし、駒を目的の配置にする。3×3のボード上で8枚の駒で同様に遊ぶものは8パズルと呼ばれる。m×nのボードとm×n-1個の駒（m, n ≧ 2）に一般化できる。右下の隅または左上の隅を空きとした配置を最終目標とするものが多い。
⇧ Wikipedia 様の見解。
n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。
8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。
簡単なソルバーをプログラミングする場合、評価関数を各駒の目的の位置までのマンハッタン距離の和とするのが手頃である。
Wikipediaさんによりますと、「数字を渦巻き」状にするような問題だと、
⇧ のようになるようなアルゴリズムを考えないといけないらしい...
そんでは、Java で15パズル問題にトライ。今回は、Paiza 様の問題。
15パズルとは、1～15の数字が書かれたタイルを4x4の合計16マスからなる枠の中でスライドさせ、並び替えるゲームです。 タイルのない空マスの四方に隣接するタイルを空マスへ移動することでゲームを進行します。
例えば、次の図のようにゲームを進行することができます。
タイルをスライドさせ、盤面を完成させるプログラムを作成してください。 ただし、最短の手数でパズルを完成させる必要はなく、盤面を完成させることができるならば、どのような順番でタイルをスライドしても構いません。
Rena and Minami International Programming Competition |Paiza Online Hackathon 5
⇧ 「右から来たものを左へ受け流すの歌」じゃないけども、左から右へ受け流す～、という思いで、左から順々に並べていくアルゴリズムですかね。
⇧ Paiza の記事で紹介されていたQiitaの「@uwi@github」 さんの記事。
- Pattern Database
- IDA* -- Iterative Deepening A* -- 反復深化A *
- 両側探索
- Greedy algorithm -- 貪欲法
- ビームサーチ
- 幅優先ビームサーチ
- 最良優先ビームサーチ
など、正直、聞いたこともないレベルの高い話に、付いていけないっす...っていうか、この人、専門的に研究されてたような人なんでしょうね...
なんとなくですが、「Pattern Database」とそれぞれの『探索法』を組みわせるというイメージですかね？
「Pattern Database」については、
The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15-Puzzle, iterative-deepening A* with pattern databases (N=8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000-fold.
⇧ 上記サイト様が詳しいです...pattern database の使用で、探索の効率がむっちゃ上がるらしい、よく分からんけど。
「IDA*」については、
そこでIDA*の出番です。(IDDFSはIDA*の h=0h=0 版です。) IDA*は、答えとなる経路の深さdd, ノードの子の数の平均値bb (branching factor) に対して、最悪でO(bd)O(bd)のメモリしか用いません。
一方、A*(およびDijkstra)は最悪でO(bd)O(bd)、すなわち指数的に大きなメモリ量を要する可能性があります。 IDA* は、用いるヒューリスティクスがconsistentであれば常に最適解を返します。
Rubik's Cube, 15/24-Puzzleなど有名なパズル問題に用いられるパターンデータベース(PDB)ヒューリスティクスは、計算が早くかつconsistentなので、よくIDA*と共につかわれます。
IDA*を一言で表すと、「最大深さを制限した深さ優先探索(DFS)を、深さを増やしながら繰り返す」です。
それぞれのイテレーションでは、最大深さの限界値はグローバル変数として設定しておき、その深さ以上には探索しません。
ここで、「深さ」は正しくはf値です。仮にh=0,f=gh=0,f=gとすると、f値は深さと同義になり、このアルゴリズムはIDDFSと呼ばれます。
⇧ 上記サイト様が詳しいです。
どうやら、「最適解」を見つかるまで、探索を繰り返すようですが、その時の探索する深さを徐々に増していくということらしいです。
探索する回数が増えるから遅くなりそうなイメージなのですが、速いらしいです。
だが、しかし！
IDA*のからくりは、一度探索したノードを忘れることにあります。ノードを忘れてしまえば、メモリを解放できますよね。
IDA*は、一回のイテレーションが終わるたびに、今まで探索された最大のf値 fnextfnext のみ保存します。その他の情報、すなわちグラフやノード、そのf値など、A*ならば常に保存している全ての情報を忘れてしまいます。
この「忘れる」動作のおかげで、IDA*を実行するのに必要なメモリ量は現在スタックに載っている量のメモリだけです。
スタックの長さは解の長さに比例するので、IDA*の線形メモリが示されます。
一方、FFが更新されるたびにノードを忘れてしまうIDA*は、同じノードを何度も展開することになります。
従って、IDA*に重いヒューリスティクスを組み合わせるのは得策とはいえないでしょう。重いヒューリスティクスを何度も計算することになってしまいますからね。
⇧ 条件によっては遅くなることになるようです。
「ビームサーチ」については、
⇧ 上記サイト様が詳しいです。
「ビームサーチ == 動的計画法（Dynamic Programming, DP）」ということらしいです、っていうか、『動的計画法』とか、また知らん言葉が出てくるし...先に進めないやんけ～（涙）。
巷では、「DP」と呼ばれるのが一般的らしいですが、
⇧ 上記サイト様が詳しいです。
「ビットボード」 については、
⇧ 上記サイト様が詳しいです。
Wikipediaさんによりますと、
ビットボード（英語: bitboard）はチェスやオセロなどのゲームの局面の状態を表すための方法のひとつ。
「ビットセット (Bitset)」、「ビットマップ (Bitmap)」と呼ばれることもあり、駒・石の種類ごとにそれが存在する場合は1、存在しない場合は0を盤面のマスの数だけ並べる。
駒の利きや、相手の石を挟んだかどうかなどの判定や、駒の移動、石の反転などの処理をループを使わず、シフトや論理演算だけで複数の駒・石について同時に行うことができる（ビットパラレル性）ため、通常のデータ構造よりも処理が高速になる。
⇧ ということらしいです。
というわけで、諸々について、全然理解できてないんだけども、Qiitaの「@uwi@github」 様のソースを、そのまま使わせていただきました。自分でやったこととしては、クラス分けしたぐらいかな...
Github に公開しましたんで、ご興味ある方は是非是非。
Eclipse上のプロジェクト構成は、
⇧ こんな感じです。
んで、実際の動作確認。入力値はというと、
入力の制約 マス t_i (1 ≦ i ≦ 16) は次を満たします。
タイルが存在するならば、1から15までのいずれかの数字である タイルが存在しないならば、文字'*'である t_iは互いに異なります。 与えらえれる盤面は必ず完成させることができます。 完成した盤面が与えられることはありません。
出力の制約 スライドさせることができないタイル(空マスの四方に隣接しないタイル)をスライドさせてはいけません。 タイルをスライドさせる回数は1,000,000回以内でなければなりません。
Rena and Minami International Programming Competition |Paiza Online Hackathon 5
という...
実行してみます。
入力してみました。
⇧ 無事、動いたようです。
ちょっと、アルゴリズム、ちゃんと勉強しないとですかね...サッパリ分からんですたい...モヤモヤ感が今日も半端ないという...
今回はこのへんで。
