Хорошо структурированные задачи и решения
Задача может быть формально определена с помощью четырех компонентов, описанных ниже.
• Начальное состояние, в котором агент приступает к работе. Например, начальное состояние для нашего агента в Румынии может быть описано как пребывание в Араде, In (Arad).
• Описание возможных действий, доступных агенту. В наиболее общей формулировке3 используется функция определения преемника. Если задано конкретное состояние х, то функция Successor-Fn (х) возвращает множество упорядоченных пар
{
Начальное состояние и функция определения преемника, вместе взятые, неявно задают пространство состояний данной задачи — множество всех состояний, достижимых из начального состояния. Пространство состояний образует граф, узлами которого являются состояния, а дугами между узлами — действия. (Карта Румынии, показанная на рис. 3.1, может интерпретироваться как граф пространства состояний, если каждая дорога рассматривается как обозначающая два действия проезда на автомобиле, по одному в каждом направлении.) Путем в пространстве состояний является последовательность состояний, соединенных последовательностью действий.
• Проверка цели, позволяющая определить, является ли данное конкретное состояние целевым состоянием. Иногда имеется явно заданное множество возможных целевых состояний, и эта проверка сводится просто к определению того, является ли данное состояние одним из них. Цель рассматриваемого агента в Румынии представляет собой одноэлементное множество {In {Bucharest) }. Иногда цель задается в виде абстрактного свойства, а не явно перечисленного множества состояний. Например, в шахматах цель состоит в достижении состояния, называемого "матом", в котором король противника атакован и не может уклониться от удара.
• Функция стоимости пути, которая назначает числовое значение стоимости каждому пути. Агент, решающий задачу, выбирает функцию стоимости, которая соответствует его собственным показателям производительности. Для данного агента, пытающегося попасть в Бухарест, важнее всего время, поэтому стоимость пути может измеряться длиной в километрах. В настоящей главе предполагается, что стоимость пути может быть описана как сумма стоимостей отдельных действий, выполняемых вдоль этого пути. Стоимость этапа, связанного с выполнением действия а для перехода из состояния х в состояние у, обозначается как с (х, а, у). Стоимости этапов для Румынии показаны на рис. 3.1 в виде дорожных расстояний. Предполагается, что стоимости этапов являются неотрицательными4.
Описанные выше элементы определяют задачу и могут быть собраны вместе в единую структуру данных, которая передается в качестве входных данных в алгоритм решения задачи. Решением задачи является путь от начального состояния до целевого состояния. Качество решения измеряется с помощью функции стоимости пути, а оптимальным решением является такое решение, которое имеет наименьшую стоимость пути среди всех прочих решений.