Schemeで非決定性探索 深さ優先探索と幅優先探索
9月 29th, 2008 at 10:08pm |
MacBook Air買いました！(挨拶
で、LLFutureんとき買ったOn Lispをがんばってしこしこ読んだらマクロのありがたさが少しわかったような
↓
でもSchemeってtraditional macroないんだよね... aifもかけやしねぇ
↓
syntax-caseで外の環境の変数とか補足できるよ！aifかけるよ！これは勝つる！！
↓
...あれ、使い方全然わかんない...←今ここ
それはそれとして、On Lispに乗ってる幅優先探索ってなんか思った通りの動作をしてくれない気がするんだけど...
見つかる解は浅いところのがちゃんと見つかるっぽいんだけど検索順路が深さ優先探索と同じ順序で探索していくのがなんかこー微妙な気持ち
どうすればいいんだ！！
深さ優先探索
SCHEME:
-
;;depth first search
-
(define depth-fail #f)
-
(define (depth-choose . args)
-
(if (null? args)
-
(depth-fail)
-
(let ((fail0 depth-fail))
-
(call/cc
-
(lambda (cc)
-
(set! depth-fail
-
(lambda ()
-
(set! depth-fail fail0)
-
(cc (apply depth-choose (cdr args)))))
-
(cc (car args)))))))
-
-
(call/cc
-
(lambda (cc)
-
(set! depth-fail
-
(lambda ()
-
(cc 'fail)))))
幅優先探索
SCHEME:
-
;;width first search
-
(define width-fail #f)
-
(define *search-path* '())
-
(define (width-choose . args)
-
(call/cc
-
(lambda (cc)
-
(set! *search-path*
-
(append *search-path*
-
(map
-
(lambda (arg)
-
(lambda () (cc arg)))
-
args)))
-
(width-fail))))
-
-
(call/cc
-
(lambda (cc)
-
(set! width-fail
-
(lambda ()
-
(if (null? *search-path*)
-
(cc 'fail)
-
(let ((path (car *search-path*)))
-
(set! *search-path* (cdr *search-path*))
-
(path)))))))
で
SCHEME:
-
;;sample code
-
(define choose width-choose)
-
(define-syntax fail
-
(syntax-rules ()
-
((_) (width-fail))))
-
;(define choose depth-choose)
-
;(define-syntax fail
-
; (syntax-rules ()
-
; ((_) (depth-fail))))
-
-
(let* ((a (choose 1 2 3 4 5 6))
-
(b (choose 1 2 3 4 5 6))
-
(c (choose 1 2 3 4 5 6)))
-
(if (and (odd? a) (even? b) (odd? c))
-
(print a " " b " " c)
-
(fail))
-
(fail))
途中(define fail depth-fail)とかやっててあれー？動かないなーとかむーむーうなってたのは内緒(しかも結構長時間
Posted in Scheme