LISP - поиск в ширину - PullRequest
       22

LISP - поиск в ширину

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

У меня есть реализация BFS, которую я получил в другом месте и немного изменил, но у меня проблемы с ее вводом.
Он принимает график и принимает его как '((a b c) (b c) (c d)) Но мой вклад, который я даю, - это взвешенный график ... Я знаю, что он бесполезен для BFS, но позже я использую весовые коэффициенты. Этот вход выглядит как
'(<br> (a (b 3) (c 1))<br> (b (a 3) (d 1))<br> (c (a 1) (d2) (e 2))<br> )
И так далее.

Мой код:

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

(defun BFS (end queue net)  
  (if (null queue)  
      nil  
      (expand-queue end (car queue) (cdr queue) net)))

(defun expand-queue (end path queue net)  
  (let ((node (car path)))  
        (if (eql node end)  
        (reverse path)  
        (BFS end
             (append queue  
                     (new-paths path node net))  
             net))))

(defun new-paths (path node net)  
  (mapcar #'(lambda (n)  
              (cons n path))  
          (cdr (assoc node net))))

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

1 Ответ

1 голос
/ 11 апреля 2011

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

Когда у графа есть синтаксис, такой как:

graph = (node*)

node = (name nextnodename*)

name = SYMBOL

nextnodename = SYMBOL

Тогда функция преобразования может быть:

(defun convert-graph (graph)
  (mapcar (lambda (node)
            (destructuring-bind (name . nodes) node
              (cons name (mapcar #'first nodes))))
          graph))

вам могут понадобиться другие функции извлечения:

(defun convert-graph (graph &key (key #'first))
  (mapcar (lambda (node)
            (destructuring-bind (name . nodes) node
              (cons name (mapcar key nodes))))
          graph))

Пример:

(convert-graph '((a (b 3) (c 1))
                 (b (a 3) (d 1))
                 (c (a 1) (d 2) (e 2)))
               :key #'first)

((A B C) (B A D) (C A D E))

Теперь вам может потребоваться удалить дубликаты ссылок.Но это зависит от синтаксиса и семантики описания вашего графа.

...