Эвристики

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

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

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

Поиск в других деревьях решений

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

=======195

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

Метод ветвей и границ (branch and bound) является одним из методов отсечения (pruning) ветвей в дереве решений, чтобы не было необходимо рассматривать все ветви дерева. Общий подход при этом состоит в том, чтобы отслеживать границы уже обнаруженных и возможных решений. Если в какой‑то точке наилучшее из уже найденных решений лучше, чем наилучшее возможное решение в нижних ветвях, то можно игнорировать все пути вниз от узла.

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

Задачи такого типа называются задачей формирования портфеля (knapsack problem). Имеется несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 миллионов долларов). Каждая из позиций имеет стоимость (деньги) и цену (тоже деньги). Необходимо найти набор позиций, который помещается в портфель и имеет максимально возможную цену.

Эту задачу можно смоделировать при помощи дерева решений. Каждый узел дерева соответствует определенной комбинации позиций в портфеле. Каждая ветвь соответствует принятию решения о том, чтобы удалить позицию из портфеля или добавить ее в него. Левая ветвь первого узла соответствует первому вложению. На рис. 8.6 показано дерево решений для четырех возможных инвестиций.

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

Размер этого дерева очень быстро растет с увеличением числа инвестиций. Для 10 возможных инвестиций, в дереве будет находиться 2¹⁰ = 1024 листа. Для 20 инвестиций, в дереве будет уже более миллиона листьев. Можно провести полный поиск по такому дереву, но при дальнейшем увеличении числа возможных инвестиций размер дерева станет очень большим.

@Рис. 8.6. Дерево решений для инвестиций

=======196

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

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

В качестве конкретного примера, предположим, что имеются инвестиции, приведенные в табл. 8.1. На рис. 8.6 показано соответствующее дерево решений. Некоторые из этих инвестиционных пакетов нарушают граничные условия задачи. Например, самый левый путь привел бы к вложению 178 миллионов долларов во все четыре возможных инвестиции.

Предположим, что мы начали поиск в дереве, изображенном на рис. 8.6 и обнаружили, что можно потратить 97 миллионов долларов на позиции A и B, получив 23 миллиона прибыли. Это соответствует четвертому листу слева на рис. 8.6.

При продолжении поиска в дереве, можно дойти до второго слева узла B на рис. 8.6. Это соответствует инвестиционному пакету, который включает позицию A, не включает позицию B, и может включать или не включать позиции C и D. В этой точке пакет уже стоит 45 миллионов долларов за счет позиции A, и приносит 10 миллионов прибыли.

Оставшиеся позиции C и D вместе взятые могут повысить прибыль еще на 12 миллионов. Текущее решение приносит 10 миллионов прибыли, поэтому наилучшее возможное решение ниже этого узла принесет не больше 11 миллионов прибыли. Это меньше, чем доход в 23 миллиона для уже найденного решения, поэтому нет смысла продолжать поиск вниз по этому пути.

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

@Таблица 8.1. Возможные инвестиции

======197

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

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

' Полная нераспределенная прибыль.

Private unassigned_profit As Integer

Public NumItems As Integer

Public MaxItem As Integer

Global Const OPTION_EXHAUSTIVE_SEARCH = 0

Global Const OPTION_BRANCH_AND_BOUND = 1

Type Item

Cost As Integer

Profit As Integer

End Type

Global Items() As Item

Global NodesVisited As Long

Global ToSpend As Integer

Global best_cost As Integer

Global best_profit As Integer

' Равно True для позиций в текущем наилучшем решении.

Public best_solution() As Boolean

' Решение, которое мы проверяем.

Private test_solution() As Boolean

Private test_cost As Integer

Private test_profit As Integer

' Инициализация переменных и начало поиска.

Public Sub Search(search_type As Integer)

Dim i As Integer

' Задание размера массивов решения.

ReDim best_solution(0 To MaxItem)

ReDim test_solution(0 To MaxItem)

' Инициализация - пустой список инвестиций.

NodesVisited = 0

best_profit = 0

best_cost = 0

unassigned_profit = 0

For i = 0 To MaxItem

unassigned_profit = unassigned_profit + Items(i).Profit

Next i

test_profit = 0

test_cost = 0

' Начнем поиск с первой позиции.

BranchAndBound 0

End Sub

' Выполнить поиск методом ветвей и границ начиная с этой позиции.

Public Sub BranchAndBound(item_num As Integer)

Dim i As Integer

NodesVisited = NodesVisited + 1

' Если это лист, то это лучшее решение, чем

' то, которое мы имели раньше, иначе он был бы

' отсечен во время поиска раньше.

If item_num > MaxItem Then

For i = 0 To MaxItem

best_solution(i) = test_solution(i)

best_profit = test_profit

best_cost = test_cost

Next i

Exit Sub

End If

' Иначе перейти по ветви вниз по ветвям потомка.

' Вначале попытаться добавить эту позицию. Убедиться,

' что она не превышает ограничение по цене.

If test_cost + Items(item_num).Cost <= ToSpend Then

' Добавить позицию к тестовому решению.

test_solution(item_num) = True

test_cost = test_cost + Items(item_num).Cost

test_profit = test_profit + Items(item_num).Profit

unassigned_profit = unassigned_profit - Items(item_num).Profit

' Рекурсивная проверка возможного результата.

BranchAndBound item_num + 1

' Удалить позицию из тестового решения.

test_solution(item_num) = False

test_cost = test_cost - Items(item_num).Cost

test_profit = test_profit - Items(item_num).Profit

unassigned_profit = unassigned_profit + Items(item_num).Profit

End If

' Попытаться исключить позицию. Выяснить, принесут ли

' оставшиеся позиции достаточный доход, чтобы

' путь вниз по этой ветви превысил нижний предел.

unassigned_profit = unassigned_profit - Items(item_num).Profit

If test_profit + unassigned_profit > best_profit Then BranchAndBound item_num + 1

unassigned_profit = unassigned_profit + Items(item_num).Profit

End Sub

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

Затем при помощи переключателя внизу формы выберите либо Exhaustive Search (Полный перебор), либо Branch and Bound (Метод ветвей и границ). Когда вы нажмете на кнопку Go (Начать), то программа найдет наилучшее решение при помощи выбранного метода. Затем она выведет на экран это решение, а также число узлов в полном дереве решений и число узлов, которые программа в действительности проверила. На рис. 8.7 показано окно программы BindB после решения задачи портфеля для 20 позиций. Перед тем, как выполнить полный перебор для 20 позиций, попробуйте вначале запустить примеры меньшего размера. На компьютере с процессором Pentium с тактовой частотой 90 МГц поиск решения задачи портфеля для 20 позиций методом полного перебора занял более 30 секунд.

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

@Рис. 8.7. Программа BindB

======200

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

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