В этой лабораторной работе мы подробно рассмотрим технику, известную как поиск в пространстве состояний. Каждая конфигурация, в которой может пребывать система, называется состоянием. Из каждого состояния можно переместиться в некоторое множество других состояний. Одно состояние называется стартовым, другое – целевым. Задача состоит в том, чтобы найти последовательность перемещений, ведущих из стартового состояния в целевое. В лабораторной работе применение алгоритмов поиска в пространстве состояний мы рассмотрим на примере задачи поиска пути в лабиринте. Пусть, есть такой лабиринт:
#####
#O#X#
# #
#####
Позиция, помеченная как 'O' – стартовая позиция; позиция, помеченная 'X' – целевая. Знаком '#' изображаются непрозрачные стены. Мы можем на каждом шаге перемещаться ВВЕРХ, ВЛЕВО, ВПРАВО или ВНИЗ. Одно из правильных решений этого лабиринта можно задать следующей серией перемещений: ВНИЗ ВПРАВО ВПРАВО ВВЕРХ
Конечно, другим правильным решением может быть следующая серия перемещений:
ВНИЗ ВВЕРХ ВНИЗ ВВЕРХ ВНИЗ ВПРАВО ВЛЕВО ВПРАВО ВПРАВО ВВЕРХ ВНИЗ ВВЕРХ
Итак, каждое состояние описывается:
- расположением стен;
- стартовой позицией;
- целевой позицией.
После того как сделано перемещение, новое состояние подобно старому, но содержит другую стартовую позицию.
Прежде чем писать «решатель лабиринтов», мы напишем универсальный инструмент поиска (который ничего не знает о лабиринтах), и применим его к задаче поиска пути в лабиринте. Один из алгоритмов поиска пространства состояний называется поиском преимущественно в глубину (depth-firth search). По этому алгоритму, когда из исходного состояния (s) получено новое (n), это новое состояние включается в поиск. Теперь мы пытаемся перевести систему из состояния n в состояние n1. Если состояние n1 ранее не было достигнуто, то производится его просмотр и поиск продолжается из n1. В противном случае выбирается другое достижимое из n состояние, и т. д. Например, предположим, что мы осуществляем поиск в следующем лабиринте:
######
## #
#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 если лабиринт не содержит стену ; в указанной позиции (row column)
(not (aref (maze-grid maze) row column)))
(new-maze-if-legal (row column)
; Возвращает состояние лабиринта, соответствующее ; состоянию, достижимому из состояния maze-state ; путем перемещения в новую строку и столбец, или ; NIL, если премещение не допустимо
(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))))
Ниже представлено несколько лабиринтов, которые Вы можете использовать для тестирования программы:
