Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 58

Пусть f — это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) трудности" этой вершины. Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой f принимает минимальное значение. Мы будем использовать здесь функцию f специального вида, приводящую к хорошо известному А*-алгоритму. Функция f(n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n. Давайте предположим, что такой путь существует и что t — это целевая вершина, для которой этот путь минимален. Тогда оценку f(n) можно представить в виде суммы из двух слагаемых (рис. 12.1):

 f(n) = g(n) + h(n)

Здесь g(n) — оценка оптимального пути из s в n; h(n) — оценка оптимального пути из n в t.

Когда в процессе поиска мы попадаем в вершину n, мы оказываемся в следующей ситуация: путь из s в n уже найден, и его стоимость может быть вычислена как сумма стоимостей составляющих его дуг. Этот путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из s в n), однако стоимость этого пути можно использовать в качестве оценки g(n) минимальной стоимости пути из s в n. Что же касается второго слагаемого h(n), то о нем трудно что-либо сказать, поскольку к этому моменту область пространства состояний, лежащая между n и t, еще не "изучена" программой поиска. Поэтому, как правило, о значении h(n) можно только строить догадки на основании эвристических соображений, т.е. на основании тех знаний о конкретной задаче, которыми обладает алгоритм. Поскольку значение h зависит от предметной области, универсального метода для его вычисления не существует. Конкретные примеры того, как строят эти "эвристические догадки", мы приведем позже. Сейчас же будем считать, что тем или иным способом функция h задана, и сосредоточим свое внимание на деталях нашей программы поиска с предпочтением.

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

Рис. 12.2. Поиск кратчайшего маршрута из s в t. (а) Карта со связями между городами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t. (b) Порядок, в котором при поиске с предпочтением происходит обход городов. Эвристические оценки основаны на расстояниях по прямой. Пунктирной линией показано переключение активности между альтернативными путями. Эта линия задает тот порядок, в котором вершины принимаются для продолжения пути, а не тот порядок, в котором они порождаются.

На рис. 12.2 показан пример поведения конкурирующих процессов. Дана карта, задача состоит в том, чтобы найти кратчайший маршрут из стартового города s в целевой город t. В качестве оценки стоимости остатка маршрута из города X до цели мы будем использовать расстояние по прямой расст( X, t) от X до t. Таким образом,

 f( X) = g( X) + h( X) = g( X) + расст( X, t)

Мы можем считать, что в данном примере процесс поиска с предпочтением состоит из двух процессов. Каждый процесс прокладывает свой путь — один из двух альтернативных путей: Процесс 1 проходит через а. Процесс 2 — через e. Вначале Процесс 1 более активен, поскольку значения f вдоль выбранного им пути меньше, чем вдоль второго пути. Когда Процесс 1 достигает города с, а Процесс 2 все еще находится в e, ситуация меняется:

 f( с) = g( c) + h( c) = 6 + 4 = 10

 f( e) = g( e) + h( e) = 2 + 7 = 9

Поскольку f( e) < f( c), Процесс 2 переходит к f, a Процесс 1 ждет. Однако

 f( f) = 7 + 4 = 11

 f( c) = 10

 f( c) < f( f)

Поэтому Процесс 2 останавливается, а Процессу 1 дается разрешение продолжать движение, но только до d, так как f( d) = 12 > 11. Происходит активация Процесса 2, после чего он, уже не прерываясь, доходит до цели t.

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

(1) л( В, F/G) — дерево, состоящее из одной вершины (листа); В — вершина пространства состояний, G — g( B) (стоимость уже найденного пути из стартовой вершины в В); F - f( В) = G + h( В).

(2) д( В, F/G, Пд) — дерево с непустыми поддеревьями; В — корень дерева, Пд — список поддеревьев; G — g( B); F —  уточненное значение f( В), т.е. значение f для наиболее перспективного преемника вершины В; список Пд упорядочен в порядке возрастания f-оценок поддеревьев.

Уточнение значения f необходимо для того, чтобы дать программе возможность распознавать наиболее перспективное поддерево (т.е. поддерево, содержащее наиболее перспективную концевую вершину) на любом уровне дерева поиска. Эта модификация f-оценок на самом деле приводит к обобщению, расширяющему область определения функции f. Теперь функция f определена не только на вершинах, но и на деревьях. Для одновершинных деревьев (листов) n остается первоначальное определение

 f( n) = g( n) + h( n)

Для дерева T с корнем n, имеющем преемников m1, m2, …, получаем

Программа поиска с предпочтением, составленная в соответствии с приведенными выше общими соображениями, показана на рис 12.3. Ниже даются некоторые дополнительные пояснения.

Так же, как и в случае поиска в ширину (рис. 11.13), ключевую роль играет процедура расширить, имеющая на этот раз шесть аргументов:

расширить( Путь, Дер, Предел, Дер1, ЕстьРеш, Решение)

Эта процедура расширяет текущее (под)дерево, пока  f-оценка остается равной либо меньшей, чем Предел.

% Поиск с предпочтением

эврпоиск( Старт, Решение) :-

 макс_f( Fмакс).         % Fмакс > любой  f-оценки

расширить( [], л( Старт, 0/0), Fмакс, _, да, Решение).

расширить( П, л( В, _ ), _, _, да, [В | П] ) :-

 цель( В).

расширить( П, л( В, F/G), Предел, Дер1, ЕстьРеш, Реш) :-

 F <= Предел,

 ( bagof( B1/C, ( после( В, В1, С), not принадлежит( В1, П)),

   Преемники), !,

 преемспис( G, Преемники, ДД),

 опт_f( ДД, F1),

 расширить( П, д( В, F1/G, ДД), Предел, Дер1,

  ЕстьРеш, Реш);

 ЕстьРеш = никогда).     % Нет преемников - тупик

расширить( П, д( В, F/G, [Д | ДД]), Предел, Дер1,

 ЕстьРеш, Реш) :-