Лекция 9

 

 

 

Поиск с предпочтением: Эвристический поиск.

 

 

Cодержание

1 Введение.

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

 

1. Введение

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

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

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

Рис 1

Рис 1 Построение эвристической оценки f(n) стоимости самого дешевого пути из s в t, проходящего через n.
f(n)=g(n)+h(n)

Мы будем в дальнейшем предполагать, что для дуг пространства состояний определена функция стоимости c(n,n') - стоимость перехода из вершины n к вершине-преемнику n'.
Пусть f - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) "трудности" этой вершины. Тогда наиболее перспективной вершиной-кандинатом следует считать вершину, для которой f принимает минимальное значение. Мы будем использовать здесь функцию f специального вида, приводящую к хорошо известному A* - алгоритму. Функция f(n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n. Давайте предположим, что такой путь существует и что t - это целевая вершина, для которой этот путь минимален. Тогда оценку f(n) можно представить в виде суммы из двух слагаемых (рис. 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 - оценки изменятся и в результате какя-нибудь другая альтернатива станет перспективной. Тогда производится переключение активности на эту альтернативу.

Рис 2

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

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

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

f(c)=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.

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

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

 

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

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

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

f(T)=minf(mi)

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

Так же, как и в случае поиска в ширину, ключевую роль играет процедура расширить , имеющая 6 аргументов:

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

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

эвропоиск(Старт,Решение):-
  макс_f(Fмакс).
  расширить([],л(Старт,0.0),Fмакс,_,да,Решение).
 
расширить(П,л(В,_),_,_,да,[B|П]):-
  цель(В).
 
расширить(П,л(В,F/G),Предел,Дер1,ЕстьРеш,Реш):-
  F < =Предел,
  (bagof(B1/C,(после(В,В1,С),not принадлежит(В1,П}),
  преемспис(G,Преемники),!,преемспис(G,Преемники, ДД),
  опт_f(ДД,F1).
 
расширить(П,д(В,F/G),[Д|ДД]),Предел,Дер1,ЕстьРеш,Реш):-    
  F < =Предел,
  опт_f(ДД,OF),мин(Предел,OF,Предел1),
  расширить([B|П],Д.Предел1,Д1,ЕстьРеш1,Реш),
  продолжить(П,д(В,F/G,[Д|ДД]),Предел,Дер1,ЕстьРеш1,ЕстьРеш,Реш).
    
расширить(_,д(_,_,[]),_,_,никогда,_):-!.
   % тупиковое дерево - нет решений
 
расширить(_,Дер,Предел,Дер,нет,_):-    
  f(Дер,F),F > Предел. % рост остановлен
 
продолжить(_,_,_,_,да,да,Реш).
 
продолжить(П,д(В,F/G,[Д1|ДД]),Предел,Дер1,ЕстьРеш1,ЕстьРеш,Реш):-
  (ЕстьРеш1=нет,встав(Д1,ДД,НДД);
   ЕстьРеш1=никогда,НДД=ДД),
   опт_f(НДД,F1),
   расширить(П,д(В,F1/G,НДД),Предел,Дер1,ЕстьРеш,Реш).
 
преемспис(_,[],[]).
 
преемспис(G0,[B/C|BB],ДД):-
  G is G0+C,
  h(B,H),       % Эвристика h(B)
  F is G+H,
  преемспис(G0,BB,ДД1),
  встав(л[B,F/G),ДД1,ДД).

рис. 4
Отношение расширить: расширение дерева Дер до тех пор, пока f-оценка не превзойдет Предел, приводит к дереву Дер1.

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

Предложение, относящееся к случаю

Дер = л(В, F/G)

порождает всех преемников вершины В вместе со стоимостями дуг, ведущих в них из В. Процедура преемспис формирует список поддеревьев, соответствующих вершинам-преемникам, а также вычисляет их g- и f-оценки, как показано на рис. 5. Затем полученное таким образом дерево подвергается расширению с учетом ограничения Предел. Если преемников нет, то переменной ЕстьРеш придается значение "никогда" и в результате лист В покидается навсегда.

     Другие отношения:
 
  после(В,В1,С)   В1 - преемник вершины В;
                  С - стоимость дуги, ведущей из В в В1.
 
  b(В,H)          H - эристическая оценка стоимости оптимального
                      пути из вершины В в целевую вершину.
     
  макс_f(Fмакс)   Fмакс - некоторое значение, задаваемое пользователем,
                        про которое известно, что оно больше любой 
                        возможной f-оценки.

 

Мы реализовали один из вариантов эвристического алгоритма, известного в литературе как А*-алгоритм. Приведем один важный результат, полученный в результате математического анализа А*-алгоритма:

рис. 5
Связь между g-оценкой вершины B и f- и g-оценками ее "детей" в прстранстве состояний.

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

   h(n) < = h*(n) 

Для всех вершин n пространства состояний.

Этот результат имеет огромное практическое значение. Даже если нам не известно точное значение h*, нам достаточно найти какую-либо нижнюю грань h* и использовать ее в качестве h в А*-алгоритме - оптимальность решения будет гарантирована.

Существует тривиальная нижняя грань, а именно: h(n)=0 для всех вершин n пространства состояний.
И при этом значении h допустимость гарантирована. Однако такая оценка не имеет никакой эвристической силы и ничем не помогает поиску. А*-алгоритм при h=0 ведет себя аналогично поиску в ширину, если положить с(n,n')=1 для всех дуг (n,n') пространства состояний. Отсутствие эвристической силы оценки приводит к большой комбинаторной сложности алгоритма. Поэтому хотелось бы иметь такую оцунку h, которая была бы нижней гранью h* (чтобы обеспечить допустимость) и, кроме того, была бы как можно ближе к h* (чтобы обеспечить эффективность). В идеальном случае, если бы нам была известна сама точная оценка h*, мы бы ее использовали: А*-алгоритм, использующийся h*, находит оптимальное решение сразу, без единого возврата.

size=1 width="75%" noshade color=gray align=left>

(c) M.N.Morozov, 1999.

информация

проекты

публикации

материалы

друзья

студенты

 

связи

 

 

Hosted by uCoz