ТИПИС

3. Очередное множество Si представить как Si = Si1 Si2, где

si Si1 MS и sj Si2 MS, где MS – память оригинальных состояний,

MS = (siо, sjt, S1, …, Si-12).

4.Если si Si2 sjt St, то задача решена, иначе – п. 5.

5.Очередное множество Si2 занести в память MS и перейти к п. 2 для множества Si2.

Таким образом, в памяти формируется множество MS = (siо, sjt, S1,… Si-12, Si2, Si+12,…Sn2) оригинальных состояний. Это множество представляет собой модель графа в виде явно несвязных фронтов оригинальных состояний. Модель графа в виде MS предотвращает циклы и тем самым определяет направление следующей генерации. Количество входящих в MS подмножеств Si2 представляет собой минимальное количество итераций (расстояние) от siо до sjt.

Метод ветвей и границ предназначен:

1) для поиска расстояния Hi до ближайшего из заданных целевых со-

стояний sti St;

2) для определения возможно минимального расстояния Hmin до ближайшего целевого состояния.

Поэтому обычно в методе ветвей и границ последовательно выполняются две задачи:

1)определение граничной глубины (количества итераций) поиска в пространстве состояний;

2)поиск минимального расстояния (ветви), ведущего к целевому состоянию.

Значимость первой задачи зависит от выбранного способа генерации,

авторой – от ресурса ПС, отведенного на поиск.

Метод ветвей и границ используется в следующих условиях, удовлетворяющих решению: St 1 и sti St. Таким образом, в данном методе целесообразно использовать генерацию, определяемую отношением множеств S и St . Обычно метод применяют в условиях, когда отношение пространства поиска и целевых состояний стремится к единице. Поэтому в методе применяют секторные способы генерации.

Схема поиска методом ветвей и границ представлена на рис. 2.9.

Рассмотрим алгоритм поиска методом ветвей и границ с генерацией

вглубину применительно к решению первой задачи:

1.Выполнить поиск, используя генерацию в глубину. При этом со-

хранять в памяти число проведенных итераций поиска H от начального состояния so.

2.Если выполняется условие si Si, sjt St , то первая задача решена и следует перейти к п. 3, иначе – п. 1.

Впункте 2 (при положительном исходе) определена граничная

глубина поиска, представленная в памяти Hi . В решении второй задачи используется такая величина: Hi+1 = Hi –1. Таким образом, сле-

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

3. Осуществлять поиск (п. 1 и 2) до получения ближайшего целевого состояния, для которого Hi будет минимальным.

Последнее сгенерированное Hi будет являться относительно минимальным расстоянием до найденного, возможно ближайшего состояния si St.

Так в данном методе формируется величина Hmin ≤ Hi – 1, которая представляет собой граничную глубину поиска и минимальное расстояние до возможно ближайшего целевого состояния.

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

N

MS = Si .

i 1

В этом случае обычно MS будет больше, чем Si – величина фронта на текущей итерации при поиске в ширину на i-й итерации.

Так, управление направлением генерации на дереве оригинальных состояний в действительности требует большего ресурса на процедуру

проверки всего множества MS , чем для слепых методов проверка состояний очередного текущего фронта. Однако при поиске на графе в условии,

что Ср стремится к бесконечности, это отношение становится обратным.

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

Сравнение осуществляется:

1)на неориентированном кольце, образованном оригинальными состояниями;

2)на дереве оригинальных состояний (у всякого «родителя» в кото-

ром по m «дочек», где m 1);

3) на графе, организация которого соответствует задаче «Перестановка», представленной в прил. Б, при заданном количестве элементов в состояниях равным n, где n 2.

Решением задачи являются заполненные количеством состояний ячейки табл. 2.2 для генерации в ширину и множества MS в методе Мура.

В табл. 2.2 в качестве примера представлено сравнение генерации в ширину и мощности MS в методе Мура при поиске на кольце, состоящем из оригинальных состояний. Дополнительно анализ мощности фронтов и MS может быть проведен и для остальных секторных генераций. Результат может быть представлен в форме табл. 2.2.

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

ставляющей преимущество методов в раскрытии особенности организации пространства поиска.

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

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

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

ление оптимального пути.

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

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

Hi

С генерацией по лучу

6000

5000

С генерацией параллельным методом

4000

С генерацией в глубину

3000

С генерацией в ширину

2000

1000

