3

显然我的老师认为，即使我们没有时间学习东西（也没有足够的例子），我们也应该继续前进，所以我现在需要知道如何在 clisp 中制作 Floyd-Warshall 和 Warshall 的算法。

正如我对 prolog 所做的那样，我的问题是从图中生成邻接矩阵，在这种情况下，它将是一个列表列表，例如：

((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

I converted the Wikipedia pseudo-code into Common Lisp with type declarations. The return type declaration is non-standard, I used SBCL. I guess this won't run but it might give you an idea how Lisp code is supposed to look like.

(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)

Note 1: If you have a 3D volume image you should have your indices like this (aref vol k j i) where k indexes z, j y and i the x-direction. That way in SBCL and presumably all other implementations the slices are consecutive in memory.

Note 2: macrolet can save quite a lot of typing. Also look at the implementation of with-arrays in this beautiful library: git://github.com/nikodemus/raylisp.git/objects/box.lisp

于 2011-07-01T14:42:09.803 回答