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

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

 

=======195

 

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

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

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

Задачи такого типа называются задачей формирования портфеля[RV14] (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. [RV15] Это соответствует инвестиционному пакету, который включает позицию 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.

Эвристики

Иногда даже алгоритм ветвей и границ не может провести полный поиск в дереве. Дерево решений для задачи портфеля с 65 позициями содержит более 7 * 10¹⁹ узлов. Если алгоритм ветвей и границ проверяет только одну десятую процента этих узлов, и если компьютер проверяет миллион узлов в секунду, то для решения этой задачи потребовалось бы более 2 миллионов лет. В задачах, для которых алгоритм ветвей и границ выполняется слишком медленно, можно использовать эвристический подход.

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

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

 

@Таблица 8.2. Число узлов, проверенных при поиске методами полного перебора и ветвей и границ

 

=======201

 

В этом разделе обсуждаются эвристики, которые полезны при решении многих сложных задач. Программа Heur демонстрирует каждую из эвристик. Она также позволяет сравнить результаты, полученные при помощи эвристик и методов полного перебора и ветвей и границ. Введите значения минимальной и максимальной стоимости и дохода, а также число позиций и полную стоимость портфеля в соответствующих полях области Parameters (Параметры), чтобы задать параметры создаваемых данных. Затем выберите алгоритмы, которые вы хотите протестировать, и нажмите на кнопку Go. Программа выведет полную стоимость и доход для наилучшего решения, найденного при помощи каждого из алгоритмов. Она также сортирует решения по максимальному полученному доходу и выводит время выполнения для каждого из алгоритмов. Используйте метод ветвей и границ только для небольших задач, а метод полного перебора только для задач еще меньшего объема.

На рис. 8.8 показано окно программы Heur после решения задачи формирования портфеля для 20 позиций. Эвристики Fixed1, Fixed2 и No Changes 1, которые будут вскоре описаны, дали наилучшие эвристические решения. Заметьте, что эти решения немного хуже, чем точные решения, которые получены при использовании метода ветвей и границ.

Восхождение на холм

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

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

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

 

@Рис. 8.8. Программа Heur

 

========202

 

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

Для списка инвестиций из табл. 8.3, программа вначале выбирает позицию A, так как она дает максимальную прибыль — 9 миллионов долларов. Затем программа выбирает следующую позицию C, которая дает прибыль 8 миллионов. В этот момент потрачены уже 93 миллиона из 100, и программа не может приобрести больше позиций. Решение, полученное при помощи эвристики, включает позиции A и C, имеет стоимость 93 миллиона, и приносит 17 миллионов прибыли.

 

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

 

Эвристика восхождения на холм заполняет портфель очень быстро. Если позиции изначально были отсортированы в порядке убывания приносимой прибыли, то сложность этого алгоритма порядка O(N). Программа просто перемещается по списку, добавляя каждую позицию, если под нее есть место. Даже если список не упорядочен, то это алгоритм со сложностью порядка O(N²). Это намного лучше, чем O(2^N) шагов, которые требуются для полного перебора всех узлов в дереве. Для 20 позиций эта эвристика требует всего около 400 шагов, метод ветвей и границ — несколько тысяч, а полный перебор — более чем 2 миллиона.

 

Public Sub HillClimbing()

Dim i As Integer

Dim j As Integer

Dim big_value As Integer

Dim big_j As Integer

 

' Многократный обход списка и поиск следующей

' позиции, приносящей наибольшую прибыль,

' стоимость которой не превышает верхней границы.

For i = 1 To NumItems

   big_value = 0

   big_j = -1

   For j = 1 To NumItems

      ' Проверить, не находится ли он уже

      ' в решении.

      If (Not test_solution(j)) And _

          (test_cost + Items(j).Cost <= ToSpend) And _

          (big_value < Items(j).Profit)

      Then

          big_value = Items(j).Profit

          big_j = j

      End If

   Next j

 

   ' Остановиться, если не найдена позиция,

   ' удовлетворяющая условиям.

   If big_j < 0 Then Exit For

 

   test_cost = test_cost + Items(big_j).Cost

   test_solution(big_j) = True

   test_profit = test_profit + Items(big_j).Profit

Next i

End Sub