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

Хотя такое требование по минимизации коэффициента конкурентоспособности может показаться резонным, можно легко доказать, что в некоторых случаях наилучший достижимый коэффициент конкурентоспособности (competitive ratio) является бесконечным. Например, если некоторые действия необратимы, то поиск в оперативном режиме может в конечном итоге перейти в тупиковое состояние, из которого не достижимо целевое состояние. Возможно, читатель сочтет выражение "в конечном итоге' неубедительным; в конце концов, должен же существовать такой алгоритм, который окажется способным не упираться в тупик в ходе проведения исследований с его помощью! Поэтому уточним приведенное выше утверждение таким образом: ни один алгоритм не позволяет избежать тупиков во всех возможных пространствах состояний. Рассмотрим два пространства состояний с тупиками, показанные на рис. 4.13, а. Для алгоритма поиска в оперативном режиме, который посетил состояния S и А, оба эти пространства состояний представляются идентичными, поэтому он должен принять одинаковое решение в обоих из них. Поэтому в одном из этих состояний алгоритм потерпит неудачу. Это — один из примеров возражения противника (adversary argument), поскольку легко себе представить, как противник формирует пространство состояний в ходе того, как это пространство исследуется агентом, и может размещать цели и тупики везде, где пожелает.

<< В начало < Предыдущая 1 2 3 Следующая > В конец >>