Метод ветвей и границ

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

Для применения метода ветвей и границ

cost(a₁, a₂, …, a_k-1) £ cost(a₁, a₂, …, a_k-1, a_k)

Когда стоимость обладает этим свойством, мы можем отбросить частичное решение (a₁, a₂, …, a_k), если его стоимость больше или равна стоимости ранее вычисленных решений. Это ограничение легко включается в общий алгоритм поиска с возвращением, как видно из следующего алгоритма 4.4. В большинстве случаев функция стоимо­сти неотрицательная и даже удовлетворяет более сильному требо­ванию

[последнее сохраняемое решение есть решение с наименьшей стоимостью]

Алгоритм 4.4. Общий метод ветвей и границ.

Задача коммивояжера

Задача коммивояжера является типичной задачей оптимизации, которую можно решить с помощью метода ветвей и границ. В этой задаче коммивояжер должен посетить n городов и возвратиться в исходный пункт, при этом требуется минимизировать общую стои­мость путешествия. Переезжая из города i в город j он терпит убы­ток С_ij. Например, если матрица стоимостей равна

то стоимость пути 1—2—5—7—3—6—4—1 равна 277, в то время как стоимость оптимального пути, скажем 1—4—6—7—3—5—2—1, равна только 126.

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

Эта проверка устраняет просмотр некоторых частей дерева, но на самом деле она достаточно слабая, допускающая

Почти оптимальные решения следует находить на раннем этапе поиска.

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

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

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

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

может быть преобразована вычитанием 3, 4, 16, 7, 25, 3 и 26 из строк 1—7 соответственно и затем вычитанием 7, 1 и 4 из столбцов 3, 4 и 7 соответственно, в результате чего преобразо­ванная матрица будет равна

Поскольку суммарное вычитаемое равно 96, 96 и будет нижней границей стоимости любого решения. Тогда первоначально мы име­ем корень бинарного дерева и соответствующую нижнюю границу:

Как этот узел распадается на поддеревья?

Предположим, что мы выбираем дугу 4—6, по которой происходит разбиение дерева. Правое поддерево будет содержать все решения, которые исключают дугу 4—6; зная, что дуга 4—6 исключена, мы можем изменить мат­рицу стоимостей, положив С_4,6=¥. Тогда у получившейся матрицы из четвертой строки можно вычесть 32, и поэтому правое поддерево имеет нижнюю границу 96+32== 128.

Левое поддерево будет содер­жать все решения, которые включают дугу 4—6, и поэтому четвер­тая строка и шестой столбец матрицы стоимостей должны быть уда­лены, поскольку теперь мы никогда не можем идти из 4 куда-нибудь еще и не придем в 6 откуда-либо еще.

В результате мы будем иметь матрицу стоимостей на единицу меньшего размера. Далее, посколь­ку все решения в этом поддереве используют дугу 4—6, дуга 6— 4 больше не используется, и нужно положить С_6,4=¥.

Наконец, мы можем теперь вычесть 3 из четвертой строки результирующей мат­рицы (i=5), что дает левому поддереву нижнюю границу 96 + 3 = 99. Бинарное дерево имеет вид, показанный на рис. 4.6.

Рис. 4.6. Расщепление корня бинарного дерева

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

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

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

Применяя метод ветвей и границ к приведенной выше в качестве примера матрице стоимостей, мы замечаем некоторую сложность. Первое включенное ребро есть 4—6, следующее — 3—5 и третье — 2—1 (см. самый левый путь из корня дерева на рис. 4.7). В этом узле нижняя граница равна 112, а преобразованная матрица стои­мостей имеет вид:

Нуль, который при замене на бесконечность позволяет вычесть наибольшее количество из соответствующей строки и столбца, на­ходится на месте i==1, j==4. Поэтому мы расщепляем данный узел, используя ребро 1—4. В левом поддереве мы получаем нижнюю оценку 126 и преобразованную матрицу стоимостей

Теперь в соответствии с описанным нами процессом мы хотим пре­дотвратить использование ребра 4—1, но матрица стоимостей не имеет элемента, соответствующего i =4, j =1. Что делать?

Ответ мы найдем; рассмотрев цель предотвращения использова­ния ребра 4—1. Эта цель состоит в том, чтобы в процессе обхода предотвращать посещение города, в котором мы уже побывали, до тех пор пока по самому последнему ребру не вернемся в исходный город. В нашем случае частичный обход, построенный до сих пор, состоит из пути 2—1—4—6 и ребра 3—5; ясно, что мы должны пред­отвратить использование ребра 6—2, поэтому заменим преобразо­ванную матрицу стоимостей на следующую:

И вообще, если ребро, добавленное к частичному обходу, есть ребро, идущее из i_u в j₁, и частичный обход содержит пути i₁ — i₂ —....— i_u и j₁— j₂—... — j_v, то нужно предотвратить использование ребра  j₁ — i₁.

Применение этого метода к матрице стоимостей, приведенной выше, в качестве примера дает бинарное дерево, показанное на рис. 4.7.

