Яка з перелічених нижче функцій не відноситься до функцій управління?

Дата добавления: 2015-08-30; просмотров: 883

В этой лабораторной работе мы подробно рассмотрим технику, известную как поиск в пространстве состояний. Каждая конфигурация, в которой может пребывать система, называется состоянием. Из каждого состояния можно переместиться в некоторое множество других состояний. Одно состояние называется стартовым, другое – целевым. Задача состоит в том, чтобы найти последовательность перемещений, ведущих из стартового состояния в целевое. В лабораторной работе применение алгоритмов поиска в пространстве состояний мы рассмотрим на примере задачи поиска пути в лабиринте. Пусть, есть такой лабиринт:

#####

#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 если лабиринт не содержит стену
; в указанной позиции (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))))

Ниже представлено несколько лабиринтов, которые Вы можете использовать для тестирования программы:

(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.»)