Работы : алгоритмы поиска в пространстве состояний




Скачать 92.32 Kb.
НазваниеРаботы : алгоритмы поиска в пространстве состояний
Дата22.12.2012
Размер92.32 Kb.
ТипЛабораторная работа
Лабораторная работа № 1


Тема работы: алгоритмы поиска в пространстве состояний.


Цели работы:

  • изучить алгоритмы слепого поиска;

  • разработать программную систему, реализующую выбранный алгоритм;

  • провести тестирование программы;

  • исследовать работу системы.



Теоретические сведения
Алгоритмы поиска решения



Классификация алгоритмов


Поиск в пространстве состояний базируется на последовательном построении (переборе) вершин графа состояний – до тех пор, пока не будет обнаружено целевое состояние. Введем несколько терминов, которые будем использовать для описания различных алгоритмов поиска.

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

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

Вершины и указатели, построенные в процессе поиска, образуют поддерево всего неявно определенного при формализации задачи графа-пространства состояний. Это поддерево называется деревом перебора.

Известные алгоритмы поиска в пространстве состояний можно классифицировать по различным характеристикам, а именно:

использование эвристической информации;

порядок раскрытия (перебора) вершин;

полнота просмотра пространства состояний;

направление поиска.

В соответствии с первой характеристикой алгоритмы делятся на два класса – слепые и эвристические. В слепых алгоритмах поиска местонахождение в пространстве целевой вершины никак не влияет на порядок, в котором раскрываются (перебираются) вершины. В противоположность им, эвристические алгоритмы используют априорную, эвристическую информацию об общем виде графа-пространства и/или о том, где в пространстве состояний расположена цель, поэтому для раскрытия обычно выбирается более перспективная вершина. В общем случае это позволяет сократить перебор.

Два основных вида слепых алгоритмов поиска, различающихся порядком раскрытия вершин – это алгоритмы поиска вширь и поиска вглубь.

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

В соответствии с направлением поиска алгоритмы можно разделить на прямые, ведущие поиск от начальной вершины к целевой, обратные, ведущие поиск от целевой вершины в направлении к начальной, и двунаправленные, чередующие прямой и обратный поиск. Наиболее употребительными (отчасти, в силу их простоты) являются алгоритмы прямого поиска. Обратный поиск возможен в случае обратимости операторов задачи.

Методы слепого (полного) перебора

Слепые алгоритмы поиска вширь (breadth_first_search) и поиска вглубь (depth_first_search) отличаются тем, какая вершина выбирается для очередного раскрытия. В алгоритме перебора вширь вершины раскрываются в том порядке, в котором они строятся. В алгоритме же перебора в глубину прежде всего раскрываются те вершины, которые были построены последними.

Рассмотрим эти алгоритмы для пространств, являющихся деревьями (корнем дерева является начальная вершина). Затем покажем, как алгоритмы следует модифицировать для поиска в произвольных графах. Организовать перебор в деревьях проще, так как при построении нового состояния (и соответствующей вершины) можно быть уверенным в том, что такое состояние никогда раньше не строилось и не будет строиться в дальнейшем.


Перебор вширь

Базовый алгоритм поиска вширь состоит из следующей последовательности шагов (здесь и далее предполагаем, что начальная вершина не является целевой):

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

Шаг 5. Проверить, нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей назад от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

Конец алгоритма.

Основу этого алгоритма составляет цикл последовательного раскрытия (шаги 2-5) концевых вершин (листьев) дерева перебора, хранящихся в списке Open. Алгоритм поиска вширь является полным. Можно также показать, что при переборе вширь непременно будет найден самый короткий путь к целевой вершине, причем быстрее, чем другие решающие пути – при условии, что этот путь вообще существует. Если же решающего пути нет, то (в случае конечных деревьев-пространств) будет сообщено о неуспехе поиска, в случае же бесконечных пространств алгоритм не кончит свою работу.

