f:id:tsurutan:20150515122712p:plain

現在私が通っている大学で人工知能についての授業をうけました。この授業をうけて探索の面白さを知りました（小並感）。ということで、この楽しさを皆さんに分かち合ってもらいたいとおもい人工知能【探索】を組み込んだ8パズルゲームを作ってみました。

実装した探索

幅優先探索

f:id:tsurutan:20150519163158g:plain

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズムである。

双方向探索【幅優先探索】

双方向探索（英: bidirectional search）とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う

f:id:tsurutan:20150519162744g:plain

A*（A-star, エースター）探索アルゴリズムは、探索アルゴリズムの一つ。スタートノードからゴールノードまでの経路を計算する、このとき求める経路が最良（最短）であることを保証しているアルゴリズムである

f:id:tsurutan:20150519163209g:plain

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。

上記のような感じで探索を8パズルゲームに実装してみました。またこの探索の早さを比較するため以下の様に定義をしました。

実際に動かしてみるとこのようになりました。

f:id:tsurutan:20150515221537p:plain

幅優先探索は圧倒的にStep数が多いですが、双方向から探索することによってStep数を減っています。またA*探索、深さ優先探索はStep数は多くないですが、TimeがStep数が最も多い幅優先探索より多くなっています。みなさんもお持ちのAndroidで試してみてはいかがでしょうか？