Рис. 4.7. Полное дерево поиска для примера задачи коммивояжера

Заметим, что первое найденное решение оптимально; мы не можем рассчитывать, что это же происходит в общем случае. В данном примере исследуется только 27 узлов; если использовать «очевидную» специализацию общего алгоритма ветвей и границ, то потребуется исследовать 559 узлов. На основе экспериментальных данных можно сделать предположение, что для случайной n´n-матрицы расстояний число исследуемых узлов равно О(1,26ⁿ).

Метод a-b-отсечений

Теоретическое обоснование метода

Введение

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

История

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

Мак-Карти думал о подобном методе в 1965 г. во время Дартмутской летней исследовательской конференции по искусственному интеллекту, где Бернстайн рассказал об одной из самых ранних шахматных программ, в которой не использовались никакие отсечения. Мак-Карти "критиковал за это программу, но не убедил Бернстайна. В то время спецификации алгоритма подготовлены не были". Очень вероятно, что замечания Мак-Карти, сделанные на этой конференции, привели к тому, что в конце 50-х гг. альфа-бета отсечения стали использовать в шахматных программах.

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

Мак-Карти ввел идентификаторы alpha и beta в своей первой программе на LISP'е, реализующей этот метод. Его программа работала даже более изощренно, чем вышеописанный метод, пос­кольку он предполагал существование двух функций "оптимистическая оценка (p)" и "пессимистическая оценка (p)", которые доставляли верхнюю и нижнюю границы оценки позиции. Программу Мак-Карти, выполняющую те же действия, что приведенная выше процедура F2, можно представить в следующем виде:

if optimistic value(p) <= alpha

  then F2 := alpha

  else if pessimistic value(p) >= beta

    then F2 := beta

    else begin <the above body of procedure F2> end.

Из-за этих добавлений Мак-Карти считал альфа-бета отсечения (возможно, дающим ошибку) эвристическим приемом, не осознав, что точное значение оценки получается, когда для всех p

optimistic value(p) = +

и

pessimistic value(p) = -

Он подарил открытие этого факта Харту и Эдвардсу, которые в 1961 году подготовили по этому поводу отчет. В этом неопубликованном отчете они приводят примеры работы общего метода, в том числе, нижних отсечений. Однако (как это было принято в 1961 г.), в нем нет ни обоснования метода, ни указания условий, при которых он работает.

Первая публикация с описанием альфа-бета отсечений появилась на русском языке в 1963 г. совершенно независимо от работ американцев. Брудно, один из разработчиков первых версий русской шахматной программы (имеется в виду программа, которую позже назвали романтическим именем КАИССА в честь музы шахмат - прим. перев.), предложил алгоритм, совпадающий с альфа-бета методом, и дал - довольно-таки сложное - доказательство его правильности.

Полное описание альфа-бета отсечений появилось в "западной" литературе по вычислениям и компьютерам в 1968 г. в статье Слейгла и Бурского о стратегиях доказательства теорем, однако, это описание страдало нечеткостью и не содержало обсуждения нижних отсечений. Таким образом, можно утверждать, что первое четкое изложение метода на английском языке появилось в 1969 г. в статьях Слейгла и Диксона и Самуэля ; в обеих статьях явно упоминается возможность нижних отсечений и обсуждение идеи включает необходимые детали.

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

Очень хорошо метод описан в книгах Нильсона и Слейгла, однако, они представляют метод "в прозе", а не в более легкой для понимания алгоритмической форме. Альфа-бета отсечения стали "широко известными", однако, насколько известно авторам, лишь в двух публикациях процедура описана на алгоритмическом языке. На самом деле, в первой из них, Уэллс приводит не полную альфа-бета процедуру, а нечто даже более слабое, чем процедура F1. (Его алгоритм не только не производит нижние отсечения, но и верхние отсечения производит лишь при выполнении строгого неравенства.) Другая версия алгоритма, принадлежащая Далу и Белснису, появилась в вышедшем на норвежском языке учебнике по структурам данных; однако, альфа-бета метод представлен в ней с использованием параметров-меток, так что доказательство правильности становится достаточно трудным. В другом недавнем учебнике содержится неформальное описание того, что там названо "альфа-бета отсечениями", но снова приведен лишь метод, реализуемый процедурой F1; по-видимому, многие не знают, что альфа-бета процедура способна производить нижние отсечения.

Игры и оценки позиций

Игры двух лиц, а только с ними мы и имеем здесь дело, обычно описывают множеством "позиций" и совокупностью правил перехода из одной позиции в другую, причем предполагают, что игроки ходят по очереди. Будем считать, что правилами разрешены лишь конечные последовательности позиций и что в каждой позиции имеется лишь конечное число разрешенных ходов. Тогда для каждой позиции p найдется число N(p) такое, что никакая игра, начавшаяся в p, не может продолжаться более N(p) ходов - это следует из "леммы о бесконечности" .

Терминальными называются позиции, из которых нет разрешенных ходов. На каждой из них определена целочисленная функция f(p), задающая выигрыш того из игроков, которому принадлежит ход в этой позиции; выигрыш второго игрока считается равным -f(p).

