8124

Поиск в пространстве состояний. Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий

Лекция

Информатика, кибернетика и программирование

Поиск в пространстве состояний.Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий. Многие задачи,в частности игры и головоломки,могут быть представлены как задачи поиска в пространств...

Русский

2013-02-04

116.01 KB

17 чел.

Поиск в пространстве состояний. Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий.

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

Решить задачузначит найти путь из исходного состояния в целевое.

Формально задача поиска в пространстве состояний в общем случае задается четверкой:

<I, {Oi}, GT, PC>,

где Iисходное состояние, т. е. состояние мира в начале задачи;

     {Oi} –множество действий (операторов), возможных в различных состояниях;

      GT (goal test) –проверка достижения целевого состояния;

      PC (path cost) –функция стоимости пути.

Действия (операторы) переводят состояния в другие состояния. Таким образом, можно ввести в рассмотрение функцию последователей S (successor), ставящую в соответствие каждому состоянию x множество состояний S(x), достижимых из x за одно действие.

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

Проверка достижения целевого состояния позволяет для каждого достигнутого состояния определить является ли оно целевым. Существует два способа задания целевых состояний:

  •  явное перечисление множества целевых состояний;
  •  использование предикатов, описывающих целевые состояния.

Как правило, некоторое решение задачи является более предпочтительным, чем другие. 

Функция PC (path cost) позволяет вычислить стоимость пути в заданных единицах. Как правило PC является аддитивной оценкой, т. е. стоимость пути вычисляется как сумма стоимостей элементов пути (операторов).

Для описания  алгоритмов реализации поиска в пространстве состояний компоненты задачи должны быть представлены соответствующими данными:

datatype Problem component : INITIAL-STATE, Оperations, Goal Test, Path-Cost-Funct.

Эффективность того или иного метода поиска определяется ответами на следующие вопросы:

  1.  Находит ли он решение в принципе (полнота);
  2.  Является ли найденное решение хорошим (т.е. имеющим низкую стоимость пути).
  3.  Какова стоимость реализации поиска, определяемая временем и памятью, требуемыми для нахождения решения (пути).

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

Процесс поиска в пространстве состояний удобно рассматривать как построение дерева поиска, которое накладывается на пространство состояний.

Корнем этого дерева является вершина соответствующая начальному состоянию.

Листья дерева соответствуют состоянию, не имеющему потомков в дереве, либо из-за того, что они еще не были раскрыты, либо они сгенерировали пустое множество потомков.

На каждом шаге алгоритм поиска выбирает для раскрытия одну концевую вершину.

Общий алгоритм поиска можно представить следующим образом:

Function General-Search (Problem, Strategy) returns solution or failure

Инициализация дерева поиска исходным состоянием задачи I

Loop do  - цикл

if (нет вершин - кандидатов для раскрытия)

then return failure

Выбрать концевую вершину (лист) для раскрытия в соответствии со стратегией.

if (вершина содержит целевое состояние)

then return solution (путь к этой вершине)

else

 Раскрыть вершину и добавить новые вершины в дерево поиска.

end

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

. Состояние в пространстве состояний, которому сопоставлена вершина.

. Родительская вершина –это вершина, непосредственным потомком которой является данная вершина.

. Оператор, в результате применения которого была порождена  данная вершина.

. Глубина вершинычисло вершин в пути от корня дерева к данной вершине.

. Стоимость пути от корневой вершины к текущей.

Таким образом, необходимо различать вершины и состояния в пространстве поиска.

Состояние представляет собой элемент пространства состояний , т.е. некоторое состояние мира. Вершинаэто структура данных, используемая для представления дерева поиска. Таким образом, вершина имеет глубину и родителей, а состояния не имеют.

Множество вершин, ожидающих раскрытия, принято называть каймой или границей (fringer).

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

С алгоритмической точки зрения граничное множество удобно представить очередью и определить над ней следующие операции:

. make-Queue (Elements) –создание очереди с заданными элементами;

. empty?(Queue) –возвращает true, если очередь пуста;

. remove-front(Queue) –возвращает первый элемент очереди и удаляет его из очереди;

. Queueing-Fn(Elements, Queue) –добавляет в очередь множество элементов. Именно эта функция определяет разные стратегии, реализующие разные алгоритмы поиска.

С использованием введенных обозначений можно записать алгоритм поиска:

