Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Утверждаю
Ректор университета
__________А.В. Лагерев
“__”________ 2010 г.
ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
информированные методы поиска решения в пространстве состояний
Методические указания
к выполнению лабораторной работы № 2
для студентов очной формы обучения
специальности 230105 – «Программное обеспечение ВТ и АС»
Брянск 2010
УДК 004.65
Интеллектуальные системы. Информированные методы поиска решения в пространстве состояний: метод. указания к выполнению лабораторной работы №2 для студентов очной формы обучения специальности 230105 – «Программное обеспечение ВТ и АС». – Брянск: БГТУ, 2010 – 7 с.
Разработал:
А.К. Буйвал,
доц.
Рекомендовано кафедрой «Информатика и программное обеспечение» БГТУ (протокол № _ от _________)
Основная идея эвристического поиска состоит в том, что каждой вершине х генерируемой в процессе поиска ставится в соответствие некоторая оценка f(x) стоимости пути от начальной вершины к целевой проходящего через заданную вершину; если таких путей несколько, то каждому из них соответствует свое f(x); наиболее перспективной считается вершина с минимальной оценкой.
Рассмотрим реализацию процедуры P:
раскрыть , для всех дочерних вершин и вычислить ;
выполнить следующее:
упорядочить по возрастанию.
Пусть каждый оператор преобразования состояний имеет положительную стоимость , – вершина, генерируемая в процессе поиска. Введем для нее следующие оценки:
– текущая стоимость пути из начальной вершины к .
– оценка стоимости пути от к целевой вершине (эвристическая оценка).
В зависимости от используемых оценок можно выделить следующие виды алгоритмов:
– алгоритм равных цен (неэвристический).
– жадный алгоритм (эвристический). Эффективность данного алгоритма определяется выбором . Нахождение оптимального пути данным алгоритмом не гарантируется.
– А-алгоритм.
А-алгоритм является допустимым, т.е. находит оптимальный решающий путь (в смысле min ), если для всех вершин выполняется условие , где реальная стоимость пути из в целевую вершину.
А-алгоритм для которого выполняется это условие называется А*-алгоритмом или Харта-Нильсона-Рафаэля.
Рассмотрим пример. Пусть s - начальная вершина, а t – целевая. Рядом с состояниями (обведены окружностью) указаны их эвристические оценки (в данном случае это ожидаемое расстояние от текущего узла до целевого). Приведенные числа над дугами указывают стоимость перехода, т.е. реальное расстояние от одного узла к другому.
|
0 |
|||
|
1 |
|||
|
2 |
|||
|
3 |
|||
|
4 |
|||
|
5 |
|||
|
6 |
Дерево поиска, получаемое при работе А*-алгоритма представлено ниже.
Одним из основных недостатков алгоритма А* является большая потребность в памяти.
Простейший способ сокращения потребностей в памяти для поиска А* состоит в применении идеи итеративного углубления в контексте эвристического поиска. Реализация этой идеи привела к созданию алгоритма А* с итеративным углублением (Iterative Deepening A* – IDA*). В методе IDA* в отличии от итеративного поиска в глубину поиск ограничивается не текущим пределом глубины, а текущим пределом значений оценок узлов (т.е. эвристических f-значений узлов).
В неблагоприятных ситуациях издержки связанные с повторением поиска, которые осуществляет алгоритм IDA* становятся неприемлимыми. В этих ситуациях более целесообразно применять лучший, хотя и более сложный метод экономии пространства, получивший название RBFS (Recursive Best-First Search – рекурсивный поиск по заданному критерию). Различие между алгоритмами А* и RBFS состоит в том, что первая обеспечивает хранение в памяти всех ранее сформированных узлов, а последняя предусматривает хранение только текущего пути поиска одноранговых узлов вдоль этого пути. Если программа RBFS на время приостанавливает поиск в поддереве (поскольку оно больше не соответствует заданному критерию), то удаляет из памяти это поддерево для экономии пространства. Поэтому потребность в ресурсах пространства для алгоритма RBFS зависит от глубины поиска только линейно.
Алгоритмы IDA и RBFS страдают от того недостатка, что в них используется слишком мало памяти. Поэтому представляется разумным использование всей доступной памяти. Двумя алгоритмами, которые осуществляют это требование, являются поиск MA* (Memory-bounded A* – поиск А* с ограничением памяти) и SMA* (Simplified MA* – упрощенный поиск MA*). Алгоритм SMA* действует полностью аналогично А*, развертывая наилучшие листовые узлы до тех пор, пока не будет исчерпана доступная память. С этого момента он не может добавить новый узел к дереву поиска, не уничтожив старый. В алгоритме SMA* всегда уничтожается наихудший листовой узел (тот, который имеет наибольшее f-значение). Как и в алгоритме RBFS, после этого в алгоритме SMA* значение забытого (уничтоженного) узла резервируется в его родительском узле. Благодаря этому предок забытого поддерева позволяет определить качество наилучшего пути в этом поддереве.
|
№ Вар. |
Задание |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Пятнашки» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Пятнашки» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «О четырех конях» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «О четырех конях» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Ханойские башни» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Ханойские башни» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Пятнашки поворотом» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Пятнашки поворотом» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Повороты шариков» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Повороты шариков» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «О коне Аттилы» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «О коне Аттилы» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Двигаем шарики» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Двигаем шарики» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Кольца с цветными шариками» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Кольца с цветными шариками» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Вращаем шарики» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Вращаем шарики» методом SMA*. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Черно-белые квадраты» методом A*. Реализовать минимум две эвристические функции и сравнить их эффективность. |
|
|
Разработать и реализовать алгоритм эвристического поиска решения в пространстве состояний задачи «Черно-белые квадраты» методом SMA*. |
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Брянский государственный технический университет