Если из позиции p имеется d разрешенных ходов p1,...,pd, возникает проблема выбора лучшего из них. Будем называть ход наилучшим, если по окончании игры он приносит наибольший возможный выигрыш при условии, что противник выбирает ходы, наилучшие для него (в том же смысле). Пусть F(p) есть наибольший выигрыш, достижимый в позиции p игроком, которому принадлежит очередь хода, против оптимальной защиты. Т.к. после хода в позицию pi выигрыш этого игрока равен -F(pi), имеем

(1)

Эта формула позволяет индуктивно определить F(p) для каждой позиции p.

В большинстве работы по теории игр используется чуть иная формулировка; в ней игроки называются Max и Min и изложение ведется с "точки зрения" игрока Max. Таким образом, если p есть терминальная позиция с ходом Max, его выигрыш равен, как и раньше f(p), если же в терминальной позиции p ходить должен Min, то его выигрыш равен

g(p) = -f(p).                                                                  (2)

Max пытается максимизировать свой конечный выигрыш, а Min старается минимизировать его. Соотношению (1) при этом соответствуют две функции, именно

(1')

которая задает максимальный гарантированный выигрыш игрока Max в позиции p, и 

(1'')

которая равна оптимуму, достижимому для игрока Min. Как и раньше, здесь предполагается, что p1,...,pd есть разрешенные в позиции p ходы. Индукцией по числу ходов легко показать, что функции, определяемые соотношениями (1) и (3), совпадают и что для всех p

G(p) = -F(p).                                                                 (5)

Таким образом, оба подхода эквивалентны.

Т.к. нам обычно легче оценивать позиции с точки зрения одного какого-то игрока, иногда удобнее использовать "минимаксный" подход (3) и (4), а не рассуждать в "плюс-минус-максимальных" терминах соотношения (1). С другой стороны, соотношение (1) предпочтительнее, когда мы хотим доказать что-нибудь, - при этом нам не приходится исследовать два (или больше - по числу игроков) разных случая.

Функция F(p) равна тому максимуму, который гарантирован, если оба игрока действуют оптимально. Следует, однако, заметить, что она отражает результаты весьма осторожной стратегии, которая не обязательно хороша против плохих игроков или игроков, действующих согласно другому принципу оптимальности. Пусть, например, имеются два хода в позиции p1 и p2, причем p1 гарантирует ничью (выигрыш 0) и не дает возможности выиграть, в то время, как p2 дает возможность выиграть, если противник просмотрит очень тонкий выигрывающий ход. В такой ситуации мы можем предпочесть рискованный ход в p2, если только мы не уверены в том, что наш противник всемогущ и всезнающ. Очень возможно, что люди выигрывают у шахматных программ таким именно образом.

Сущность метода

Рассмотрим основные понятия.

Например, на рис. 1 показаны фрагменты дерева игры в крестики-нолики, где первым ставится крестик (´); на дереве показаны только неэквивалентные (с точностью до вращения и/или отражения) сыновья узла.

Каждый лист дерева игры представляет собой возможное оконча­ние игры; в случае игры в крестики и нолики окончанием может быть победа крестиков, победа ноликов или ничья. Нас интересует оценка дерева игры с позиций первого игрока; каждый лист помечается значе­нием выигрыша первого игрока: +1 в случае победы. —1 в случае поражения и 0 при ничьей.

Значения других узлов опреде­ляются значениями их сыновей. Для узла N с сыновьями N₁, N₂, ..., N_k значение V(N) имеет вид:

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

Мы могли бы применить просто очевидную технику возвращения для оценки всех уз­лов дерева и определить значение в корне. Од­нако существует лучший метод, называемый a-b-отсечением, который использует идею метода ветвей и границ для обрывания поддеревьев де­рева игры.

Заметим, что, как только узел оценен, становится кое-что известно о значении, которое будет присвоено его отцу.

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

Такая нижняя граница уровня, в котором вычисляется максимум, называется a-значе­нием.

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

В примере на рис.2, как только узлу d присваивается значение 3, сразу же получается b-значение 3 для узла m; и мы получаем, что значение V(N) в m будет не больше чем 3.

Располагая такой информацией, мы рассуждаем следующим образом. Если можно по­казать, что значение любого другого потомка узла m будет боль­ше 3, мы можем спокойно игно­рировать оставшуюся часть дерева, расположенную ниже этого потомка.

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

На уровне, в котором вычисляется максимум, имеем сходную ситуацию. Возвращаясь снова к примеру и обнаружив, что для узла m значение равно 3, мы имеем для корня дерева a-значение 3, так что, если можно показать, что узел z имеет значение, меньшее 3, мы можем иг­норировать все, что расположено ниже его. Поэтому после уста­новления значения 2 в узле q, мы обрываем оставшуюся часть де­рева, находящуюся ниже узла z, так как оценка не будет больше влиять на окончательное значение корня. Эта процедура назы­вается a-отсечением.

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