Предположим, что мы начали поиск в дереве, изображенном на рис. 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 * 1019 узлов. Если алгоритм ветвей и границ проверяет только одну десятую процента этих узлов, и если компьютер проверяет миллион узлов в секунду, то для решения этой задачи потребовалось бы более 2 миллионов лет. В задачах, для которых алгоритм ветвей и границ выполняется слишком медленно, можно использовать эвристический подход.
Если качество решения не так важно, то приемлемым может быть результат, полученный при помощи эвристики. В некоторых случаях точность входных данных может быть недостаточной. Тогда хорошее эвристическое решение может быть таким же правильным, как и теоретически «наилучшее» решение.
В предыдущем примере метод ветвей и границ использовался для выбора инвестиционных возможностей. Тем не менее, вложения могут быть рискованными, и точные результаты часто заранее неизвестны. Может быть, что заранее будет неизвестен точный доход или даже стоимость некоторых инвестиций. В этом случае, эффективное эвристическое решение может быть таким же надежным, как и наилучшее решение, которое вы может вычислить точно.
@Таблица 8.2. Число узлов, проверенных при поиске методами полного перебора и ветвей и границ
=======201
В этом разделе обсуждаются эвристики, которые полезны при решении многих сложных задач. Программа Heur демонстрирует каждую из эвристик. Она также позволяет сравнить результаты, полученные при помощи эвристик и методов полного перебора и ветвей и границ. Введите значения минимальной и максимальной стоимости и дохода, а также число позиций и полную стоимость портфеля в соответствующих полях области Parameters (Параметры), чтобы задать параметры создаваемых данных. Затем выберите алгоритмы, которые вы хотите протестировать, и нажмите на кнопку Go. Программа выведет полную стоимость и доход для наилучшего решения, найденного при помощи каждого из алгоритмов. Она также сортирует решения по максимальному полученному доходу и выводит время выполнения для каждого из алгоритмов. Используйте метод ветвей и границ только для небольших задач, а метод полного перебора только для задач еще меньшего объема.
На рис. 8.8 показано окно программы Heur после решения задачи формирования портфеля для 20 позиций. Эвристики Fixed1, Fixed2 и No Changes 1, которые будут вскоре описаны, дали наилучшие эвристические решения. Заметьте, что эти решения немного хуже, чем точные решения, которые получены при использовании метода ветвей и границ.
Эвристика восхождения на холм (hill‑climbing) вносит изменения в текущее решение, чтобы максимально приблизить его к цели. Этот процесс называется восхождением на холм, так как он похож на то, как заблудившийся путешественник пытается ночью добраться до вершины горы. Даже если уже слишком темно, чтобы еще можно было разглядеть что‑то вдали, путешественник может попытаться добраться до вершины горы, постоянно двигаясь вверх.
Конечно, существует вероятность, что путешественник застрянет на вершине меньшего холма и не доберется до пика. Эта проблема всегда может возникать при использовании этой эвристики. Алгоритм может найти решение, которое может оказаться локально приемлемым, но это не обязательно наилучшее возможное решение.