Выполнение работы. В этой лабораторной работе мы подробно рассмотрим технику, известную как поиск в пространстве состояний
В этой лабораторной работе мы подробно рассмотрим технику, известную как поиск в пространстве состояний. Каждая конфигурация, в которой может пребывать система, называется состоянием. Из каждого состояния можно переместиться в некоторое множество других состояний. Одно состояние называется стартовым, другое – целевым. Задача состоит в том, чтобы найти последовательность перемещений, ведущих из стартового состояния в целевое. В лабораторной работе применение алгоритмов поиска в пространстве состояний мы рассмотрим на примере задачи поиска пути в лабиринте. Пусть, есть такой лабиринт: ##### #O#X# # # ##### Позиция, помеченная как 'O' – стартовая позиция; позиция, помеченная 'X' – целевая. Знаком '#' изображаются непрозрачные стены. Мы можем на каждом шаге перемещаться ВВЕРХ, ВЛЕВО, ВПРАВО или ВНИЗ. Одно из правильных решений этого лабиринта можно задать следующей серией перемещений: ВНИЗ ВПРАВО ВПРАВО ВВЕРХ Конечно, другим правильным решением может быть следующая серия перемещений: ВНИЗ ВВЕРХ ВНИЗ ВВЕРХ ВНИЗ ВПРАВО ВЛЕВО ВПРАВО ВПРАВО ВВЕРХ ВНИЗ ВВЕРХ Итак, каждое состояние описывается: - расположением стен; - стартовой позицией; - целевой позицией. После того как сделано перемещение, новое состояние подобно старому, но содержит другую стартовую позицию. Прежде чем писать «решатель лабиринтов», мы напишем универсальный инструмент поиска (который ничего не знает о лабиринтах), и применим его к задаче поиска пути в лабиринте. Один из алгоритмов поиска пространства состояний называется поиском преимущественно в глубину (depth-firth search). По этому алгоритму, когда из исходного состояния (s) получено новое (n), это новое состояние включается в поиск. Теперь мы пытаемся перевести систему из состояния n в состояние n1. Если состояние n1 ранее не было достигнуто, то производится его просмотр и поиск продолжается из n1. В противном случае выбирается другое достижимое из n состояние, и т. д. Например, предположим, что мы осуществляем поиск в следующем лабиринте: ###### ## # #O #X# ## # ###### Предположим, что когда мы ищем следующее состояние, мы пытаемся выполнять перемещения в следующем порядке: ВВЕРХ, ВПРАВО, ВНИЗ, ВЛЕВО. Поиск в глубину попытается перевести систему в новое состояние используя вначале перемещение ВВЕРХ. Это перемещение блокируется стеной. Следующим выбирается перемещение ВПРАВО. Получим такое состояние лабиринта: ###### ## # # O#X# ## # ###### Пытаемся переместиться ВВЕРХ. Получим следующее состояние: ###### ##O # # #X# ## # ###### После нескольких применений перемещения ВПРАВО перемещение ВНИЗ приводит к достижению цели. В противоположность этому поиску, поиск преимущественно в ширину (breadth-first search) сначала осуществляет поиск по всем узлам уровня k, а затем уже – по узлам уровня k+1. Поиск преимущественно в ширину для этого же лабиринта сначала применит перемещение ВПРАВО. Получим: ###### ## # # O#X# ## # ###### Затем применим перемещение ВВЕРХ. Получим: ###### ##O # # #X# ## # ###### Поскольку это не конечное состояние, возвращаемся назад и пытаемся применить перемещение ВНИЗ. Получим: ###### ## # # #X# ##O # ###### Поскольку это не конечное состояние, возвращаемся назад и пытаемся применить перемещение ВПРАВО. Получим: ###### ## O # # #X# ## # ###### И т. д. Другими словами поиск в ширину просматривает все состояния, которые находятся на расстоянии k перемещений от начального, прежде, чем просматривает какое-либо состояние, которое находится на расстоянии k+1. Функции поиска Для перехода в следующее состояние используется функция поиска. Алгоритм поиска в дереве состояний следующий: 1. Если нет доступных состояний, мы не можем найти решение. 2. В противном случае, если исходное состояние целевое, то вернуть это состояние. 3. В противном случае переходим из исходного состояния в новое. Затем формируем новое множество состояний (включаем новое состояние в список состояний). 4. Новое состояние становится исходным. 5. Перейти к пункту 1.
Функция поиска по дереву – tree-search получает четыре параметра: states – список состояний; is-goal – предикат is-goal получает в качестве аргумента состояние. Если состояние целевое, is-goal возвращает не NIL. В противном случае, возвращает NIL. expand-state – получает в качестве аргумента какое-то состояние. Возвращает список всех состояний, которые могут быть достигнуты из заданного состояния, за одно перемещение. (Список может быть пустым, если нет состояний, достижимых из заданного). combine-states – функция combine-states получает два аргумента. Первый аргумент – список уже существующих состояний. Второй аргумент – список сгенерированных функцией expand-state состояний. Функция возвращает список состояний просто объединяя все состояния в обоих списках. Порядок, в котором состояния представлены в списке, это порядок, в котором состояния были получены. Используя различные версии функций is-goal, expand-state, combine-states мы можем реализовать почти каждый поисковый алгоритм, использующий поиск по дереву. Рекурсивная версия функции поиска по дереву. (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)))) Эта функция выполняет поиск по дереву, начиная с состояний заданных аргументом states, пока не будет достигнуто состояние, для которого предикат is-goal вернет значение не NIL. Функция expand-state используется для генерации новых состояний, достижимых из данного. Функция combine-states используется для объединения сгенерированных состояний с предыдущими. Поиск реализован рекурсивно. Теперь мы можем использовать функцию поиска по дереву – tree-search для реализации алгоритмов поиска в глубину и в ширину. Функция поиска в глубину – depth-first-search имеет следующий вид: (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))) ) Функция depth-first-search выполняет поиск в глубину, начиная с состояния state, до тех пор, пока не будет найдено целевое состояние. Функция expand-state используется для генерации дочерних состояний. Функция tree-searcher используется для выполнение алгоритма поиска по дереву. Лабиринт Лабиринт представим структурой. Структура для описания лабиринта должна иметь следующие поля: строку и столбец начальной позиции, и строку и столбец целевой позиции. В структуру входит также двумерный массив, который показывает расположение стен в лабиринте. (defstruct maze «Двумерный лабиринт» start-row; Строка начальной позиции. start-column; Столбец начальной позиции. goal-row; Строка целевой позиции. goal-column; Столбец целевой позиции. grid; Двумерный массив элементы которого принимают ; значение не NIL, там где в лабиринте расположены ; стены, и NIL - на свободных местах. Первый индекс ; массива - индекс строк, второй - индекс столбцов. ; Нумерация начинается с нуля. ;Например, индекс элемента, расположенного во ; второй строке и третьем столбце - (1, 2). ) Мы можем представить состояние как список из двух элементов. Первый элемент списка – список уже посещенных позиций на пути из стартовой позиции к текущей. Второй элемент списка – лабиринт, который представлен, как описано выше. Функция печати лабиринта maze-print получает два аргумента: лабиринт и список пройденных позиций: (defun maze-print (maze positions) ... ) Для печати переданного лабиринта функция использует несколько символов: - символ '#' используется для изображения стен; - символ 'O' используется для изображения стартовой позиции; - символ 'X' используется для изображения целевой позиции. Перед лабиринтом не печатается пустая строка. Пустая строка печатается в конце каждой строки лабиринта, включая последнюю. Список positions содержит пройденные позиции (найденный в лабиринте путь). Они изображаются символом '.'.
Функция maze-is-goal возвращает не NIL, если указанный лабиринт решен, т. е., если стартовая и целевая позиции одинаковы. (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)))) )
Функция maze-expand возвращает список состояний лабиринта, достижимых за одно перемещение. Состояние достижимо, если новая стартовая позиция получается одним перемещением влево, вправо, вверх или вниз относительно начальной стартовой позиции и координаты этой позиции не совпадают с координатами стены. (defun maze-expand (maze-state) (let ((maze (second maze-state))) (labels ((is-empty (row column) ; Возвращает не-NIL если лабиринт не содержит стену (not (aref (maze-grid maze) row column))) (new-maze-if-legal (row column) ; Возвращает состояние лабиринта, соответствующее (and (array-in-bounds-p (maze-grid maze) row column) (is-empty row column) (not (member (list row column) (first maze-state) :test #'equal)) (list ;Новая позиция добавляется в начало списка ;позиций (cons (list row column) (first maze-state)) ; Новый лабиринт такой же как и старый, ; различны только стартовые позиции (make-maze:start-row row :start-column column :goal-row (maze-goal-row maze) :goal-column (maze-goal-column maze) :grid (maze-grid maze)))))) (let ((row (maze-start-row maze)) (column (maze-start-column maze))) (remove nil ; Формируем список достижимых состояний. ; Некоторые элементы могут быть равны NIL, ; если попытки перемещения закончились неудачей (mapcar #'new-maze-if-legal (list (1- row) (1+ row) row row) (list column column (1- column) (1+ column)))))))
) Примечание: функция labels эквивалентна функции let, но работает с функциями, а не с переменными. Например: (labels ((factorial (n) (if (= n 0) 1 (* n (factorial (- n 1)))))) (factorial 3)) Функция maze-solve решает заданный лабиринт, печатает решение. Если решения не существует, печатает соответствующее сообщение. Эту функцию можно определить следующим образом: (defun maze-solve (maze search-strategy tree-searcher) (format t «Attempting to solve the following maze:~%») (maze-print maze nil) (terpri) (let ((solution (funcall search-strategy (list (list (list (maze-start-row maze) (maze-start-column maze))) maze) #'maze-is-goal #'maze-expand tree-searcher))) (if solution (progn (format t «Solution:~%») (maze-print (second solution) (first solution)) ) (format t «No solution exists.~%»)) solution))
Ниже приведено несколько примеров использования выше перечисленных функций. Примеры. >(maze-solve complex-maze #'breadth-first-search #'iterative-tree-search) Attempting to solve the following maze: ########## # # # ## # ### # # # # # # ## # # # ## ##### # # 0 # ## ### # # ## # X ########
Solution: ########## # # # ## # ### # # # # # # ## # # # ## ##### # #....... #...## ### #.# ## # ..######## (((9 0) (9 1) (8 1) (7 1) (7 2) (7 3) (6 3) (6 4) (6 5) (6 6) (6 7) (6 8) (6 9)) #S(MAZE START-ROW 9 START-COLUMN 0 GOAL-ROW 9 GOAL-COLUMN 0 GRID #2A((T T T T T T T T T T) (T NIL NIL T NIL NIL NIL NIL NIL T) (T T NIL T NIL T T T NIL T) (T NIL NIL NIL NIL T NIL T NIL T) (T NIL T T NIL T NIL NIL NIL T) (T NIL T T NIL T T T T T) (T NIL T NIL NIL NIL NIL NIL NIL NIL) (T NIL NIL NIL T T NIL T T T) (T NIL T NIL T T NIL NIL NIL T) (NIL NIL T T T T T T T T))))
Ниже представлено несколько лабиринтов, которые Вы можете использовать для тестирования программы: (defconstant simple-maze (make-maze:start-row 0 :start-column 0 :goal-row 2 :goal-column 2 :grid #2A((nil nil t) (nil t t) (nil nil nil))) «A very simple maze.»)
(defconstant complex-maze (make-maze:start-row 6 :start-column 9 :goal-row 9 :goal-column 0 :grid #2A( (t t t t t t t t t t) (t nil nil t nil nil nil nil nil t) (t t nil t nil t t t nil t) (t nil nil nil nil t nil t nil t) (t nil t t nil t nil nil nil t) (t nil t t nil t t t t t) (t nil t nil nil nil nil nil nil nil) (t nil nil nil t t nil t t t) (t nil t nil t t nil nil nil t) (nil nil t t t t t t t t))) «A more complex maze.»)
|
