На этом шаге мы рассмотрим реализацию этого алгоритма.
Алгоритм ветвей и границ можно считать разновидностью алгоритма перебора с возвратами, который выполняет такой же полный, но более эффективный перебор вариантов решения дискретных и комбинаторных задач оптимизации. Его идея заключается в использовании границ для сокращения дерева рекурсии не только тогда, когда частичное решение не удовлетворяет ограничениям задачи, но и когда ясно, что расширение частичного решения не улучшит решения, найденного на предыдущих шагах.
Суть метода ветвей и границ, который мы применим к задаче о рюкзаке 0-1, - в использовании дополнительного параметра для хранения максимальной суммарной стоимости, которая получается при расширении частичного решения. Если при вызове некоторого метода это значение хуже лучшего, найденного на предыдущих шагах, то алгоритм не будет расширять частичное решение, поскольку не сможет улучшить его. Это позволяет сократить ещё больше узлов дерева рекурсии, что может привести к значительно более эффективному поиску.
На рисунке 1 приведено дерево рекурсии для тех же весов, стоимостей и грузоподъёмности рюкзака, что на рисунке 1 предыдущего шага.
Рис.1. Дерево рекурсии алгоритма ветвей и границ для решения задачи о рюкзаке 0-1
Но в этом случае числа в узлах указывают частичную стоимость и границу максимально возможной стоимости, которую мы могли бы получить, расширив связанное с ней частичное решение, как показано на рисунке 1(a). Первоначально частичная стоимость равна 0, а граница, как показано на рисунке 1(b), равна сумме всех стоимостей предметов (то есть 23 = 7 + 2 + 10 + 4), так как сначала мы должны рассмотреть случай, когда все предметы помещаются в рюкзаке.
Каждый внутренний узел глубины i может иметь два дочерних узла. Спуск по левой ветви означает, что предмет i не добавляется в рюкзак. Поэтому частичная стоимость не меняется, но граница при этом уменьшается на vi, поскольку стоимость этого предмета уже не может входить в суммарную стоимость полного решения. И наоборот, спуск по правой ветви означает, что предмет добавляется в рюкзак и его стоимость vi добавляется к частичной стоимости, но граница при этом остаётся неизменной.
Подобно примеру на рисунке 1 202 шага, метод обновляет лучшее решение, найденное ранее (затемнённые листья дерева). Кроме того, обведённые крупным пунктиром узлы обозначают вызовы метода, которые не выполняются, так как сумма весов предметов превышает грузоподъёмность рюкзака. Помимо этого, на рисунке есть обведённые мелким пунктиром узлы, которые алгоритм также не вызывает, поскольку граница их стоимости меньше лучшей из встречавшихся ранее. Например, лучшая стоимость по достижении четвёртого листа - 14. После этого нужно рассмотреть узел с частичной стоимостью 2 и границей 16. Отказавшись от третьего предмета, алгоритм должен уменьшить границу на 10, а это означает, что максимально возможная суммарная стоимость, которую можно получить при расширении частичного решения, равна 16 - 10 = 6. Поскольку 6 < 14 (это отношение изображено под узлом), алгоритм не вызывает метода, сокращая тем самым дерево рекурсии. Обратите внимание, что дерево рекурсии этого алгоритма имеет ту же структуру, что на рисунке 1 202 шага, но содержит меньше узлов, так как сокращает дерево в большем количестве случаев. На практике такое усовершенствование может оказать существенное влияние на эффективность.
В примере 12.14 приведён код решения задачи методом ветвей и границ, который во многом схож с текстом примера 12.12.
Пример 12.14. Алгоритм ветвей и границ для решения задачи рюкзака 0-1
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
def knapsack_0_1_bnb(i, w_left, current_v, max_v, sol, opt_sol, opt_v, w, v, C): # Проверить базовый вариант if i == len(sol): # Check if better solution has been found if current_v > opt_v: # Обновить оптимальное значение и решение opt_v = current_v for k in range(0, len(sol)): opt_sol[k] = sol[k] else: # Генерация кандидатов for k in range(0, 2): # Проверить, можно ли обрезать дерево рекурсии # в соответствии с ограничением (емкости) if k * w[i] <= w_left: # Обновить максимально возможное значение new_max_v = max_v - (1 - k) * v[i] # Проверить, можно ли обрезать дерево рекурсии # в соответствии с оптимальным значением if new_max_v > opt_v: # Развернуть частичное решение sol[i] = k # Обновите оставшуюся емкость # и частичное значение new_w_left = w_left - k * w[i] new_current_v = current_v + k * v[i] # Попробовать развернуть частичное решение opt_v = knapsack_0_1_bnb(i + 1, new_w_left, new_current_v, new_max_v, sol, opt_sol, opt_v, w, v, C) # Возврат оптимального решения, найденного на данный момент return opt_v |
Основное различие между ними - новый (четвёртый) параметр max_v, в котором сохраняется граница. Отметим, что он инициализируется в методе-оболочке суммарной стоимостью всех предметов. В рекурсивном условии метод, проверив правильность частичного решения с новым кандидатом (строка 17), вычисляет новое значение границы new_max_v (строка 20). Обратите внимание, что при k = 0 новая граница уменьшается на vi, тогда как при k = 1 она остаётся неизменной. После этого метод проверяет, можно ли сократить дерево с новой границей и вычисленной ранее оптимальной стоимостью решения (строка 24). Остальная часть кода аналогична алгоритму перебора с возвратами.
Наконец, в примере 12.15 приводится метод-оболочка, решающий задачу для конкретных значений w, v и C.
Пример 12.15. Метод-оболочка алгоритма ветвей и границ для решения конкретной задачи рюкзака 0-1
| 1 2 3 4 5 6 7 8 9 10 11 12 |
def knapsack_0_1_branch_and_bound_wrapper(w, v, C): sol = [0] * (len(w)) opt_sol = [0] * (len(w)) total_v = knapsack_0_1_bnb(0, C, 0, sum(v), sol, opt_sol, -1, w, v, C) print_knapsack_solution(opt_sol, w, v, C, total_v) w = [3, 6, 9, 5] # Список весов объектов v = [7, 2, 10, 4] # Список значений объектов C = 15 # Грузоподъемность рюкзака knapsack_0_1_branch_and_bound_wrapper(w, v, C) |
На следующем шаге мы приведем решения нескольких задач.
