Lisp - измените A *, чтобы проверить лучшие цены, получите список узлов цели - PullRequest
Новая
       44

Lisp - измените A *, чтобы проверить лучшие цены, получите список узлов цели

3 голосов
/ 11 октября 2011

Я пытаюсь изменить существующую функцию набора высоты, которая принимает два имени узла (например, 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 &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 Ответ

2 голосов
/ 12 октября 2011

Я не совсем уверен, в чем здесь проблема.В вашем 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 &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 вокруг и дополнительный аргумент в 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 (что также будет означать, что вам придется пропустить список узлов).

...