Рис. 2.10. График зависимости количества итераций H от количества знаков

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

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

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

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

В общем случае алгоритм поиска методом ветвей и границ с памятью и генерацией в глубину будет выглядеть следующим образом:

1. Выполнить поиск, используя генерацию в глубину. При этом сохранять в памяти оригинальные состояния MS и число проведенных итераций поиска H от начального состояния so.

2. Если выполняется условие si Si2 sjt St, то первая задача решена, и следует перейти к п. 3, иначе – п. 1.

В пункте 2 не только определяется граничная глубина поиска, пред-

ставленная в памяти: Hi , но и сокращается пространство поиска за счет применения MS.

3. Осуществлять поиск (п. 1 и 2) до получения ближайшего целевого состояния, для которого Hi будет минимальным. Причем Hi будет не относительно минимальным, как это было бы в результате применения традиционного метода ветвей и границ, а действительно минимальным.

На рис. 2.11 представлена схема поиска методом ветвей и границ с памятью.

Граница для нового поиска Hi+1

Hi+1 = Hi –1

Рис. 2.11. Схема поиска методом ветвей и границ с памятью

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

Вариант объединения простейших эвристических методов поиска в комбинированный алгоритм показан на рис. 2.12.

Начало

Ввод данных

Алгоритм поиска ветвей и границ (с генерацией в глубину)

Нет

Условия перехода

Алгоритм поиска Мура (с генерацией в ширину)

Нет

Условия перехода

Алгоритм поиска ветвей и границ (с генерацией по лучу)

Вывод данных

Конец

Рис. 2.12. Комбинированный алгоритм поиска

На первом этапе применяется метод ветвей и границ с генерацией в глубину (генерация с относительно узким фронтом). Это позволяет снизить необходимый ресурс ПС за счет формирования граничной глубины.

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

Далее возникает задача остановки поиска методом ветвей и границ. Существуют множество способов остановки поиска [15–23]. Одним из способов может быть использование показателей формулы Байеса для оценки вероятности события гипотезы в определенных условиях. Такое ограничение используется в ряде экспертных систем, в частности ЭС PROSPECTOR. Следует отметить, что в основе каждого способа используется оценочная эвристическая информация.

Так, при выполнении условия, что некоторое sj St является ближайшей к so, осуществляется переход к следующему этапу поиска. В общем случае первое условие может иметь следующий вид:

S* St* = k,

где k – коэффициент, представляющий мощность множества

St* оставшихся целевых состояний в ограниченном Hmin пространстве поиска S* .

Коэффициент k равен единице при условии, что S* = St* , и равенS* в случае St* = 1. Напомним, что метод Мура обычно применяется в условии, когда существует только одно sj St. Поэтому, чем ближе k по значению к S* , тем более целесообразно начать применение метода Мура на втором этапе комбинированного алгоритма.

На втором этапе происходит проверка границы Hmin методом Мура (генерация с максимально широким фронтом). При этом расстояние, соот-

ветствующее MS до первого найденного целевого состояния, будет ми-

нимальным, т. е. MS Hmin .

С помощью генераций в ширину и глубину, используемых в простейших эвристических методах поиска, можно определить минимальное расстояние MS или Hmin до заданного состояния. Использование в дальнейшем генерации по лучу в простейших эвристических методах поиска позволит выделить кратчайший путь как цепочку операторов Li = {f1, f2, …, fn} (результат решения третьей задачи поиска). Для этого в комбинированном алгоритме (рис. 2.12) предусмотрен третий этап поиска.

После определения расстояния до ближайшего целевого состояния для выделения кратчайшего пути можно использовать поиск методом вет-

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

третьего этапа будут получены цепочки или цепочка Hmin ={f1, f2, …, fn}, т. е. путь или пути, соответствующие Li. Выделенные таким образом в MS пути

будут по определению кратчайшими.

Однако выделение оптимального пути предусматривает использование в методах поиска априорной информации, представленной в явном виде. Например, в виде оценочной функции видовых признаков состояний пространства поиска. Таким образом, решение третьей задачи (выделение оптимального пути) осуществляется на основе анализа видовых признаков состояний.

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

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

Управление генерацией на основе апостериорной информации может быть выполнено следующим образом:

1)исключением повторений, как это реализовано в методе Мура;

2)ограничением числа итераций, как это реализовано в методе ветвей и границ.

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

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

Вследующем параграфе будут рассмотрены особенности планирования на основе априорной информации.