最近はC言語系の記事ばっか書いてるんでさすがに疲れた。
やっぱ、C言語が嫌いなんだなぁ、って実感してる(笑)。
しかしまだ書く事があるんだ。
でもちと小休止して、気晴らしにLispの記事を書く。
マジでLispに戻ってくるとホッとする(笑)。
さて、今回は、「人工知能」の基礎テクニックである探索の基礎をやろう。「探索」と聞けば「難しそうだ」と思いがちだが、基礎に絞ればそうでもない。
まぁ、何でもそうなんだけど、まずは「どういうデータを設計するか」が最初に来て、そのデータに従った関数を書けば良い、ってだけの話ってば話になる。
そしてそこで使うデータ構造は「木」と呼ばれるモノを使うか、あるいは「ネットワーク」と呼ばれるモノを使うか、と基本的には二択だ。
まぁ、場合によっては「データを生成しながら探索をかける」って事もあり得るんだけど、とりあえず入門編としては「既に固定されたデータ型がある」って事にしよう。
今後、GLibの方でも「木」を取り扱う事になりそうなんで、丁度良いタイミングだって言えば良いタイミングとなる。
1. 属性リスト
さて、本論へ行く前に先にちょっとしたユーティリティを作ろうと思う。今まではモダンな抽象データ型として、Pythonでは辞書型、Lispでは連想リスト、ハッシュテーブル、二分探索木を扱ってきた。
今回はRacketで、ANSI Common Lispの機能のエミュレートとして属性リスト(p-list: property list)と言う機能をまずは実装してみよう。これは別に探索で必須の機能ではないけど、あれば論が展開しやすい、っつーか実装が簡単にはなる。
属性リストとは、単純には、シンボルとリストを結びつけて、そのリストの中身が
(属性0 値0 属性1 値1 属性2 値2 ...)
と属性と値が交互に並んでるモノを言う(※1)。そして例えば属性1を指定すると値1が返ってくる、と言うような事が出来るわけだ。
ある意味、連想リストと変わらない、って言えば変わらないんだが、ただし、カッコを要さないんで、書きやすい、と言う利点がある。
ここでは属性リストを大域変数として定義する。そしてこのブログでは珍しく、「破壊的変更」を用いて実装する。と言うのも、そもそもANSI Common Lispでのプログラムの「仕組み」自体は大して「関数的」でもないから、そのうちの1つをエミュレートするなら、大域変数の破壊的変更を行った方が上手く行くから、だ。
そして、属性リストを「大域的に定義した」連想リストで実装しようと思う(※2)。
(require (only-in srfi/1 alist-cons alist-delete))
次に大域変数、*p-list*を空リストとして設定する。
(define *p-list* '())
これを破壊的変更して、属性リストを得る事とする。
次に、ANSI Common Lispのsymbol-plist関数をエミュレートする。
(define (symbol-plist sym)
(cond ((assq sym *p-list*) => (lambda (x)
(cdr x)))
(else null)))
これは、例えば*p-list*が
(define *p-list* '((Mary #:occupation lawyer #:children (Bill Susan Alice) #:sex female #:age 28)))
のような状態だった時に、シンボル'Maryの属性リストの中身を全部取り出す為の関数だ。
> (symbol-plist 'Mary)
'(#:occupation lawyer #:children (Bill Susan Alice) #:sex female #:age 28)
この属性リストに対して色々と操作していくわけだ。
次に、属性を指定し、それに関連付けられている値を返す関数、keyword-getを書く(※3)。
(define keyword-get
(case-lambda
((args kw not-found)
(cond ((memq kw (symbol-plist args))
=> (lambda (x)
(cadr x)))
(else not-found)))
((args kw) (keyword-get args kw #f))))
オプショナル引数があり、「属性が見つからなかった場合」、デフォルトでは#fが返るが返却値は好きに変える事が出来る。
> (keyword-get 'Mary '#:age)
28
> (keyword-get 'Mary '#:children)
'(Bill Susan Alice)
ここまでで、既に充分、属性リストは連想リストに比肩するだけの機能を持ってる事が分かるだろう。
次に、属性リストから属性を指定すれば属性とそれに関連付けられた値を破壊的に削除する関数、remprop!を書く。これもANSI Common Lispから持ってきた関数だ。
仕様上、この関数は真偽値を返す。目的とした属性が見つかった時には#tを返し、そうじゃなければ#fを返す。ただし、見つかった場合は、その属性とそれに関連する値を削除して、*p-list*を破壊的変更して何食わぬ顔をする。
最後は属性リストに属性と値を破壊的に追加、あるいは変更する関数putprop!を書く。
(define (putprop! atom val property)
(when (keyword-get atom property)
(remprop! atom property))
(let ((datum (append `(,property ,val) (symbol-plist atom))))
(set! *p-list* (alist-cons atom datum (alist-delete atom *p-list*)))
val))
こういう副作用使いまくりの関数を書く事が無いんで、違和感を感じるかもしんない。when節は「指定した属性が属性リストに含まれてた場合」その属性と関連する値を削除する。しかしそこは「破壊的変更」目的で返り値をアテにしていない。Schemeのwhenって本来こういう使い方を想定してるんだよな(そして同時にこれが逐次処理の実例だ)。
結局、属性があろうと無かろうと、4行目に到達した時には指定した属性と関連した値が無い、ってのは確定してるんで*p-list*を、新しく作ったdatum(symbol-plistで得た属性リストを加工したモノ)をatomに結びつけて破壊的に変更する、と。
なお、返り値がvalになってるのは、ANSI Common Lispの挙動に合わせてるから、だ。
> (keyword-get 'Mary '#:age)
28> (putprop! 'Mary (add1 (keyword-get 'Mary '#:age)) '#:age)
29> (keyword-get 'Mary '#:age)
29
シンボル'Maryの年齢('#:age)が28から29に変更されてるのが分かるだろう。
これでユーティリティ、属性リスト作成は終了だ。ソースコードはここに置いておこう。
2. 属性リストと木/ネットワークの構築
例えばHarryには二人の子、JaneとBillがいて、Janeには二人の子、JoeとDianeがいて、Billにも二人の子、JuliaとMikeがいて・・・と言う状況を考える。
これは次のような木構造として考えられる。
これは作成した属性リストユーティリティを使えば、次のようにプログラムする事が出来る。
(putprop! 'Harry '(Jane Bill) '#:children)
(putprop! 'Jane '(Joe Diane) '#:children)
(putprop! 'Bill '(Julia Mike) '#:children)
(putprop! 'Julia '(Frank Suzan) '#:children)
(putprop! 'Frank '(Anne) '#:children)
木構造としてはある程度の複雑さはあるが、putprop!を使えば5行程度で「シンボルとシンボルのリンク」を表現する事が可能だ。
この時点で大域変数*p-list*は次のようになってるだろう。
> *p-list*
'((Frank #:children (Anne))
(Julia #:children (Frank Suzan))
(Bill #:children (Julia Mike))
(Jane #:children (Joe Diane))
(Harry #:children (Jane Bill)))
*p-list*自体は連想リストとして実装されてるので、これを見れば属性リストを使わずに、直接連想リストで実装するなり、ハッシュテーブルで実装しても構わない、って事が分かると思う(あるいは、データ自体を構造体で書くのもアリだ)。
ただ、実の事を言うと、「この時点」では単一のシンボルと別のシンボル(がいくつあるかは構わないが)のリンク「だけ」はハッキリしてるが、木構造、あるいはネットワークとして表現されてるわけではない。
よって次に、探索の肝、展開関数を導入して、シンボル同士の「結びつきの連鎖」を調べる事とする。
3. 展開関数
とは言っても、展開関数を書く事は超簡単だ。上の例で言うと、あるシンボルに対して'#:childrenの属性に対する値を取り出せばいいだけ、だ。
つまり、keyword-getをラップするだけで展開関数は書ける。
;;; 展開関数
(define (expand person)
(keyword-get person '#:children '()))
ここでは「見つからなかった」際に空リストを返すように書いてる。
いずれにせよ、あるシンボルが与えられた時に'#:children属性を調べれば「シンボルが展開された」と言う意味になる。
;;; Janeの子供はJoeとDianeと言う意味> (expand 'Jane)
'(Joe Diane)
上の図と比較すれば確かにその通りになってるだろう。
そしてこの「展開関数」が探索のキーとなる。
便宜上、木の左側方面から始めるが(理論的には右からやっても同じだ)、節(ノードとも言う)をどんどん終わりまで潜って行って、端を見つけたら1つ戻り、(あれば)もう一つの節に潜って・・・と探索するのを深さ優先探索と呼ぶ。
上の図で言うと、次の経路(赤の矢印)を持つ探索になる。
これは名前付きletを用いて次のように書ける。
;;; 深さ優先探索
(define (depth person1 person2)
(let loop ((stack (expand person1)))
(if (null? stack)
null
(let ((person (car stack)))
(or (eq? person person2)
(loop (append (expand person) (cdr stack))))))))
stackで常にシンボルを展開しつつ、既存のstackの先頭に追加する、と言うのがポイントだ。そうすれば、
(Harry) -> (Jane Bill) -> (Joe Diane Bill) -> (Diane Bill) -> (Bill) -> (Julia Mike) -> (Frank Susan Mike) -> (Anne Susan Mike) -> (Susan Mike) -> (Mike) -> ()
と常にstackの先頭が展開され、「深さ優先」で調べていってるのが分かるだろう。
そしてその過程で「目的のモノが見つかったら」#tを返して探索は終了する。
;;; Billから辿っていってFrankが見つかるか?(FrankはBillの子孫か?)> (depth 'Bill 'Frank)
#t
この「展開しつつ条件に見合うか調べる」と言うのが探索の基本テクニックだ。
なお、stackと言うのはスタックの事で、一般的にはメモリの使い方の1つだ。特徴は後挿れ中出し後入れ先出し(LIFO: Last In First Out; FILO: First In Last Out)と言うシステムで、Java仮想マシンなぞにも使われてるシステムだ。そしてLispとも相性がいい。なんせ、consとcarがその後入れ先出しだから、だ。
以前、メモリの使い方には2種類あって、それがスタックとヒープだ、と言う話を書いた。スタックは上に書いたようなモノで「そうじゃない」のをヒープと呼ぶ、と。と言うのもヒープを説明するのがメンド臭い(と言うか正確な定義がない)から、だが、実はこの説明は正確じゃない。
と言うのも、メモリの使い方にはもう1つあって、3番目の使い方をキュー(Queue: 待ち行列)と呼ぶ。
キューはスタックと対象的に「先入れ先出し」(FIFO: First In First Out)スタイルのメモリの使い方、だ。銀行なんかの「先に待ってる人が先に受付へ行ける」システムとの類似性で「待ち行列」と訳したりするわけだ。
ラーメン屋の前のQueue(待ち行列)。先に並んだ方が先に食えるわけで、これがStack(後入れ先出し)だったら暴動が起きるだろう。結果、現実世界とStackは相性が悪い(笑)。
いずれにせよ、定義的にハッキリとしている「メモリの使い方」にはスタックとキューがあって、「それ以外」をヒープと呼ぶ、と言った方がより正確になる。
さて、何でキューの話を書いたのか、と言うと、「探索技法の基礎中の基礎」には「深さ優先探索」ともう一つ、「幅優先探索」っちゅうのがあるんだけど、実はこの2つ、殆ど同じなんだ。
違うのは「深さ優先探索」ではスタックを使うんだけど、「幅優先探索」ではキューを使う、と。
それだけが違いなんだ。
なお、深さ優先探索のサンプルコードはここに挙げておく。
例えば次のような木構造を考える。
これを属性リストユーティリティで実装すれば次のようになる。
(putprop! 'a '(b c) '#:subnodes)
(putprop! 'b '(d e) '#:subnodes)
(putprop! 'e '(i j) '#:subnodes)
(putprop! 'c '(f g h) '#:subnodes)
(putprop! 'g '(k) '#:subnodes)
大域変数*p-list*は次のようになってるだろう。
> *p-list*
'((g #:subnodes (k))
(c #:subnodes (f g h))
(e #:subnodes (i j))
(b #:subnodes (d e))
(a #:subnodes (b c)))
さて、幅優先探索とは、同じレベル(高さ)にある節(ノード)を全部調べて、その後で1つ深度を深める、と言う探索方法だ。探索経路的には次のようになる(赤い矢印が探索経路)。
これを実現するには、先程も書いた通り、スタック使用の代わりにキューを使用すればいい。
;;; 幅優先探索
(define (breadth start)
(let loop ((queue `(,start)))
(if (null? queue)
null
(let ((node (car queue)))
(if (keyword-get node '#:success)
node
(loop (append (cdr queue) (expand node))))))))
展開関数はこうだ。
;;; 展開関数
(define (expand node)
(keyword-get node '#:subnodes '()))
この幅優先探索関数は'#success属性を持つノード(節)を発見した時点でそのノードを返してくれる(それは与えてないが、putprop!を使って適当なノードに'#success属性を与えて実験してみて欲しい)。
そして、幅優先探索関数breadthの実装の殆どは深さ優先探索と同じなのが分かるだろう。違うのはスタックの代わりにキューを使ってるトコだ。Lispだと先頭からノードを取り出す方がやりやすいんで、「展開したブツ」はキューのケツから追加していってる。そこだけが違いだ。
結果、キューとその先頭の展開過程は、
(a) -> (b c) -> (c d e) -> (d e f g h) -> (e f g h) -> (f g h i j) -> (g h i j) -> (h i j k) -> (i j k) -> (j k) -> (k) -> ()
となり幅優先になってるのが分かるだろう。「展開してはケツに追加」の効果がこれだ。
なお、幅優先探索のサンプルコードはここに置いておく。
6.徹底探索/力まかせ探索/しらみつぶし探索(BFS: Brute-Force Search; Exhaustive Search)
「お姉さまを徹底探索♥」(違
今までの探索関数は「お題に見合ったノード(節)が見つかると」そこで探索をストップしてた。
しかし、場合によっては「条件に見合うノード(節)が複数存在する」場合もあるだろう。それを全部拾うには?
そういう場合の探索を徹底探索/力まかせ探索/しらみつぶし探索、と言う。
ここでは5. の幅優先探索関数を改造して徹底探索関数にする。
とは言ってもこれも簡単だ。
;;; 徹底探索
(define (exhaustive start)
(let loop ((queue `(,start)) (result '()))
(if (null? queue)
result
(let ((node (car queue)))
(loop (append (cdr queue) (expand node))
(if (keyword-get node '#:success)
(cons node result)
result))))))
今までは、例えば(keyword-get node '#:success)なんかが#tを返した時点で探索を終了してたが、ここでは探索を終了する代わりにresult変数に見つかったノード(節)をconsしている。そしてキューが空になるまで、つまり、木の全部の節を調べ終わるまで探索は終了しない。
そこだけ、が違いだ。
なお、「目的を見つける」と探索を即終了する関数と違って、この「徹底探索」は計算コストは結構かかる(だから「力まかせ」なんだ・笑)。
また、このテの実装は深さ優先探索関数を改造するより幅優先探索関数を改造した方が良いだろう。
徹底探索のサンプルコードはここに置いておこう。
7. ネットワーク探索
今までは木構造を相手に探索していた。
ここでは木構造の代わりにネットワークを探索してみる。
ネットワークは木構造に似てはいるが、端的に言うと、
子ノードが複数の親を持ちうる
と言う辺りが違うんだ。
つまり、木構造は「分岐」だけが基本だが、ネットワークは「分岐」の他に「合流」があり得る。また、そのために、孫ノードから自分に向かっての「流入」さえあり得る。
従って、データ構造的には無限ループを起こしやすい、と言う事になる。
ネットワークの簡単な例
;;; 上の図のネットワークを属性リストユーティリティで実装した例(putprop! 'Start '(a b) '#:subnodes)
(putprop! 'a '(e c) '#:subnodes)
(putprop! 'e '(g h) '#:subnodes)
(putprop! 'b '(c f) '#:subnodes)
(putprop! 'c '(i j) '#:subnodes)
(putprop! 'f '(k l) '#:subnodes)
(putprop! 'l '(b) '#:subnodes)
上のネットワークの例示だと、ノードcはノードa、ノードbから「合流」してる。
また、ノードb、ノードf、ノードlの間には「循環」が生じてる。
こういうのがネットワークでは当たり前で、今までの探索関数だと太刀打ちが出来ない「データ構造」だろう。
とは言っても解決策は簡単で、一端調べたノードを記録しておき、再度そのノードに出会った時には展開せずにスルーする、と言うのがテクニックになる。
;;; ネットワーク探索
(define (network-depth node1 node2)
(let loop ((stack (expand node1)) (visited '()))
(if (null? stack)
null
(let ((head (car stack)) (tail (cdr stack)))
(or (eq? head node2)
(loop (if (memq head visited)
tail
(append (expand head) tail))
(cons head visited)))))))
ここでは4. の深さ優先探索を改造している。
ノードを辿る度に変数visitedにノードがconsされていく。
また、stack上でノードを展開する際に、変数visitedにそのノードが既に存在するかどうか調べ、無かった場合は展開するが、存在した場合にはそのノードを捨てるようにしてる。
これで「子ノードに複数の親ノードがある場合」や「経路に循環構造がある場合」を避けるわけだ。
ネットワーク探索のサンプルコードはここに置いておこう。
8. 経路探索
今までは目的とするノードが「見つかった」「見つからなかった」だけがトピックだったけど、「目的のノードまで至る経路」が重要になる時の方が多い。
特にネットワーク上の探索にその気がある。
ここでは4. のHarryから始まる家系図に対して、「とあるノードから目的のノードに至るまでの」経路を記録して返す関数を書いていく。
とは言ってもこれも簡単で、ネットワーク用探索関数だった前項のnetwork-depthを改造すればいい。
(define (related person1 person2)
(let loop ((stack `((,person1))) (visited '()))
(if (null? stack)
null
(let ((head (car stack)) (tail (cdr stack)))
(let ((person (car head)))
(if (eq? person person2)
(reverse head)
(loop (if (memq person visited)
tail
(append (expand-path head) tail))
(cons person visited))))))))
基本的なアイディアはnetwork-depthとまるっきり同じで、一回訪れたノードは変数visitedへとconsされる。
ただし、stackの構造が1つ深く設計されていて、また、呼び出す展開関数が「経路へと」展開されるモノが使われる、と言うのが違う。
;;; 展開関数
(define (expand person)
(keyword-get person '#:children '()))
(define (expand-path path)
(let loop ((temp (expand (car path))) (result '()))
(if (null? temp)
result
(loop (cdr temp) (cons (cons (car temp) path) result)))))
関数expand-pathは展開関数expandを利用して「経路」を記録していく。
例えば'(Bill)がpathに与えられると、返り値は'((Julia Bill) (Mike Bill))となり、これはBill->Juliaと言う経路とBill->Mikeと言う経路が2つある事を示す。
また、Bill->Juliaと言う経路から何が得られるか、と言うとBill->Julia->Frankと言う経路とBill->Julia->Susanと言う経路が存在する事を教えてくれる。
> (expand-path '(Bill))
'((Mike Bill) (Julia Bill))
> (expand-path '(Julia Bill))
'((Susan Julia Bill) (Frank Julia Bill))
これを利用してstackに「経路情報」を積んでいくわけだ。
> (related 'Bill 'Anne)
'(Bill Julia Frank Anne)
経路情報を返すサンプルコードはここに置いておこう。
とまぁ、これが「探索技術」の基本だ。
この先となると、ネットワーク上での最短経路を探すダイクストラ法なんかが出てくるが、それは今回のテーマを超えるので割愛する(※4)。
いずれにせよ、「探索」の基本技術はここで紹介した5つで学べると思う。ここがスタート地点で、いろんな「探索」へと発展していける。
そして、ここに挙げた5つは全てテクニックを共有してる事も分かるだろう。
まとめると、
- 探索するノードの候補を得る為に「展開」する。
- 「展開したノード情報」は、深さ優先探索の場合はスタックに積み、幅優先探索の場合はキューへ積む。
- 全部のノードを調べるならマーキング用の変数(リスト)を用意してそこに訪れたノードを記録しておき、スタックやキューが空になったら全探索は終了してる。
- ノードを展開する際に、必要なら経路を記録しておけば良い。
と言う事だ。
ここをスタート地点としていろんな「探索テクニック」を身につけて欲しい。
※1: 正確に言うと、ANSI Common Lispでは属性リストはそんな簡単な実装になってるわけではない。リストの中身はその通りだが、属性リスト用の名前空間はまた別に存在してて、属性リストはシンボルに内部的に「直に」結び付けられたモノになっている(C言語風に言うと、構造体「シンボル」は「属性リスト」と言うメンバ変数/スロット/フィールドを持っている)。それはインタプリタ上で、シンボル名を変数名としてリストを「束縛する」と言うのとは次元の違う事をやってるって意味だ。
従って、属性リストとはANSI Common Lispのシンボルの「基本機能の1つ」となる。
結果、ANSI Common Lispでは1つのシンボルで、値、関数、属性リスト、と最低でも3つの意味を「同時に」持たせる事が可能で、Schemeのシンボルよりも遥かに強力だ。
※2: 属性リストはSchemeの仕様書には存在しないし、Racketも持ってないが、一方、Scheme実装によってはシンボルに属性リストの機能を持たせたモノも存在する。例えばGNU Guileなんかはそう言う機能を持ってて、フツーのScheme実装よかシンボルの機能は高機能になっている。
※3: この関数名は、RacketがMzSchemeだった頃にあった関数名から持ってきてる。ただし、オリジナルのこの関数は、後方互換性の為にライブラリ関数として遺されてはいるが、現在では非推奨。
※4: ダイクストラ法は書籍「プログラミングの基礎」の大きなテーマの1つだ。
基本となるアイディアはこのページから辿る事が出来る。
 | プログラミングの基礎 ((Computer Science Library)) 浅井 健一 サイエンス社 |
 | これがLISPだ! (Information & computing (30)) 浩, 玉井 サイエンス社 |
