Блог

Главная - Вопросы по программированию - Lisp — изменить A * для проверки наилучшей стоимости, получить список целевых узлов

Lisp — изменить A * для проверки наилучшей стоимости, получить список целевых узлов

#search #lisp #common-lisp #clisp #hill-climbing

#Поиск #lisp #common-шепелявый #clisp #восхождение на холм #common-lisp

Вопрос:

Я пытаюсь изменить существующую функцию подъема на холм, которая принимает два имени узлов (например, A и E) и имеет необязательный параметр, который используется рекурсивно (очередь). Я пытаюсь определить функцию «дешевле», которая оценивает, является ли один путь дешевле другого. Кроме того, вместо одного целевого узла я пытаюсь передать список целевых узлов, которые функция, достигнув одного из этих узлов, перестает оценивать.

Проблема в том, что моя функция не вернет ничего, кроме начального узла, который я ввел, и пустого списка.

Вот моя сеть / график и связанные с ними затраты:

 (setf (get 's 'coordinates) '(0 3)
      (get 'a 'coordinates) '(4 6)
      (get 'b 'coordinates) '(7 6)
      (get 'c 'coordinates) '(11 9)
      (get 'd 'coordinates) '(2 0)
      (get 'e 'coordinates) '(9 2)
      (get 'f 'coordinates) '(11 3))


(setf (get 's 'cost) 0
      (get 'a 'cost) 16
      (get 'b 'cost) 4
      (get 'c 'cost) 10
      (get 'd 'cost) 5
      (get 'e 'cost) 12
      (get 'f 'cost) 14)

А вот моя модифицированная функция подъема на холм:

 (defun hill-climb (start finish amp;optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'(lambda (p1 p2)
                                                      (cheaper p1 p2 
                                                               finish)))
                                            (rest queue))))))

Наконец, вот функции «стоимость» и «дешевле»:

 (defun cost (path)
  (apply '  (mapcar #'(lambda (x) (get x 'cost)) path)))


(defun cheaper (p1 p2)
  (< (cost p1)
     (cost p2)))

РЕДАКТИРОВАТЬ: Извините, и вот «расширить»:

 (defun extend (path)
  (print (reverse path))
  (mapcar #'(lambda (new-node) (cons new-node path))
          (remove-if #'(lambda (neighbor) (member neighbor path))
                     (get (first path) 'neighbors))))

Комментарии:

1. Где extend ? Обратите внимание, что вы передаете неправильное количество аргументов cheaper . Кроме того, использование односвязных списков в качестве очередей, вероятно, не лучшая идея.

2. Извините, добавлено расширение. Заметил, что раньше дешевле было использовать функцию, которая принимала 3 аргумента. Настройка очереди как бы диктуется назначением. Итак, я знаю, что проблема в том, что, поскольку я использую список возможных целевых узлов вместо одного, когда я вызываю функцию рекурсивно, я не уверен, как это будет работать с точки зрения того, что я передаю ей из списка «готово». Возможно, если я просто изменю «дешевле», это сработает лучше…

3. Теперь, откуда берется neighbors свойство? Вы планировали добавить это свойство на отдельном шаге? Я не знаю ваших спецификаций, но я бы исключил, что сосед должен быть /-1 для каждой координаты (?). Кроме того, поскольку это домашнее задание, пожалуйста, пометьте его как таковое.

Ответ №1:

Я не совсем уверен, в чем проблема. В вашем expand neighbor используется свойство, которое не указано в вашем вопросе. Если это свойство определено для каждого узла, ваш код работает.

Предполагая, что каждый узел находится рядом с другим без другого между ними (что является единственным вариантом, который, по-видимому, имеет смысл для ваших данных, поскольку альтернатива, а именно создание только касательных узлов (т. Е. Узлов, Которые являются /-1 для одной или обеих координат) соседями, вообще не даст соседей вваш пример):

 (setf (get 's 'neighbors) '(a d)
      (get 'a 'neighbors) '(s b d)
      (get 'b 'neighbors) '(a c e)
      (get 'c 'neighbors) '(b)
      (get 'd 'neighbors) '(s a e)
      (get 'e 'neighbors) '(b d f)
      (get 'f 'neighbors) '(e))

(defun hill-climb (start finish amp;optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'cheaper)
                                            (rest queue))))))

(Недостающие части остаются такими же, как в вашем сообщении. Только незначительные корректировки, такие как удаление lambda around и дополнительный аргумент для, cheaper .)

Даст правильные результаты:

 CL-USER> (hill-climb 's '(b))

(S) 
(S D) 
(S D E) 
(S D E B)
CL-USER> (hill-climb 's '(b d))

(S) 
(S D)

Если вы не можете ввести новое свойство, вам придется проверять наличие соседей в вашей expand функции (что также будет означать, что вам придется передавать список узлов).