Лисп - Восхождение на холм - PullRequest
Новая
       43

Лисп - Восхождение на холм

3 голосов
/ 29 апреля 2011

Хорошо, у меня есть реализация BFS на Лиспе, которую я пытаюсь преобразовать для поиска по альпинизму.

Вот как выглядит мой BFS-код: 

; The list of lists is the queue that we pass BFS.  the first entry and 
; every other entry in the queue is a list.  BFS uses each of these lists and 
; the path to search.  

(defun shortest-path (start end net)   
  (BFS end (list (list start)) net))

;We pass BFS the end node, a queue containing the starting node and the graph 
;being searched(net)   

(defun BFS (end queue net)
  (if (null queue) ;if the queue is empty BFS has not found a path so exit
      nil
      (expand-queue end (car queue) (cdr queue) net)))

(defun expand-queue (end path queue net)
  (let ((node (car path)))
    (if (eql node end)   ; If the current node is the goal node then flip the path
                         ; and return that as the answer
        (reverse path)
        ; otherwise preform a new BFS search by appending the rest of 
        ; the current queue to the result of the new-paths function
        (BFS end (append queue (new-paths path node net)) net))))

; mapcar is called once for each member of the list new-paths is passed
; the results of this are collected into a list
(defun new-paths (path node net)
  (mapcar #'(lambda (n) (cons n path))
         (cdr (assoc node net))))

Теперь я знаю, что вместо того, чтобы всегда расширять левый узел, как я это делаю в BFS, мне нужно развернуть узел, который кажется наиболее близким к целевому состоянию.
График, который я использую, выглядит следующим образом: 

(a (b 3) (c 1))  
(b (a 3) (d 1))

У меня есть функция преобразования, чтобы заставить это работать с вышеуказанной реализацией BFS, но теперь мне нужно превратить это в восхождение на холм, используя этот формат графика.

Я просто не уверен, с чего начать, и пытался безрезультатно. Я знаю, что в основном мне нужно изменить функцию expand-queue, чтобы развернуть ближайший узел, но я не могу создать функцию для определения ближайшего узла.

Спасибо за помощь!

1 Ответ

0 голосов
/ 30 апреля 2011

Неправильно добавлять вещи в конец списка. Это самая дорогостоящая операция со списком. Весь список копируется, а затем добавляется другой список. Вы используете его в рекурсивной процедуре, что означает, что это будет выполняться каждый раз, когда вы расширяете узел для создания новых путей.

Если вы помещаете предметы в очередь, вам нужно посмотреть, в каком порядке вы это делаете. Когда ширина широка, каждый посещает каждый узел на уровне, прежде чем перейти на следующий уровень. Скалолазание потребовало бы, чтобы вы отсортировали кандидатов на «лучших», используя весовую функцию. Таким образом, вам нужна какая-то функция, вычисляющая числовое значение из текущего узла и кандидата на следующий узел. Затем вам нужно отсортировать кандидатов и развернуть сначала «лучший» узел. Для очереди LIFO (последний пришел, первый вышел) это означает, что наиболее многообещающий узел должен быть перемещен последним, так что он будет развернут первым. Обратите внимание, что очереди LIFO хорошо подходят для односвязных списков. FIFO (первым пришел, первым вышел) не так.

Типичная идея информатики - абстракция данных. Если LIFO QUEUE является такой структурой данных, вам необходимо определить такие функции, как MAKE-LIFO-QUEUE, EMPTY-QUEUE-P, .... Эти функции вы бы затем использовали вместо LIST, NULL и других, и они делают целью структура данных понятнее. Это делает ваш код длиннее, но, поскольку списки Lisp являются общими и могут (ab-) использоваться для всех видов сценариев использования, рассмотрение одних только операций над списками не проясняет их намерения. Это особенно важно для более сложных графовых алгоритмов.

...