たまに書きます。

気になって調べたことを書いていきます。

そしてCommon Lispで書いてみた

一つ前のと全く同じアルゴリズム、データ構造で書いてみた。
引数に渡すネットワークも同じ。

ただ、これってネットワークが循環してるとだめだよね。だから、経路を見たら、子ノードがそれまで通ってきたところでないことをチェックさせないといけない。また今度w

;ネットワークの定義
(setf net (make-hash-table))
(setf (gethash 'a net) '(b c))
(setf (gethash 'b net) '(d))
(setf (gethash 'd net) '(e))
(setf (gethash 'c net) '(e))

(defun shortest_path (start goal network)
  (bfs (list (list start)) goal network) )

(defun bfs (queue goal network)
  (if (eql (caar queue) goal)
    (reverse (car queue))
    (bfs (append (cdr queue) (make-newpath (car queue) network))
	 goal
	 network )))

(defun make-newpath (cur_path network)
  (let ((next (gethash (car cur_path) network)))
    (mapcar #'(lambda (x) (cons x cur_path)) next) ))

(princ (shortest_path 'a 'e net))

結果も同じ。なんかでももっと綺麗に書けないかな。
あと、これってハッシュ表は使わないほうがいいのかな。連想リストの方が遅いけど、そっちのほうが構造に依存しないっていう点でいい気もする。

最近はLispよく書くけど、しばらく続くだろうね。慣れると面白い。
でも関数型プログラミングっていうものに頭が慣れていく感じがあまりしない。っていうかデータの通用範囲(っていえば良いの?)が口では分かっているつもりでも、意識がなかなか行かなくて困ってるw

追記。
一つ前の記事消えてる。もう一回同じことやってダメだったら報告かな。