探索アルゴリズムの実装(グラフ定義)

graph.scm

; graph
; 「人工知能システムの構成」をogura
; 「人工知能の基礎知識」をtahara

;グラフのコストを入力するための手続き
; 単方向のコスト
(define (gcost  from to cost)
  (list (cons (cons from to) cost) ) )

; 双方向のコスト
(define (gcost2 from to cost)
  (append 
    (gcost from to cost) 
    (gcost to from cost) ) )

; ヒューリスティック関数をつくる
(define (make-heuristic-fn h-table)
  (lambda (a)
    (let ( ( h (assoc a h-table) ) )
      (if h (cdr h) #f) ) ) )

; 「人工知能システムの構成」図2.7 p.26
(define ogura-graph27 
  '( 
     ( #\S #\B #\D #\A )  
     ( #\A #\C )
     ( #\B #\E #\F )
     ( #\D #\H #\C )
     ( #\E #\D #\F )
     ( #\H #\G )
     )
  )

; 「人工知能の基礎知識」図3.5 p.48
(define tahara-graph35
  '( (#\S #\A #\B)
     (#\A #\B #\F)
     (#\B #\C #\F #\H)
     (#\C #\D #\I #\H)
     (#\D #\I)
     (#\E #\A)
     (#\F #\E #\H)
     (#\H #\I #\G)
     (#\I #\G)
    ))

; 「人工知能の基礎知識」図3.19 p.63
; ヒューリスティック関数の定義
(define tahara-h319
  (make-heuristic-fn
    '((#\G . 0) ; <---- ゴールは最小評価に
      (#\A . 7)
      (#\B . 4)
      (#\C . 6)
      (#\D . 4)
      (#\E . 2)
      (#\F . 3)
      (#\H . 4)
      (#\I . 2)
      ) ) )

; 「人工知能の基礎知識」図3.27 p.70
; ヒューリスティック関数の定義(A*アルゴリズム)
(define tahara-h327
  (make-heuristic-fn
    '((#\G . 0) ; <---- ゴールは最小評価に
      (#\A . 8)
      (#\B . 7)
      (#\C . 7)
      (#\D . 6)
      (#\E . 9)
      (#\F . 7)
      (#\H . 5)
      (#\I . 4)
      ) ) )

; 「人工知能の基礎知識」図3.11 p.54
; 有向グラフの枝のコスト
(define tahara-cost311
  (append
    (gcost #\A #\B 1)
    (gcost #\A #\F 6)
    (gcost #\B #\C 6)
    (gcost #\B #\F 6)
    (gcost #\B #\H 3)
    (gcost #\C #\D 5)
    (gcost #\C #\H 2)
    (gcost #\C #\I 4)
    (gcost #\D #\I 2)
    (gcost #\E #\A 1)
    (gcost #\F #\E 7)
    (gcost #\F #\H 2)
    (gcost #\H #\G 7)
    (gcost #\H #\I 1)
    (gcost #\I #\G 5)
    (gcost #\S #\A 1)
    (gcost #\S #\B 3)
    ))



; 「人工知能システムの構成」図3.1迷路の探索,p.32
(define ogura-grid31
  '(
    (#\S . (0 . 0) ) 
    (#\A . (0 . 1) )
    (#\B . (0 . 2) )
    (#\D . (0 . 3) )
    (#\E . (1 . 0) )
    (#\F . (1 . 1) )
    (#\H . (1 . 2) )
    (#\I . (1 . 3) )
    (#\J . (2 . 0) )
    (#\K . (2 . 1) )
    (#\L . (2 . 2) )
    (#\G . (2 . 3) )
    (#\M . (3 . 0) )
    (#\N . (3 . 1) )
    (#\P . (3 . 2) )
    (#\Q . (3 . 3) )
    ))


(define (ogura-h31 pt-id) 
  (define goal-pt (cdr (assoc #\G ogura-grid-31)))
  (let ((p (assoc pt-id ogura-grid31) ))
    (if p
      (let ((pt (cdr p)))
        (+ (abs (- (car pt) (car goal-pt) ))
           (abs (- (cdr pt) (cdr goal-pt)))))
      0) ) )

; 「人工知能システムの構成」図3.1(a)迷路の探索,p.32
(define ogura-graph31a
  '( (#\S #\A #\E)
     (#\A #\S #\F #\B)
     (#\B #\A #\D)
     (#\D #\B #\I)
     (#\E #\S #\F #\K #\J)
     (#\F #\A #\E #\H)
     (#\H #\F)
     (#\I #\D)
     (#\J #\E #\M)
     (#\K #\E #\N #\L)
     (#\L #\K)
     (#\M #\J)
     (#\N #\K #\P)
     (#\P #\N #\Q #\G)
     (#\Q #\P) ))

; 「人工知能システムの構成」図3.1(b)迷路の探索,p.32
(define ogura-graph31b
  '( (#\S #\A #\E)
     (#\A #\S #\F #\B)
     (#\B #\A #\D)
     (#\D #\B #\I)
     (#\E #\S #\K #\J)
     (#\F #\A #\H)
     (#\H #\F #\K)
     (#\I #\D)
     (#\J #\E #\M)
     (#\K #\E #\H #\M #\N #\L)
     (#\L #\K)
     (#\M #\J #\K #\N)
     (#\N #\K #\P #\M)
     (#\P #\N #\Q #\G)
     (#\Q #\P) ))

; 「人工知能システムの構成」図3.3(a)迷路二題 , p.36
(define ogura-graph33a
  '( (#\S #\A #\E)
     (#\A #\S #\F #\B)
     (#\B #\A #\D) 
     (#\D #\B #\I)
     (#\E #\S #\F #\K #\J)
     (#\F #\A #\H #\L #\E)
     (#\H #\F #\G)
     (#\I #\D)
     (#\J #\E)
     (#\K #\E #\L)
     (#\L #\F #\K #\G)
     ))

; コスト
(define ogura-cost33a
  (append
    (gcost2 #\A #\B 3)
    (gcost2 #\A #\F 2)
    (gcost2 #\A #\S 1)
    (gcost2 #\B #\D 4)
    (gcost2 #\D #\I 2)
    (gcost2 #\E #\F 1)
    (gcost2 #\E #\J 5)
    (gcost2 #\E #\K 1)
    (gcost2 #\E #\S 5)
    (gcost2 #\F #\H 1)
    (gcost2 #\F #\L 4)
    (gcost2 #\H #\G 4)
    (gcost2 #\K #\L 1)
    (gcost2 #\L #\G 1)
    ))

; 「人工知能システムの構成」図3.3(b)迷路二題 , p.36
(define ogura-graph33b
  '( (#\S #\A #\E #\F)
     (#\A #\S #\B)
     (#\B #\A #\F #\H #\I #\D) 
     (#\D #\B #\I)
     (#\E #\S #\J)
     (#\F #\S #\B #\K #\J) 
     (#\H #\B #\K #\L)
     (#\I #\B #\D #\L #\G)
     (#\J #\E #\F #\K)
     (#\K #\J #\F #\H #\L)
     (#\L #\I #\K #\H #\G)
     ))

(define ogura-cost33b
  (append
    (gcost2 #\A #\B 6)
    (gcost2 #\A #\S 2)
    (gcost2 #\B #\D 1)
    (gcost2 #\B #\F 3)
    (gcost2 #\B #\H 1)
    (gcost2 #\B #\I 3)
    (gcost2 #\D #\I 1)
    (gcost2 #\E #\J 2)
    (gcost2 #\E #\S 1)
    (gcost2 #\F #\J 2)
    (gcost2 #\F #\K 2)
    (gcost2 #\F #\S 4)
    (gcost2 #\H #\K 2)
    (gcost2 #\H #\L 2)
    (gcost2 #\I #\G 1)
    (gcost2 #\I #\L 2)
    (gcost2 #\J #\K 4)
    (gcost2 #\K #\L 4)
    (gcost2 #\L #\G 2)
    ))

; 「人工知能システムの構成」図3.5(a) p.40
(define ogura-graph35a
  '(
    (#\S #\A #\B) ;<---- 図では双方向だが、スタートは一方通行とした
    (#\A #\C #\D)
    (#\B #\E #\D)
    (#\C #\A #\F #\G)
    (#\D #\A #\G #\H #\B)
    (#\E #\B #\H #\I)
    (#\F #\C #\G)
    (#\H #\D #\G #\I #\E)
    (#\I #\E #\H)
    ))

(define ogura-h35a
  (make-heuristic-fn
    '((#\G . 0) ; <---- ゴールは最小評価に
      (#\A . 3)
      (#\B . 3)
      (#\C . 3)
      (#\D . 2)
      (#\E . 5)
      (#\F . 2)
      (#\H . 2)
      (#\I . 3)
      ) ) )

(define ogura-cost35a
  (append
    (gcost2 #\A #\S 2)
    (gcost2 #\A #\D 3)
    (gcost2 #\A #\C 3)
    (gcost2 #\B #\S 3)
    (gcost2 #\B #\D 1)
    (gcost2 #\B #\E 2)
    (gcost2 #\C #\F 4)
    (gcost2 #\C #\G 3)
    (gcost2 #\D #\G 2)
    (gcost2 #\D #\H 3)
    (gcost2 #\E #\H 4)
    (gcost2 #\E #\I 4)
    (gcost2 #\F #\G 2)
    (gcost2 #\H #\G 2)
    (gcost2 #\H #\I 2)
    ))

; 「人工知能システムの構成」図3.5(b) p.40
(define ogura-graph35b
  '(
    (#\S #\A #\B) ;<---- 図では双方向だが、スタートは一方通行とした
    (#\A #\G #\C)
    (#\B #\G #\D)
    (#\C #\A #\G)
    (#\D #\B #\G)
    ))

(define ogura-h35b
  (make-heuristic-fn
    '((#\G . 0) ; <---- ゴールは最小評価に
      (#\A . 3)
      (#\B . 4)
      (#\C . 2)
      (#\D . 3)
      ) ) )

(define ogura-cost35b
  (append
    (gcost2 #\A #\S 2)
    (gcost2 #\A #\C 3)
    (gcost2 #\A #\G 4)
    (gcost2 #\B #\S 3)
    (gcost2 #\B #\G 2)
    (gcost2 #\B #\D 1)
    (gcost2 #\C #\G 3)
    (gcost2 #\D #\G 3)
    ))

; 「人工知能システムの構成」図3.6 p.41
(define ogura-graph36
  '(
    (#\S #\A #\B #\C) ;<---- 図では双方向だが、スタートは一方通行とした
    (#\A #\B #\D)
    (#\B #\A #\D #\G #\C)
    (#\C #\B #\G)
    (#\D #\A #\B)
    ))

(define ogura-h36
  (make-heuristic-fn
    '((#\G . 0) ; <---- ゴールは最小評価に
      (#\A . 12)
      (#\B . 2)
      (#\C . 7)
      (#\D . 8)
      ) ) )

(define ogura-cost36
  (append
    (gcost2 #\A #\S 1)
    (gcost2 #\A #\B 2)
    (gcost2 #\A #\D 1)
    (gcost2 #\B #\S 8)
    (gcost2 #\B #\D 3)
    (gcost2 #\B #\G 6)
    (gcost2 #\B #\C 2)
    (gcost2 #\C #\S 4)
    (gcost2 #\C #\G 9)
    ))