Ab-отсечения

Заменяем на 0

Вывод: Проверка стоимости туров нижними границами Н_i позволяет исключать из рассмотрения большое число ветвей графа, для которых было выявлено, что Н_i>min.

Алгоритм ветвей и границ должен оптимизировать точное решение.

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

Первый игрок ставит цель максимизировать свой выигрыш на каждом ходе, а второй – минимизировать свой проигрыш. Дерево решений будет строиться на основе двух стратегий: максимума (max) и минимума (min).

Пример 1:

Игра «Крестики-нолики».

Для нее можно построить полное дерево решений, однако можно не рассматривать множество «плохих» решений и отсекать «плохие» ветви.

Для определения стратегии и значений узлов дерева в этой игре используются следующие варианты:

+1 выигрыш первый игрок.

-1 выигрыш второй игрок.

0 ничья.

Листьями являются полные решения, а узлами – промежуточные состояния.

Зная значение узла, в соответствии с выбранной стратегией либо рассматривают всех потомков этого узла, либо отсекают.

Стратегии max соответствует N-четное, а стратегии min – N-нечетное, где N – порядок узлов дерева.

На первом уровне имеется 9 вариантов возможных комбинаций (поскольку все клетки игрового поля пусты), на втором уровне – 8 возможных комбинаций и т. д. Всего получается 9!=362880 листьев. Из этого числа возможных решений множество листьев дублируют друг друга.

Сложность алгоритма полного перебора O(N!).

Общее правило отсечения узлов связано с понятиями конечных и ориентировочных значений узлов. Конечное значение – это выигрыш в данной ситуации. Ориентировочное значение – это верхний предел значений узлов, находящийся в режиме min (b-значения), или это нижний предел значений узлов в режиме max (a-значения).

b-значения характеризуют стратегию наихудшей обороны, a-значения характеризуют стратегию наихудшей атаки.

Правила определения конечных и ориентировочных значений:

1) Если уже рассмотрены или отсечены все потомки некоторого узла N, то – сделать ориентировочное значение этого узла конечным значением.

2) Если ориентировочное значение узла N в режиме max равно V1, а значение одного из его потомков равно V2, то – установить ориентировочное значение узла N как функцию max(V1, V2). Если узел N в режиме min имеет значение Р1, а его потомок – значение Р2, то – установить ориентировочное значение узла N как функцию min(P1, P2).

3) Если некоторый узел P в режиме min является потомком узла Q в режиме max и ориентировочные значения их равны V1 и V2 соответственно, причем V1>V2, то можно отсечь всех нерассмотренных потомков узла Р.

Можно отсечь нерассмотренных потомков узла Q в режиме max со значением V1, предка узла Р в режиме min, имеющего ориентировочное значение V3, если выполняется условие V3<V1.

Пример 2:

b_N < a_N+1

Если существует потомок узла N с b-значением в режиме min, расположенный на два уровня ниже, имеющий большее значение, чем значение узла N, то можно отсечь соответствующую ветвь потомков узла N (b-отсечение).

Если существует потомок для узла N с a-значением в режиме max, расположенный на два уровня ниже и a_N > b_N+1, т. е. его значение может только уменьшить значение предка, то эту ветвь можно отсечь (a-отсечение).

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

Дата добавления: 2014-01-07