В случае поиска на произвольном графе (и в этом – отличие от деревьев-пространств) одно и тоже состояние может быть продублировано в разных частях полученного дерева перебора. В примере игры в восемь по принятому предположению об операции раскрытия исключалось только повторное возникновение состояний, встречавшихся два шага вверх по дереву перебора, другие же, более далекие друг от друга повторы одного и того же состояния остаются возможными. В случае поиска в графе состояний общего вида он как бы разворачивается при поиске в дерево путем дублирования некоторых его частей. Если это дублирование неоднократное (из-за циклов в графе), то оно может привести к зацикливанию базового алгоритма поиска вширь.


Перебор вглубь

Для формулировки алгоритма поиска вглубь необходимо определить понятие глубины вершины в дереве поиска. Это можно сделать следующим образом:

глубина корня дерева равна нулю;

глубина каждой некорневой вершины на единицу больше глубины ее родительской вершины.

В алгоритме перебора вглубь раскрытию в первую очередь подлежит вершина, имеющая наибольшую глубину. Такой принцип может привести к бесконечному процессу – это происходит, если пространство состояний бесконечно, и поиск вглубь пошел по ветви дерева, не содержащей целевую вершину. Поэтому необходимо то или иное ограничение этого процесса, самый распространенный способ – ограничить глубину просмотра дерева. Это означает, что в ходе перебора можно строить только вершины, глубина которых не превышает некоторую заданную граничную глубину. Тем самым, раскрытию в первую очередь подлежит вершина наибольшей глубины, но расположенная выше фиксированной границы. Соответствующий алгоритм поиска называется ограниченным перебором вглубь.

Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной D) таковы:

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

Шаг 4. Если глубина вершины Current равна граничной глубине D, то перейти к шагу 2, в ином случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

Шаг 6. Если среди дочерних есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

Конец алгоритма.

Приведенное только что описание очень похоже на описание алгоритма поиска вглубь, разница заключается только в ограничении глубины (шаг 4) и в месте списка Open, куда помещаются построенные дочерние вершины (шаг 5).

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

Для решения задач в конкретной постановке применяются различные модификации переборных алгоритмов.


Волновой алгоритм

Рассмотрим задачу поиска по карте местности кратчайшего маршрута, соединяющего две заданные точки. Если бы все участки были проходимы, то оптимальный маршрут строился бы легко — это отрезок прямой, соединяющий указанные точки. Будем предполагать, что карта местности разбивается на мелкие квадраты, размером которых можно пренебречь, и координаты точки пересечения диагоналей квадрата примем за координаты этого квадрата.

Всю карту можно представить в виде двухмерного целочисленного массива Map, индексы которого — координаты соответствующих точек, а значения — признак возможности прохождения точки с координатами х и у. Map [х, у] = 0, если участок проходим, и Map [х, у]=1, если нет.

Две точки будем называть соседними, если они имеют только одну различную координату (например, точки Map [5, 4] и Map [6, 4] — соседние, а точки Map [5, 4] и Map [6, 3] — нет). Маршрутом будем считать последовательность соседних точек карты. Длиной маршрута будем считать число клеток в нем (это определение соответствует случаю равнинной местности, когда при преодолении любого квадрата проходится примерно одинаковый путь).

В терминах этой модели исходная задача формулируется так: даны двухмерный числовой массив Map с элементами, равными 0 и —1, и две пары индексов (две точки): x_begin, y_begin и x_end, y_end. Требуется построить последовательность соседних элементов с нулевыми значениями такую, чтобы первым элементом в ней был Map [x_begin, y_begin] , а последним — Map [x_end, y_end], причем число элементов в ней было бы минимальным из всех возможных. Для решения задачи будем использовать волновой алгоритм.


Описание волнового алгоритма:

1. Начальный этап. Пометим начальную точку числом 1 (в эту точку ведет маршрут длины 0).

2. Распространение волны. Если рассматриваемая точка помечена числом К > 0 (в нее можно попасть за К—1 шагов), то все соседние точки, помеченные нулем, надо пометить числом К + 1 (в них можно попасть за К шагов). Распространение волны осуществляется до тех пор, пока это возможно (есть еще соседние, помеченные нулем, точки) и целесообразно (еще не дошли до конечной точки).

