3

どうやら私の先生は、何かを学ぶ時間がなくても（十分な例も）先に進むべきだと信じているので、今度はフロイド-ワーシャルとワーシャルのアルゴリズムをclispで作成する方法を知る必要があります。

私がプロローグで行ったように、私の問題はグラフから隣接行列を生成することです。この場合、それはリストのリストになります。例：

((A B) (A C) (A D) (B C) (C D))

それは生成するはずです：

((0 1 1 1) (1 0 1 9) (1 1 0 1) (1 9 1 0))

私はこれを持っています：

(defun floyd(graph)
    (setf l (length graph)) 
    (setf mat (matrix l graph))
)

(defun matrix(l graph)
    (setf matrix (make-array (list l l)))
    (dotimes (i l)
        (dotimes (j l)
            (if (= i j)
                (setf (aref matrix i j) 0)
                (setf (aref matrix i j) ???)
            )
        )
    )
    matrix
)

どんな助けでも大歓迎です。

また、ちょっとオフトピックです。自分の質問を解決できた場合、質問に答えるために自分自身に返信する必要がありますか？

4

1 に答える 1

1

ウィキペディアの擬似コードを型宣言付きのCommonLispに変換しました。戻り型の宣言は非標準です。SBCLを使用しました。これは実行されないと思いますが、Lispコードがどのように見えるかがわかるかもしれません。

(defparameter *n* 5)
(defparameter *path*
  (make-array (list *n* *n*)
          :element-type '(unsigned-byte 64)))


(defun floyd-warshall (path)
  (declare (type (simple-array (unsigned-byte 64) 2) path)
       (values (simple-array (unsigned-byte 64) 2) &optional))
  (destructuring-bind (y x) (array-dimensions path)
    (unless (= y x)
      (break "I expect a square matrix, not ~ax~a." x y))
    (macrolet ((p (j i)
         `(aref path ,j ,i)))
      (dotimes (k x)
    (dotimes (i x)
      (dotimes (j x)
        (setf (p j i)
          (min (p j i) (+ (p k i)
                  (p j k)))))))))
  path)

注1：3Dボリューム画像がある場合は、次のようなインデックス（aref vol kji）が必要です。ここで、kはz、jy、およびiをx方向にインデックス付けします。このようにSBCLおよびおそらく他のすべての実装では、スライスはメモリ内で連続しています。

注2：マクロレットを使用すると、かなり多くの入力を節約できます。この美しいライブラリのwith-arraysの実装も見てください：git：//github.com/nikodemus/raylisp.git/objects/box.lisp

于 2011-07-01T14:42:09.803 に答える