Формулировка задачи

Задача любого агента может быть определена с помощью четырех компонентов: начального состояния, функции определения преемника, функции проверки цели и функции определения стоимости пути.

1. Начальное состояние (X) — это состояние, в котором агент приступает к работе, например начальное состояние для нашего агента может быть описано, как пребывание в Лос-Анджелесе.

2. Функция определения преемника (S(x)) — представляет собой описание возможных действий, доступных агенту. Так, если задано конкретное состояние х, то функция S(x) возвращает множество состояний, которые могут быть достигнуты из х, например из состояния Лос-Анджелес, функция определения преемника возвратит города Сан-Фернандо и Санта-Моника (см. рис.1), т.е. S(Лос-Анджелес) = {Сан-Фернандо, Санта-Моника}.

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

Рис.3. Пространство состояний задачи

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

3. Функция проверки цели (C(x)) позволяет определить, является ли данное конкретное состояние целевым. Эта функции принимает два значения: ИСТИНА, если состояние х является целью, или ЛОЖЬ — в противном случае, например С(Лос-Анджелес) = ЛОЖЬ, С(Лонг Бич) = ЛОЖЬ, а С(Санта-Барбара) = ИСТИНА.

4. Функция стоимости пути (U) назначает каждому пути числовое значение. Данная функция используется, когда агент находит несколько путей и из них необходимо выбрать самый оптимальный, например самый короткий по протяженности в километрах. Следует отличать понятия стоимости пути и стоимости этапа f(x, y). Стоимость этапа определяет стоимость единичного перехода из состояния х в состояние у. Стоимость пути складывается из стоимости этапов.

Таким образом, задача поиска представляется четверкой <X, S(x), C(x), U>. Решением задачи является путь от начального состояния в целевое, а качество решения определяется с помощью функции стоимости пути. Оптимальным является такое решение, которое имеет наименьшую стоимость пути из всех имеющихся.

Таким образом, задача нашего агента следующая. X = Лос-Анджелес. S(x) определяет города, соседние с х, С(х) принимает значение ИСТИНА тогда, когда х = Санта-Моника, где х — некоторое промежуточное состояние. Для простоты предположим, что расстояния между городами равны (или неизвестны), и функцию U определим как количество посещенных городов. Оптимальным будет являться путь с наименьшим числом посещенных городов.

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

Дата добавления: 2015-07-26; просмотров: 185; Нарушение авторских прав

Мы поможем в написании ваших работ!