Главная arrow Поиск arrow Структурированные задачи
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Структурированные задачи Печать
Задача может быть формально определена с помощью четырех компонентов,
описанных ниже.

  • Начальное состояние, в котором агент приступает к работе. Например, начальное состояние для нашего агента в Румынии может быть описано как пребывание в Араде, In (Arad).
  • Описание возможных действий, доступных агенту. В наиболее общей формулировке используется функция определения преемника. Если задано конкретное состояние х, то функция Successor-Fn(x) возвращает множество упорядоченных пар <action, successor>, где каждое действие action представляет собой одно из допустимых действий в состоянии х, а каждый преемник successor представляет собой состояние, которое может быть достигнуто из х путем применения этого действия. Например, из состояния in(Arad) функция определения преемника для данной задачи проезда по Румынии возвратит следующее: {<Go{Sibiu) , In{Sibiu)>, <Go{Timisoara) , In(Timisoara) >, <Go(Zerind), In(Zerind)>}

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


  • Проверка цели, позволяющая определить, является ли данное конкретное состояние целевым состоянием. Иногда имеется явно заданное множество возможных целевых состояний, и эта проверка сводится просто к определению того, является ли данное состояние одним из них. Цель рассматриваемого агента в Румынии представляет собой одноэлементное множество {In {Bucharest) }. Иногда цель задается в виде абстрактного свойства, а не явно перечисленного множества состояний. Например, в шахматах цель состоит в достижении состояния, называемого «матом», в котором король противника атакован и не может уклониться от удара.
  • Функция стоимости пути, которая назначает числовое значение стоимости каждому пути. Агент, решающий задачу, выбирает функцию стоимости, которая соответствует его собственным показателям производительности. Для данного агента, пытающегося попасть в Бухарест, важнее всего время, поэтому стоимость пути может измеряться длиной в километрах. Предполагается, что стоимость пути может быть описана как сумма стоимостей отдельных действий, выполняемых вдоль этого пути. Стоимость этапа, связанного с выполнением действия а для перехода из состояния х в состояние у, обозначается как с (х, а, у). Стоимости этапов для Румынии показаны на рисунке в виде дорожных расстояний. Предполагается, что стоимости этапов являются неотрицательными.

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