Лекция: Large(TT,Solv).

3.3. ЭВРИСТИЧЕСКИЙ ПОИСК: ПОИСК С ПРЕДПОЧТЕНИЕМ

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

Будем предполагать, что для графа состояний определена функция стоимости его дуг и введем функция s(a,b) равную стоимости перемещения из вершины а в вершину b. Введем эвристическую функцию f(b) равная «сложности достижения» вершины b. В соответствии с данным определением эвристической функции, из всех возможных узлов наиболее предпочтительным является тот, у которого значение эвристической функции принимает минимальное значение.

Сформируем функцию f(n) таким образом, что бы она оценивала стоимость наилучшего пути решения от начального узла до целевого, при прохождении пути через узел n. Пусть такой путь существует и t – целевая вершина, для которой этот путь минимален. Тогда оценку f(n) можно представить как сумму:

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

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

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

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

На рис. 1.4. приведен пример поведения конкурирующих процессов. Здесь представлена карта маршрутов перемещения из пункта s в целевой пункт t. Оценка стоимости остатка маршрута из пункта X до цели выполняется «вычислением» расстояния расст(X,t) прямой «видимости» от X до t. Таким образом формируем оценочную функцию:

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

Рис.1.4. Поиск кратчайшего маршрута из s в t.

а) Карта со связями между пунктами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t.

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

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

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

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

Поскольку f(c)>f(e), процесс 2 переходит к, а процесс 1 ждет. В пункте f имеем:

f(f)= 7+4=11;

f(c)=10,

f(c)<f(f)

поэтому II процесс предает управление I-у процессу, и движение продолжается до пункта d, так как f(d)=12>11. В этом пункте вновь активизируется процесс 2, который и завершает путь до цели t.

В программе множество деревьев-кандидатов представлены в виде дерева. Дерево изображается в программе как терм, имеющий одну из форм:

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

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

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

.

Пояснения к программе.

Пояснения к некоторым предикатам.

Т=tr(B,F/G,[T|TT]) – дерево Т имеет поддеревья. Расширению подвергается наиболее перспективное дерево Т. В качестве ограничения этому дереву выдается не Extr, а некоторое, возможно, меньшее значение Extr1, зависящее от f-оценок других конкурирующих поддеревьев ТТ. Так гарантируется, что растущее дерево – это всегда перспективное дерево. После расширения самого перспективного кандидата процедура (предикат) continue в зависимости от типа результата либо выдает результат, если найдено решение, либо продолжает процесс расширения.

Т=l(B,F/G) – порождает всех преемников вершины В вместе со стоимостями дуг, ведущих в них из В.

suc_list– формирует список поддеревьев, соответствующих вершинам-преемникам, а также вычисляет их g- и f-оценки. Полученное дерево подвергается расширению с учетом ограничения Extr. Если преемников нет, то переменной Is_solv придается значение never и в результате лист В из рассмотрения устраняется.

аfter(B,B1,C) – В1 – преемник вершины В; С – стоимость дуги, ведущей из В в В1.

h(B,H) – H – эвристическая оценка стоимости оптимального пути из вершины В в целевую вершину.

Max_f(Fmax) – Fmax – некоторое значение, задаваемое пользователем. Это значение должно быть больше любой возможной f-оценки.

Рассмотрим текст программы поиска с предпочтением (эвристического поиска)

evrpoisk(Start,Solve):-

max_f(Fmax), % Fmax > любой f-оценки

propag([],l(Start,0/0),Fmax,_,yes,Solve).

propag(P,l(B,_),_,_,yes,[B|P]):-

goal(B). % рассматриваемый лист – цель поиска.

propag(P,l(B,F/G),Extr,Tree1,Is_solv,Solve):-

F=<Extr, % получение дерева из приемников листа

bagof(B1/C,(after(B,B1,C),not(member(B1,P))),Successers),

!,suc_list(G,Successers,TT),