3. Проверка возможности построения пути. Если после распространения волны конечная точка помечена некоторым числом К > 0, то в нее можно попасть за К— 1 шаг. В противном случае эта точка недостижима из начальной.

4. Построение пути. Для того, чтобы построить оптимальный маршрут, необходимо, начиная с конечной точки, выбирать соседнюю с ней, помеченную числом на единицу меньше. Затем проделать это же с новой точкой. Описанный процесс продолжают до тех пор, пока не будет достигнута начальная точка.

Из описания алгоритма видно, что он распадается на два этапа: распространение волны (включая начальный этап) и построение пути. Такая структура позволяет естественным образом разбить исходный алгоритм на две процедуры.

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

Задание.

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

  2. Найти решение головоломки «8». Отобразить последовательность состояний игры, используя алгоритм поиска в ширину. Исходное состояние задается пользователем.

  3. Отобразить последовательность состояний игры, используя алгоритм поиска в глубину. Исходное состояние задается вводом.

  4. Дан неориентированный граф. Отобразить последовательность раскрываемых вершин при поиске в ширину. Количество вершин, матрица смежности(список связности), начальная и конечная вершина задаются пользователем.

  5. Дан неориентированный граф. Отобразить последовательность раскрываемых вершин при поиске в глубину. Количество вершин, матрица смежности(список связности), начальная и конечная вершина задаются пользователем.

Похожие:

Работы : алгоритмы поиска в пространстве состояний icon1. Алгоритм поиска работы
В специальной литературе процесс поиска работы представляют последовательностью определенных стадий активной деятельности соискателя....
Работы : алгоритмы поиска в пространстве состояний iconМоделирование в фазовом пространстве состояний психофизиологических функций учащихся югры

Работы : алгоритмы поиска в пространстве состояний iconНеизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай
Необходимой, а иногда и достаточной, частью такого тестирования является обход графа состояний автомата. Основное внимание уделяется,...
Работы : алгоритмы поиска в пространстве состояний iconЗадача о минимальном потоке в сети и алгоритмы ее решения
Каспшицкая М. Ф., Сергиенко И. В. О понятии линейности и выпуклости в одном дискретном пространстве. Комбинаторные линейные задачи....
Работы : алгоритмы поиска в пространстве состояний iconЭкзаменационные вопросы интернет-курсов интуит (intuit) : Распределенные системы и алгоритмы
В информационном пространстве к субъектам, осуществляющих информационное взаимодействие, можно отнести
Работы : алгоритмы поиска в пространстве состояний iconПоиск ключа в массиве. Анализ эффективности алгоритмов поиска
Целью работы является закрепление практических навыков по реализации алгоритмов поиска, а также анализ эффективности их работы
Работы : алгоритмы поиска в пространстве состояний iconСодержание программы дисциплины "синтез дискретных систем управления"
Системы со многими входами и выходами. Описание с помощью полиномиальных матриц. Описание в пространстве состояний. Степень, полюсы...
Работы : алгоритмы поиска в пространстве состояний iconМетодические указания по выполнению контрольной работы №1 по дисциплине Информатика На тему: Линейные алгоритмы. Разветвляющиеся алгоритмы для студентов II курса заочного отделения специальности
Контрольная работа — это самостоятельная работа студента по дисциплине «Информатика»
Работы : алгоритмы поиска в пространстве состояний iconРабочая программа учебной дисциплины «адаптивные и оптимальные системы управления»
Целью дисциплины является изучение основ современной теории оптимизации и оптимального управления технологическими процессами, методов...
Работы : алгоритмы поиска в пространстве состояний iconОбход неизвестного ориентированного графа конечным роботом
Это аналогично задаче обхода лабиринта роботом, находящимся внутри него и не имеющем плана лабиринта. Если робот – это «компьютер...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница