Рисунок справа иллюстрирует ситуацию перед началом заполнения рюкзака. В первом поле находятся неупакованные предметы, которые нам предстоит рассмотреть. Второе поле представляет свободное место в рюкзаке и предметы, которые уже уложены. Выполнение функции greedy_knapsack дает прибыль 39, а powdered_knapsack — 52,66. Это означает, что оптимальная прибыль находится где-то посередине. Как мы знаем из раздела «Разделяй и властвуй», эта задача с n предметами делится на две подзадачи с n — 1 предметами. Первая подзадача подразумевает, что предмет A был взят, вторая — что он не был взят:
Мы вычисляем верхнюю и нижнюю границы для этих двух подзадач. Каждая имеет нижнюю границу, равную 48: теперь мы знаем, что оптимальное решение находится между 48 и 52. Давайте рассмотрим подзадачу справа, поскольку у нее более интересные границы:
Крайняя левая подзадача имеет самую многообещающую верхнюю границу. Давайте продолжим наш анализ и выполним разбиение этой подзадачи:
Теперь мы можем сделать важные выводы. Выделенная цветом подзадача имеет нижнюю границу 49, которая равна ее верхней границе. Это означает, что оптимальная прибыль здесь должна равняться строго 49. Кроме того, обратите внимание, что 49 больше верхних границ во всех других ветвях, которые были проанализированы. Никакая другая ветвь не даст большую прибыль, чем 49, а значит, мы можем исключить их все из дальнейшего поиска.
Рациональное использование верхних и нижних границ позволило нам найти оптимальную прибыль, выполнив совсем немного вычислений. Мы динамически адаптировали наше пространство поиска по мере анализа возможностей.
Вот общие принципы работы метода ветвей и границ:
1) разделить задачу на подзадачи;
2) найти верхние и нижние границы каждой подзадачи;
3) сравнить границы подзадач всех ветвей;
4) выбрать самую многообещающую задачу и вернуться к шагу 1.
Если вы помните, стратегия поиска с возвратом (см. соответствующий раздел) тоже позволяет найти решение без обследования каждого возможного варианта. В случае поиска с возвратом мы исключаем пути, изучив каждый из них так далеко, как это возможно, и останавливаемся, когда нас устраивает решение. В случае же с методом ветвей и границ мы заранее определяем бесперспективные пути и не тратим впустую энергию на их обследование.
Подведем итоги
Решение задач, в сущности, представляет собой перемещение по пространству возможностей с целью найти правильный вариант. Мы узнали несколько способов, как это делается. Самый простой — полный перебор, то есть последовательная проверка каждого элемента в пространстве поиска.
Мы научились систематически делить задачи на меньшие, получая большое увеличение производительности. Многократное деление задач часто бывает сопряжено с решением проблем, вызванных одинаковыми подзадачами. В этих случаях важно использовать динамическое программирование, чтобы избежать повторных вычислений.
Мы убедились, что поиск с возвратом позволяет оптимизировать некоторые алгоритмы, основанные на полном переборе. Значения верхних и нижних границ (там, где их можно получить) позволяют ускорить поиск решения, для этого используется метод ветвей и границ. А когда стоимость вычисления оптимального решения оказывается неприемлемой, следует использовать эвристический алгоритм.
Все стратегии, с которыми мы познакомились, предназначены для работы с данными. Далее мы узнаем самые распространенные способы организации данных в памяти компьютера и как они влияют на производительность операций.
Полезные материалы
• Клейнберг Дж., Традос Е. Алгоритмы: разработка и применение. СПб.: Питер, 2017.
• Выбор стратегии проектирования алгоритмов (Choosing Algorithm Design Strategy, Shailendra Nigam, см. https://code.energy/nigam).
• Динамическое программирование (Dynamic programming, by Umesh V. Vazirani, см. https://code.energy/vazirani).
Глава 4. Данные
Хорошие программисты беспокоятся о структурах данных и их отношениях.
Линус Торвальдс
Контроль над данными в computer science имеет принципиальное значение: вычислительные процессы состоят из операций над данными, которые преобразуют вход в выход. Но алгоритмы обычно не конкретизируют, как они выполняются. К примеру, алгоритм merge (см. раздел «Итерация» главы 3) опирается на неустановленный внешний исходный код, который создает списки чисел, проверяет наличие в них элементов и добавляет эти элементы в списки. Алгоритм queens (раздел «Поиск (перебор) с возвратом») делает то же самое: он не заботится о том, как выполняются операции на шахматной доске или как позиции хранятся в памяти. Эти детали скрыты позади так называемых абстракций. В главе 4 мы узнаем:
как абстрактные типы данных делают код чистым;
какие общие абстракции желательно знать и уметь ими пользоваться;
какие существуют способы структурирования данных в памяти.
Но прежде чем мы углубимся в эту тему, давайте разберемся, что означают термины «абстракция» и «тип данных».
Абстракции
Абстракции позволяют нам опускать детали; они представляют простой интерфейс для доступа к функциональности сложных объектов. Например, автомобиль скрывает сложный механизм за панелью управления, причем таким образом, что любой человек может легко научиться водить без необходимости разбираться в машиностроении.
