はじめに
前回(「LIPS Schemeを使ってみました)に引き続きLipsの記事です。
ピアソン・エディケーション発行の ANCI Common Lisp(ポール・グレアム著) を使って学習しています。20年余ぶりの学習再開です。
「連想リスト」の節で 「最短経路(広さ優先探索:BFS)」 アルゴリズムの実装が例題で掲載されていますが
本文の説明だけではサンプルプログラムの理解に苦労したので備忘録として記事にしました。
LISP学習の環境
動作確認に使っている環境はScheme LispをサポートしているLipsです。学習にはCommon Lispの参考書を使ってますがLispの言語感覚を味わうことが目的なのでOKです。
私のPC利用に関する諸事情によりランタイムパッケージをインストールできないため
ブラウザ(Chrome)からLipsのREPL環境を使っています。
当然ですが時々マクロや関数にCommonとSchemeの方言差が出てCommon系参考書のサンプルをそのまま打つとエラーに出くわすことがあります。ﾟ(∀) ﾟ ｴｯ?
そんな時はAI先生に教えを乞いましょう。この時代! ( ｀д´)b ｵｯｹｰ!
広さ優先探索:BFS[Breadth-First Search]について
BFSとは探索対象の構造（主にグラフや木）を「広がりながら」探索する手法(アルゴリズム)です。(...らしいです。)
参考書のサンプルでは下図のようなネットワークを↓
次のようなリストデータで表現しています。
((a b c) (b c) (c d))
例題では出発点aから目的地dに到達する経路を求めています。
この例題は探索の順番を管理しているキュー(Queue)の使い方がポイントです。
キューにチェックしたノードの値を溜めていき
最終的にキューに保管した リストが目的地までのパスを示すデータになります。
参考書の例題は連想リスト関数(assoc)を使ってキューを実装する例を示しています。
フローは大体こんな感じです。
アルゴリズム実装の練習
Lipsの練習を兼ねてブラウザのREPLで上のフロー図をステップバイステップでアルゴリズムの各処理を体験してみましょう。
※ 「FLW③:キューは空か?」は割愛します。
1.探索対象になるネットワークのデータを格納する変数(net)を定義します。
(define net '((a b c) (b c) (c d)))
2.目的地ノード名を示す変数(end)を定義します。
(define end 'd)
3.キューの役割を担う変数(queue)を定義します。(FLW①)
初期値としてaをセットします。要素が1つだけのリストのリストです。各リストは関係する要素の塊になります。
(define queue (list (list 'a)))
4.queueからチェック対象のリストを取り出して変数(path)をセットします。(FLW②)
(define path (car queue))
5.さらに上で取り出したpathからチェック対象ノードを取り出します。(FLW②)
(define node (car path))
6.キューから取り出した値とノードの値を比較します。(FLW⑤)
false(#f)が返された場合(一致しない)、次ステップに進みます。
true(#t)が返された場合(一致する)、最終ステップに進みます。
(if (eq? node end) #t #f)
7.チェックしたノード(nodeの値)に連結しているノードリストをネットワーク(net)から取り出します。(FLW⑦)
(define assoc_nodes (cdr (assoc node net)))
8.上のステップで取り出したリストの各ノード(assoc_nodes →→ n)を確認済の経路パス(path)に結合します。(FLW⑧)
(define path-w (map (lambda (n) (cons n path)) assoc_nodes) )
9.queueの2列目以後のパスを取り出して、その値に上のステップで取り出したパス(path-w)を連結してqueueを更新します。(FLW⑧)
(次の比較対象になるパスを入れ換えるということです)
(define queue (append (cdr queue) path-w) )
10.ステップ7の結果がtrue(#t)になるまで4～9のステップを繰り返します。
繰り返しステップでは各変数の値は次のように展開されます。
| 繰返し順 | ステップ3:queue初期化 | ステップ4:path (car queue) | ステップ5:node (car path) | ステップ7:assoc_nodes (cdr (assoc node net)) | ステップ9:queue更新 |
|---|---|---|---|---|---|
| 0 | ((a)) | (a) | a | (b c) | ((b a)(c a)) |
| 1 | - | (b a) | b | (c) | ((c a)(c b a)) |
| 2 | - | (c a) | c | (d) | ((c b a)(d c a)) |
| 3 | - | (c b a) | c | (d) | ((d c a)(d c b a)) |
| 4 | - | (d c a) | d | - | - |
11.最後に取り出したpathが探索結果になるので経路を反転表示されます。
(reverse path)
まとめ
探索対象のネットワークからノードを取り出した結果をキューに蓄え続けて
最終的に目的地に到達するqueueが下のようなイメージで展開していることを体験できれば成功です。
- netから各queueに向かっている矢印はステップ7でnetから関連ノードを取り出す処理部分に該当します。
- 上側queueから下側queueに向かっている矢印はステップ8,9でqueueを更新する処理結果に該当します。
おわり＼(^o^)／