読者です 読者をやめる 読者になる 読者になる

(ブログ名 '未定)

プログラミングとかのメモ帳

Lispで深さ優先探索

Lisp

Common Lisp深さ優先探索をしました
正しく説明できている自信がないので、間違えなどはご指摘いただけるとありがたいです
あまり参考にしないほうがいいと思います(汗
とりあえずコードから

(defparameter *graph*
  '((a b c d)
    (b c)
    (c d)
    (d a)))
    
(defun depth-search (passed-point goal graph)
  (let* ((now-point (car passed-point))
         (next-points (cdr (find-if #'(lambda (point)
                                        (equal now-point (car point)))
                                    graph)))
         (new-graph (remove-if (lambda (x)
                                 (equal now-point (car x)))
                               graph)))
    (cond ((eq now-point goal) (list (reverse passed-point)))
          (t (mapcan #'(lambda (point)
                         (depth-search
                          (cons point passed-point)
                          goal
                          new-graph))
                     next-points)))))

実行は

CL-USER> (depth-search (list 'a) 'd *graph*)
((A B C D) (A C D) (A D))

課題内容

ある点からある点までの考えうる全ての経路を表示せよ
以下のような形式のデータが与えられる

[(a b c d)
 (b a c e)
 (c a b f) ...]
X Y

それぞれの()内の構造は、
(点N 点Nから行ける点1 点Nから行ける点2 ...)
のようになっていて、この配列をグラフと言う。
このとき、点Xから点Yに到達できる経路すべてを表示せよ。
ただし、同じ点は2回以上通ってはいけないものとする

課題の例

たとえば、このデータが与えられたとする

[(a b c d) (b c) (c d) (d a)]
a d

グラフイメージするとこんな感じだ
f:id:ikemaki:20160208234346g:plain
この問題は、上のようなグラフの点aから点dまでの経路を考えるというものだ。
この時、考えられる経路は、はじめにa->bを通った場合、a->cを通った場合、a->dを通った場合の3つになるだろう。そうすると
a -> b -> c -> d 
a -> c -> d
a -> d
になる。このように、経路を探索するのが今回の課題だ

今回の考え

  1. 関数searchには、経過した点、ゴール、グラフの3つの情報が与えられる
  2. 経過した点の配列から、最後に通った点(点N)を抜き出す
    1. グラフから、点Nから行ける点の配列(配列G)を抜き出す
    2. グラフから、点Nを除いたグラフ(新グラフ)を作る
  3. これを元に、以下の動作をする
    • 点Nがゴールと同じなら、配列Pを返す
    • 配列Gが空なら、空配列を返す (明記されていない)
    • 配列Gのそれぞぞれの要素(点G)に同じことをし、空配列を取り除く
      1. 関数searchに、点Gと経過した点を合わせた配列、ゴール、新グラフを与える

というのが、上のコードを日本語に概訳したものだ。

改良すべき点

  • (equal now-point (car x)) が2つあって気持ち悪い。
  • 再帰呼出しごとに、グラフのコピーが発生していて、メモリを圧迫しかねない。そもそもnew-graphの存在自体が疑問
  • 同じことを同じ引数で処理している。メモ化すべき
  • わかりにくい。高速化の前に、更に行う処理をシンプルにしたい

とりあえず思いついたことです
このプログラムは巨大なグラフが与えられると、一発で死ぬと思われるので、全く実用的ではありません。
私の力不足を感じた次第であります

参考文献

Common Lispによるグラフの探索が細かく書かれています。この方は他にも多くの記事を書かれていて、プログラミングに関する様々なノウハウが詰まっています