LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину , поиск решений в пространстве состояний (нужно сдать до 23.10.14) очень нужна помощь!!!

[Екатерина_93]

Здравствуйте! Помогите пожалуйста! Есть готовая правильная рабочая программа, реализующая задачу о двух кувшинах, написанная на Lisp по алгоритму поиска решений в пространстве состояний В ГЛУБИНУ. Нужно переделать чтобы работала по алгоритму поиска В ШИРИНУ !

Задача о двух кувшинах

Условие - Дан кувшин с водой емкостью N литров и пустой кувшин емкостью M литров. Требуется получить заданную емкость L литров (L<N и L<M). Воду можно либо выливать, либо переливать из одного кувшина в другой. (Кувшины можно полностью наполнять водой неограниченно). Значения N, M, L вводятся с клавиатуры, например, соответственно: 5, 2, 1

Немного теории : При поиске в глубину всегда раскрывается самая глубокая вершина в текущем фронте поиска. Процедура поиска в глубину отличается от процедуры поиска в ширину тем, что дочерние вершины, получаемые при раскрытии вершины x , помещаются в начало списка OPEN ,то есть принцип формирования списка open соответствует стеку, когда в алгоритме поиска в ширину принцип формирования списка OPEN соответствует очереди.
[ code ]
(defun lab5()
(princ "N M L: ")

(let* ((n (read *standard-input*))(m (read *standard-input*))(l (read *standard-input*)) (open (list (list n 0))) (close nil) (x))
(loop

(if (equal open nil ) (return "Nea") )
(setf x (first open))
(setf close (append close (list x)))
(if (equal (second x) l) (return "YES"))
(setf open (cdr open))
(cond

( (and (not (equal (first x) 0)) (not (equal (second x) 0)))
(if (> m (second x))
(setf open (append open (list (list (- (first x) (- m (second x))) m))))


(if (< (first x) (second x))
(setf open (list (list 0 (first x))))
(setf open (append open (list (list (first x) 0))))
)
)
)

( (and (equal (first x) 0) (equal (second x) 0))
(setf open (append open (list (list n 0)) ))
)

( (and (not (equal (first x) 0)) (equal (second x) 0))
(if (> (- (first x) m) 0)
(setf open (list (list (- (first x) m) m)))
(setf open (append open(list (list 0 (first x)))))
)
)

( (and (equal (first x) 0) (not (equal (second x) 0)))
(setf open (append open (list (list n (second x))) ))
)
)
(print x)

)
)
)
[ /code ]

[amk]

Цитата Екатерина_93 @ 16.10.14, 10:28

то есть принцип формирования списка open соответствует стеку, когда в алгоритме поиска в ширину принцип формирования списка OPEN соответствует очереди.

Ну собственно ты и сам всё знаешь. Собственно алгоритмы только тем и отличаются, что при поиске в глубину используется стек, а при поиске в ширину очередь. Правда поиск в глубину можно реализовать ещё и рекурсией.

[Vesper]

Переставь операнды у append, где она вызывается для изменения open, должно хватить.