Лабораторная работа №1 Тема работы




Скачать 92.31 Kb.
НазваниеЛабораторная работа №1 Тема работы
Дата публикации14.12.2013
Размер92.31 Kb.
ТипЛабораторная работа
uchebilka.ru > Астрономия > Лабораторная работа
Лабораторная работа № 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. Дан неориентированный граф. Отобразить последовательность раскрываемых вершин при поиске в глубину. Количество вершин, матрица смежности(список связности), начальная и конечная вершина задаются пользователем.

Добавить документ в свой блог или на сайт

Похожие:

Лабораторная работа №1 Тема работы iconЛабораторная работа №7. Тема работы
Тема работы: исследование цепей переменного тока, содержащие индуктивно связанные катушки

Лабораторная работа №1 Тема работы iconЛабораторная работа №6. Тема работы
Тема работы: исследование цепи трехфазного тока при соединении приемников треугольником

Лабораторная работа №1 Тема работы iconЛабораторная работа №10 Тема
Тема: Реализация классических алгоритмов для работы с массивами и строковыми величинами в виде программ

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

Лабораторная работа №1 Тема работы iconЛабораторная работа 4 по курсу «Сетевые технологии» Тема. Работа...
Цель работы: практическое освоение построения Web-страниц с использованием гиперссылок и фреймов

Лабораторная работа №1 Тема работы iconЛабораторная работа №14 Тема
Цель работы: Закрепление знаний о множественных типах данных; о принципах работы с множествами; составление, ввод и выполнение программ...

Лабораторная работа №1 Тема работы iconЛабораторная работа 3 по курсу «Сетевые технологии» Тема. Работа...
Цель работы: практическое освоение построения Web-страниц с использованием средств мультимедиа

Лабораторная работа №1 Тема работы iconЛабораторная работа 6 по курсу «Сетевые технологии» Тема. Работа с приложениями isapi
Цель работы: практическое освоение построения Web-страниц с формами с использованием isapi

Лабораторная работа №1 Тема работы iconЛабораторная работа 5 по курсу «Сетевые технологии» Тема. Работа с приложениями cgi
Цель работы: практическое освоение построения Web-страниц с формами с использованием cgi

Лабораторная работа №1 Тема работы iconЛабораторная работа №1 Тема: Основы работы с графическим интерфейсом ос windows
Цель: Освоить основные навыки работы с помощью мыши с объектами графического интерфейса ос. Научится работать с окнами и меню

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<