AIアルゴリズム

どんな学問についても言えるけど、最初は浅く見える学問領域でも、知れば知るほど深く見えてくる。人工知能なんてものはまさにそうで、実際まだまだ未解決問題がたくさんあって(だからこそおもしろいといえるかもしれないけど)、発展途上の学問領域だということを最近知った。近頃では、GoogleやAmazonで見られるようなWebインテリジェンスや知的エージェントの研究が盛んなようで、商業利用のAIはこれからますます需要が増えると予想されてるそうな。人工生命だけが人工知能の利用法ではないというわけか。

＜メモ＞
探索木の例(Sがスタート地点）

・深さ優先探索 depth-first-searchのアルゴリズム

1　初期節点をopenに入れる。
2　LOOP：if open = 空 then exit(fail)
3 n:=first(open)
4 if goal(n) then exit(n)
5 remove(n,open)
add(n,closed)
6 nを展開し、openあるいはclosed野中に含まれない子節点だけをopenの先頭に入れ、そのおのおのからnへのポインタをつける。
7 goto LOOP

1のopenというのはこれから調べるべき探索木の節点のこと。
2のLOOPは繰り返すこと。繰り返す内容は「:」の右側の文で、それはopenリストに何もなければ終了する。つまり探索の失敗。
3は2が当てはまらない時、nをopenリストに入れることを表す。
4はもしnが目標節点ならば終了することを表す。
5はnをopenリストから削除し、closedリストに追加することを表す。closedリストとは探索済みの節点のこと。
6はopenリスト(これから探索する節点リスト)やclosedリスト(探索済みリスト)に既に含まれている節点を再び探索しないようにするため。発見した節点を先頭に入れるのは深さ優先探索アルゴリズムの特徴で、発見した節点から順に探索するため。
7は2へ戻ることを表す。

上の下手な探索木の図の例では次のような順序で探索する。
A→C→D→B→E→H→G→F

・幅優先探索 breadth-first-search

1　初期節点をopenに入れる
2　LOOP：if open = 空 then exit(fail)
3 n:=first(open)
4 if goal(n) then exit(n)
5 remove(n,open)
add(n,closed)
6 nを展開し、全ての子節点を生成する。子節点のうち、openあるいはclosedの中に含まれない節点だけをopenの最後部に入れ、そのおのおのからnへのポインタを付ける。
7 goto LOOP

6以外は深さ優先探索と同じ。6のとき、最後部に入れることで初期節点から近い節点を優先的に調べることができる。

上の探索木の例では次のような順序で探索する。
A→B→C→D→E→F→H→G

他にもたくさんの探索アルゴリズムがあったりするけど、今はこれくらいにしよう。

ところでこのプログラムは応用すれば、地図の目的地への最短距離を探すプログラムが書けるんじゃないかな。駅すぱあととかはやっぱりこういうアルゴリズムの拡張版を使ってるのだろうか？でも地図みたいに巨大な対象をアルゴリズムで扱うことができるのかね？最近のパソコンは処理能力は高くなってるけどどうなんだろう。いかんせんコンピュータ関係に対してまだまだ経験がほとんどない自分としてはよく分からないな。