LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину

Vesper — Tue, 04 Nov 2014 11:19:53 +0000

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

LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину

amk — Sun, 19 Oct 2014 12:52:07 +0000

amk:

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

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

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

LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину

Екатерина_93 — Thu, 16 Oct 2014 10:28:02 +0000

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

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

Условие - Дан кувшин с водой емкостью N литров и пустой кувшин емкостью M литров. Требуется получить заданную емкость L литров (L
Немного теории : При поиске в глубину всегда раскрывается самая глубокая вершина в текущем фронте поиска. Процедура поиска в глубину отличается от процедуры поиска в ширину тем, что дочерние вершины, получаемые при раскрытии вершины x , помещаются в начало списка OPEN ,то есть принцип формирования списка open соответствует стеку, когда в алгоритме поиска в ширину принцип формирования списка OPEN соответствует очереди. :help:
[ 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 ]

Форум на Исходниках.RU

LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину

LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину

LISP по алгоритму поиска решений в глубину переделать по алгоритму в ширину