6. СТРАТЕГИИ ПОИСКА

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

Во второй главе рассматривались понятия, используемые при постановке и решении задачи в пространстве состояний, в частности было введено понятие вывода для нахождения цели. Вывод не является однозначным и после очередного шага приходится определять, какой же следующий шаг целесообразно сделать, чтобы поскорее достичь цели. Очередной шаг зависит от того, какая стратегия вывода выбрана. Понятие «вывод» обычно используют вместе с той или иной логической системой; понятие «поиск» — безотносительно к какой-либо логической системе.

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

Состояние (или состояния) среды, с которого агент начинает решение задачи, называют начальным состоянием.

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

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

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

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

6.1. Оценки успеха при поиске цели

Оценки успеха, характеризующие эффективность поиска, могут быть самыми различными. Будем полагать, что оценка успеха является положительным числом или нулем и чем больше число, тем успешнее действует агент. Тогда самая очевидная оценка — это возможность достижения цели вообще. Эта оценка носит двузначный характер: например, она принимает некоторое максимальное значение, если цель достижима, и минимальное в противном случае. Другая оценка может быть ценой пути, вычисляемой с помощью функции цены пут Третья оценка может быть ценой поиски, характеризующейся объемом необходимых для поиска времени и памяти. Наконец, еще одна оценка успеха может быть общей ценой, являющейся некоторой функцией, от цены пути и цены поиска.

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

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

Полнота: стратегия является полной при условии, что она всегда обеспечивает нахождение решения (целевого состояния или состояний), если оно вообще существует в данном пространстве состояний.

Сложность по времени: время, необходимое, для нахождения решения.

Сложность по памяти: объем памяти, необходимый для решения задачи.

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

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

Стратегии поиска разбивают на две большие группы: слепой поиск и направленный поиск. Различие между слепым и направленным поиском можно продемонстрировать на следующем простом примере. Представйм себе, что агент приехал в Россию по туристической путевке с целью совершить путешествие по золотому кольцу России. Его самолет сел в аэропорту Шереметьево.

Обратный вылет тоже из Шереметьева. Путешествие по золотому кольцу агент совершал на автобусе. Посетив все города золотого кольца, агент самостоятельно поехал в близлежащий город Иваново, где задержался и отстал от автобуса. В отличие, например, от Ярославля, Иваново не имеет прямой автострады, соединяющей, его с Москвой. У агента есть обратный билет на самолет с датой вылета на следующий день, билет не может быть продлен, да к тому же обратных билетов вообще нет на ближайшие две недели. Срок визы также заканчивается через два дня. Отправляясь в поездку, агент ставил перед собой, помимо туристических, несколько других целей: улучшить знание русского языка, завязать полезные деловые контакты, написать несколько пейзажей с вилами русской природы и т.п. Но, учитывая серьезность ситуации, главной его целью теперь стало вовремя добраться до аэропорта Шереметьево, не опоздав на свой самолет. После формулировки главной цели агент может принимать во внимание и другие факторы, влияющие на ее достижение.

Прежде всего, следует решить, что мы будем понимать под действиями и состояниями. Если бы вдруг нам пришло в голову в качестве действий выбрать такие, как «повернуть руль на 10 градусов» или «продвинуться вперед на 1 метр», то решение задачи на таком уровне детализации стало бы практически неразрешимой задачей. В нашем случае в качестве действий лучше всего выбрать переезд из одного города в другой, а в качестве состояний нахождение агента в том или ином населенном пункте. Целевым состоянием в этом случае будет нахождение агента в аэропорту Шереметьево (в Москве).

Поиск будет слепым, если агент не имеет никакой информации о дорогах, ведущих из Иванова в другие города, и будет перебирать все дороги подряд. И наоборот, его поиск станет направленным, если он ознакомится с картой, увидит, что Москва лежит на юго-западе от Иванова, и будет пытаться выбирать дороги, ведущие в юго-восточном или близком к нему направлении.