матрица смежности/Floyd/Warshall в lisp

Очевидно, мой учитель считает, что даже если у нас нет времени на изучение материала (и недостаточно примеров), мы должны двигаться дальше, поэтому теперь мне нужно знать, как сделать алгоритмы Флойда-Уоршалла и Уоршалла в 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
)

Любая помощь приветствуется.

Кроме того, и немного не по теме: если бы я мог решить свой собственный вопрос, должен ли я ответить себе, чтобы получить ответ на вопрос?


graph matrix lisp floyd-warshall clisp
person Kirby    schedule 24.05.2011    source источник
comment
Существует значок самообучения, если вы ответите на свой вопрос с оценкой 3 или более. Я бы воспринял это как подсказку относительно того, приемлемо ли отвечать с решением самостоятельно.   -  person Terje Norderhaug    schedule 25.05.2011
comment
В качестве начала для более идиоматического кода используйте let вместо setf для l, mat и matrix.   -  person Terje Norderhaug    schedule 25.05.2011
comment
CLISP — это реализация, язык называется Common Lisp или сокращенно CL. Вам также необходимо объявить переменные (например, с помощью LET). Установка произвольных неопределенных переменных не является хорошей идеей. Также не форматируйте код с одиночными круглыми скобками в строке.   -  person Rainer Joswig    schedule 25.05.2011
comment
В качестве разминки рассмотрите возможность написания функции, которая возвращает узлы графа, например (A B C D).   -  person Terje Norderhaug    schedule 25.05.2011
comment
Ваш учитель будет гораздо больше впечатлен вашим мастерством, если вы решите его с помощью чистых функций, а не будете полагаться на о побочных эффектах. Посмотрите, сможете ли вы отказаться от использования SETF.   -  person Terje Norderhaug    schedule 25.05.2011
comment
@Terje Большое спасибо за все ваши комментарии, я попробую разминку, и если у меня будет время, я попытаюсь понять чистые функции xD Проблема в том, что у меня сейчас около 36 часов.   -  person Kirby    schedule 25.05.2011

Ответы (1)


arrow_upward
1
arrow_downward

Я преобразовал псевдокод Википедии в Common Lisp с объявлениями типов. Объявление возвращаемого типа нестандартное, я использовал 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: Если у вас есть трехмерное объемное изображение, ваши индексы должны быть такими (aref vol k j i), где k индексирует z, j y и i направление x. Таким образом, в SBCL и, предположительно, во всех других реализациях срезы располагаются в памяти последовательно.

Примечание 2: макролет может сэкономить довольно много времени. Также посмотрите на реализацию with-arrays в этой прекрасной библиотеке: git://github.com/nikodemus/raylisp.git/objects/box.lisp

person whoplisp    schedule 01.07.2011