Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования, науки, молодёжи и спорта Украины
ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ
Кафедра «Информационные технологии»
Отчёт о выполнении лабораторной работы №3
«Методы поиска решений в пространствах состояний»
Выполнил:
Студент КСФ 4 к. 4 гр.
Мельников В.Е.
Проверил:
Бодарев Д. А.
Одесса-2013
Выполнение работы
(defun tree-search
(states is-goal expand-state combine-states)
(cond ((null states) nil)
((funcall is-goal (first states))
(first states))
(t (tree-search
(funcall combine-states (rest states)
(funcall expand-state (first states)))
is-goal
expand-state
combine-states ))))
(defun depth-first-search
(state is-goal expand-state tree-searcher)
(funcall tree-searcher
(list state) is-goal expand-state
#'(lambda (old-states new-states)
(append new-states old-states))))
(defun maze-is-goal (maze-state)
(let ((maze (second maze-state)))
(and
(= (maze-start-row maze) (maze-goal-row maze))
(= (maze-start-column maze)
(maze-goal-column maze)))))
Контрольные вопросы
1.Когда лучше использовать поиск в ширину, а когда в глубину. (Под лучше понимается находить решения быстрее).
Под названием «поиск в глубину» понимается порядок рассмотрения альтернатив в пространст¬ве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую «глубокую» из них. Самая глубокая вершина – это вершина, расположенная дальше других от стартовой вершины.
В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину.
2.Какие параметры (search-strategy и tree-searcher) Вы передадите функции maze-solve?
Функция maze-solve решает заданный лабиринт, печатает решение. Если решения не существует, печатает соответствующее сообщение.
Функция tree-searcher используется для выполнения алгоритма поиска по дереву.
states – список состояний;
is-goal – предикат is-goal получает в качестве аргумента состояние. Если состояние целевое, is-goal возвращает не NIL. В противном случае, возвращает NIL.
expand-state – получает в качестве аргумента какое-то состояние. Возвращает список всех состояний, которые могут быть достигнуты из заданного состояния, за одно перемещение. (Список может быть пустым, если нет состояний, достижимых из заданного).
combine-states – функция combine-states получает два аргумента. Первый аргумент – список уже существующих состояний. Второй аргумент – список сгенерированных функцией expand-state состояний. Функция возвращает список состояний просто объединяя все состояния в обоих списках. Порядок, в котором состояния представлены в списке, это порядок, в котором состояния были получены.