LISPによる横型探索

質問

LISPのSchemeをつかって横型探索で探索した経路を出力するプログラムをつくっているのですが、
今は探索が終わると終了するとCLOSEDの中を表示するプログラムしかできていません
もしこれに探索した経路の出力をする機能を加える場合どうすればいいですか？

OPEN→待ちリスト
CLOSED→展開済みリスト
GOAL→目標地点
OP→オペレータの集まり

nとopから展開の結果をだす
(define (tenkai n op)
(tenkai2 n op '()))

(define (tenkai2 n op kekka)
(if (null? op)
kekka
(if (= n (car (car op)))
(tenkai2 n (cdr op) (cons (car (cdr (car op))) kekka))
(tenkai2 n (cdr op) kekka))))

(define (yokogata open goal op closed)
(if (null? open)
'sippai
(if (= (car open) goal)
(display closed)
(yokogata
(append (cdr open) (tenkai (car open) op))
goal
op
(append closed (list (car open)))))))

回答No.1

cametan_42 · ベストアンサー

う～～ん……。
こう言うのって検索対象の「データ構造」が分かんないと何とも言えないですよね。
結局二分木探索でしょ?その二分木探索対象のリストが「どう言う構造なのか?」で全然違うんですよ。表現方法が色々ある。だから特定出来ませんね。
また、opと言われても「一体何をさせたいのか?」不明です。演算子の集合、っつってもどう言う集合なんだか皆目不明ですし。

一般的な幅優先探索の簡単なコードは、ポール・グレアムの「ANSI Common Lisp」によれば次のような感じです。Scheme用に書き換えてあります。

(define (shortest-path start end net)
　(breadth-first-search end (list (list start)) net))

(define (breadth-first-search end queue net)
　(or (null? queue)
　　　　(let ((path (car queue)))
　　　　　(let ((node (car path)))
　　　　　　(if (eqv? node end)
　　　　　　　　(reverse path)
　　　　　　　　(breadth-first-search end
　　　　　　　　　　　　　　　　　　　(append (cdr queue)
　　　　　　　　　　　　　　　　　　　　　　　(new-paths path node net))
　　　　　　　　　　　　　　　　　　　net))))))

(define (new-paths path node net)
　(map
　　(lambda (n)
　　　(cons n path))
　　(cdr (assoc node net))))

netに探索したい二分木リスト、startに探索始点、endに探索終点を与えると経路のリストを返します。
例えば、家系図リスト、familyを次のように設定します。

(define family '((Harry Jane Bill) (Jane Joe Diane) (Joe '() '()) (Dian '() ())
　　　　　　　　　(Bill Julia Mike) (Julia Frank Susan) (Frank Anne '()) (Susan '() '())
　　　　　　　　　(Mike '() '())))

このリストの各要素は(ノード 子供左 子供右)となっていて、左の枝から順に整列しています。
この二分木リストをnetに与え、例えばBillからFrankへの系図を辿るには、

> (shortest-path 'Bill 'Frank family)
(Bill Julia Frank)

となりますね。つまり、Billの子供の一人がJuliaで、Juliaの子供がFrankです。つまり、FrankはBillの孫ですよね。
こう言う感じで経路を記録していくんですが、参考になったでしょうか?

お礼

お礼が大変遅くなってすいません。
かなり参考になり、無事完成しました。
本当にありがとうございます