function General-Search(Problem, Queuing-Fn) returns solution or failure

    nodes  make-Queue(Make-Node(Init-State[Problem]) //присваивание

    Make-Node;  // порождение вершины, т.е. получили корень

     loop do

if  nodes = 0 then return failure

node  Remove-Front (nodes)

         if Goal-Test[problem] (State(node))=true

 then return node

 else nodes  Queueing-Fn(nodes, Expand(node, OPERATORS[Problem]))

end

Последний оператор к множеству уже существующих вершин добавляет результат раскрытия Expand. OPERATORS обеспечивают переход из одного состояния в другое. Результатом являются все возможные потомки в вершине Expand.

3


 

А также другие работы, которые могут Вас заинтересовать

83809. Современные тенденции совершенствования налоговой системы Российской Федерации 39.76 KB
  Основные направления налоговой политики принимаются ежегодно Основные направления бюджетной политики на 2015 год и на плановый период 2016 и 2017 годов принимаются и рассматриваются одновременно с проектом закона о федеральном бюджете на текущий период 3 года и утверждаются на заседании правительства РФ. Политики: Поддержка инвестиций Развитие человеческого капитала Повышение предпринимательской активности.
83810. Налоговое администрирование. Структура налоговых органов РФ, их полномочия и функции 41.21 KB
  Структура налоговых органов РФ их полномочия и функции. Нет единой точки зрение на определение налогового администрирования Налоговое администрирование система управления налоговыми правоотношениями или всем комплекс налоговых отношений Титов Налог.администрирование деятельность и управление налоговых органов по осуществлению контроля за соблюдением налогового законодательства. Однако все определения условно можно объединить в 3 блока: Связанные с управлением Не связанные с управлением Опровергающие существование самого этого понятия...
83811. Правовое положение, функции и полномочия Министерства финансов РФ в налоговой сфере 41.23 KB
  Министерство финансов Российской Федерации Минфин России является федеральным органом исполнительной власти осуществляющим функции по выработке государственной политики и нормативноправовому регулированию в сфере бюджетной налоговой страховой валютной банковской деятельности государственного долга аудиторской деятельности бухгалтерского учета и бухгалтерской отчетности производства переработки и обращения драгоценных металлов и драгоценных камней таможенных платежей определения таможенной стоимости товаров и транспортных...
83812. Правовое положение Федеральной налоговой службы и её органов (структурных подразделений) 40.57 KB
  Основные функции возложенные на ФНС России по контролю и надзору: за соблюдением законодательства РФ о налогах и сборах; за правильностью исчисления полнотой своевременностью внесения в соответствующий бюджет налогов и сборов и иных обязательных платежей; за производством и оборотом этилового спирта спиртосодержащей алкогольной и табачной продукции; за соблюдением валютного законодательства в пределах компетенции налоговых органов; за информированием налогоплательщиков по вопросам налогового законодательства и разъяснением системы...
83813. Анализ действующей налоговой системы, современного налогового законодательства и направления налоговой реформы 40.05 KB
  Основные направления налоговой политики принимаются ежегодно Основные направления бюджетной политики на 2015 год и на плановый период 2016 и 2017 годов принимаются и рассматриваются одновременно с проектом закона о федеральном бюджете на текущий период 3 года и утверждаются на заседании правительства РФ. Политики: Поддержка инвестиций Развитие человеческого капитала Повышение предпринимательской активности.
83814. Правовое регулирование налога на добавленную стоимость: налогоплательщики и основные элементы налога 44.09 KB
  НДС это косвенный налог. Плательщиками НДС признаются: организации в том числе некоммерческие предприниматели Условно всех налогоплательщиков НДС можно разделить на две группы: налогоплательщики внутреннего НДС т. НДС уплачиваемого при реализации товаров работ услуг на территории РФ налогоплательщики ввозного НДС т. НДС уплачиваемого при ввозе товаров на территорию РФ Освобождение от исполнения обязанностей плательщиков НДС Организации и предприниматели у которых за 3 предшествующих последовательных календарных месяца сумма...
83815. Правовое регулирование акцизов: налогоплательщики, основные элементы налога. Обязанности взимания акциза при ввозе и вывозе подакцизных товаров Таможенного союза 47.79 KB
  Обязанности взимания акциза при ввозе и вывозе подакцизных товаров Таможенного союза. Налогоплательщики: 1 организации; 2 индивидуальные предприниматели; 3 лица признаваемые налогоплательщиками в связи с перемещением товаров через таможенную границу Таможенного союза определяемые в соответствии с таможенным законодательством Таможенного союза и законодательством Российской Федерации о таможенном деле. Объектом налогообложения признаются следующие операции: 1 реализация на территории Российской Федерации лицами произведенных ими...
83816. Правовое регулирование налога на доходы физических лиц: налогоплательщики, основные элементы налогообложения, особенности налоговых льгот 46.1 KB
  Налогоплательщиками признаются физические лица являющиеся налоговыми резидентами Российской Федерации а также физические лица получающие доходы от источников в Российской Федерации не являющиеся налоговыми резидентами Российской Федерации. Налоговыми резидентами признаются физические лица фактически находящиеся в Российской Федерации не менее 183 календарных дней в течение 12 следующих подряд месяцев. Налоговыми резидентами в 2015 году признаются физические лица фактически находящиеся в Российской Федерации на территориях Республики...
83817. Правовое регулирование налога на прибыль организаций: налогоплательщики, основные элементы налогообложения, особенности определения доходов и расходов у разных налогоплательщиков 49.15 KB
  Расходы. Группировка расходов Расходы это обоснованные и документально подтвержденные затраты предприятия. Они делятся на расходы связанные с производством и реализацией зарплата сотрудников покупная стоимость сырья и материалов амортизация основные средств и пр. и на внереализационные расходы отрицательная курсовая разница судебные и арбитражные сборы и пр.