Жадные, динамика, backtracking: как выбирать подход🔗
Три стратегии решения: от локального выбора к глобальному оптимуму🔗
В задачах оптимизации цель неизменна — найти наилучший результат среди множества вариантов. Однако метод поиска напрямую зависит от структуры задачи и того, как локальные действия влияют на финал.
Рассмотрим ситуацию: вам нужно покорить горную вершину в густом тумане.
- Жадный алгоритм (Greedy): на каждом этапе вы делаете шаг туда, где подъем самый крутой в данный момент. Вы не смотрите на карту, рассчитывая, что сумма выгодных мгновенных решений выведет вас на пик.
- Динамическое программирование (DP): вы делите склон на уровни. Чтобы достичь вершины, вы рассчитываете лучшие маршруты до промежуточных точек и сохраняете их, избавляя себя от повторных расчетов.
- Backtracking (Поиск с возвратом): вы методично проверяете каждую тропу. Если дорога заходит в тупик, вы возвращаетесь к последней развилке и пробуете альтернативу.
Формализация подходов🔗
Выбор стратегии диктуют три свойства задачи:
- Принцип жадного выбора (Greedy Choice Property): глобальный максимум достижим через серию локально оптимальных шагов, которые не придется отменять.
- Оптимальная подструктура (Optimal Substructure): общее решение состоит из лучших решений более мелких подзадач.
- Перекрывающиеся подзадачи (Overlapping Subproblems): в процессе вычислений алгоритм многократно сталкивается с одними и теми же условиями. Это свойство делает DP эффективнее перебора.
Диаграмма загружается…
Жадные алгоритмы обычно самые быстрые — их сложность составляет O(n) или O(nlogn). Динамическое программирование требует больше ресурсов: время выполнения растет до O(nk), а для хранения результатов нужна память. Backtracking — наиболее «дорогой» метод: в худшем случае его сложность экспоненциальна (O(2n) или O(n!)), поэтому его используют только на небольших объемах данных.
Изучим точные математические критерии, которые позволяют безошибочно определить подходящий метод.
Теоретический минимум: Математические критерии выбора🔗
Чтобы не подбирать инструменты наугад, в алгоритмике используют строгие критерии выбора метода. Решение между жадным подходом, динамическим программированием (DP) или бэктрекингом диктуется структурой пространства поиска и спецификой целевой функции.
1. Жадные алгоритмы: Локальная оптимальность🔗
Этот подход оправдан, если задача обладает свойством жадного выбора: локально лучший шаг на каждом этапе неизменно ведет к глобальному максимуму или минимуму. С точки зрения математики в последовательности решений S={s1,s2,…,sn} текущий выбор si не должен отрезать путь к оптимальному финалу.
Метод безупречно работает в структурах вроде матроидов. Однако если сиюминутная выгода блокирует доступ к лучшему итогу в будущем, жадная стратегия окажется ложной.
2. Динамическое программирование: Уравнение Беллмана🔗
DP применяют, когда задача сочетает в себе оптимальную подструктуру (глобальное решение строится из лучших решений подзадач) и перекрывающиеся подзадачи.
Фундаментом здесь служит принцип оптимальности Беллмана: какими бы ни были исходные условия, последующие действия должны формировать оптимальную стратегию относительно состояния, возникшего после первого шага. Это выражается рекуррентным уравнением:
V(s)=maxa∈A(s){R(s,a)+γV(s′)}
Где:
- V(s) — ценность текущего состояния;
- R(s,a) — мгновенная выгода от действия;
- V(s′) — ценность следующего состояния.
В отличие от жадности, мы не просто забираем максимум R(s,a), а соотносим его с потенциалом будущей выгоды V(s′).
3. Backtracking: Обход пространства состояний🔗
Когда у задачи нет явной подструктуры, а условия накладывают жесткие глобальные ограничения (например, поиск пути в лабиринте или расстановка фигур на доске), строится дерево решений:
- Узел — частичный вариант решения.
- Ребро — переход к новому шагу.
- Отсечение (Pruning) — немедленная остановка обхода ветви, если текущий вариант нарушает правила.
Сравнительная таблица критериев🔗
| Критерий |
Жадный алгоритм |
Динамическое программирование |
Backtracking (Бэктрекинг) |
| Логика выбора |
Один локальный шаг |
Сравнение результатов подзадач |
Проба с возможностью возврата |
| Гарантия идеала |
При «жадном свойстве» |
Глобальный оптимум |
Гарантирован (полный перебор) |
| Связи |
Шаги независимы в будущем |
Подзадачи взаимосвязаны |
Глобальные ограничения |
| Сложность |
От O(n) до O(nlogn) |
Полиномиальная O(nk) |
Экспоненциальная O(2n) или O(n!) |
Направления реализации🔗
Для DP и бэктрекинга характерны две стратегии управления данными:
- Top-down (Сверху-вниз): Рекурсивный путь. Задача дробится на части с использованием мемоизации (кеширования ответов), чтобы исключить дублирующие вычисления. Ситуация похожа на разбор матрешки, где мы запоминаем содержимое каждой уже открытой куклы.
- Bottom-up (Снизу-вверх): Итеративный путь. Таблица или массив заполняется последовательно, от простейших базовых случаев к итоговому результату. Это экономит стек вызовов и обычно выигрывает в скорости.
Механику этих стратегий на примере классической «Задачи о рюкзаке» изучим в следующем блоке.
Механика и реализация: Задача о рюкзаке (Knapsack Problem)🔗
Задача о рюкзаке — классический тест для проверки эффективности алгоритмов. Условие предельно ясно: есть набор предметов с весом wi и ценностью vi, а также сумка ограниченной емкости W. Требуется собрать комбинацию вещей с максимальной суммарной стоимостью. При этом логика решения радикально меняется даже при небольшом уточнении условий.
1. Дробный рюкзак (Fractional Knapsack): Жадный выбор🔗
Если содержимое можно делить (как золото или песок), применяется жадный метод. Здесь эффективен принцип локального оптимума: на каждом этапе выбирается объект с самой высокой удельной стоимостью pi=wivi.
Алгоритм действий:
- Вычислить pi для каждого элемента.
- Отсортировать предметы по убыванию ценности за единицу веса.
- Заполнять рюкзак, пока хватает места. Если целый объект не влезает, берется его максимально доступная часть.
Сложность составляет O(nlogn) из-за сортировки. Для жадной стратегии это самый удачный вариант развития событий.
2. Дискретный рюкзак (0/1 Knapsack): Динамическое программирование🔗
Когда предметы неделимы, простая сортировка по удельной цене подводит. Представим: объем рюкзака — 10 кг. Есть груз весом 6 кг стоимостью 60идвапо5кгза40 каждый. У первого плотность выше (10 против 8). Жадный алгоритм заберет его и остановится на выгоде в 60.Однакодинамическоепрограммирование(DP)найдетсвязкуиздвухпятитылограммовыхпредметов,котораядаст80.
Для поиска такого решения строится таблица состояний dp[i][j], где i — количество учтенных элементов, а j — доступная емкость от 0 до W.
Принцип вычислений:
Для каждого предмета и каждого значения веса:
- Если вес wi>j, забираем результат с прошлого шага: dp[i][j]=dp[i−1][j].
- Математически выбираем между «не брать предмет» и «положить его», прибавив его ценность к оптимальному набору для оставшегося веса:
dp[i][j]=max(dp[i−1][j],vi+dp[i−1][j−wi]).
| Предмет (v,w) |
j=0 |
j=1 |
j=2 |
j=3 |
j=4 |
j=5 |
| (0, 0) — Пусто |
0 |
0 |
0 |
0 |
0 |
0 |
| (6, 2) — А |
0 |
0 |
6 |
6 |
6 |
6 |
| (10, 3) — Б |
0 |
0 |
6 |
10 |
10 |
16 |
| (12, 4) — В |
0 |
0 |
6 |
10 |
12 |
16 |
def knapsack_dp(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w],
values[i-1] + dp[i-1][w - weights[i-1]])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
Временная и пространственная сложность — O(n⋅W). Затраты памяти можно оптимизировать до O(W), если использовать одномерный массив для хранения текущего ряда.
3. Малый рюкзак и Backtracking: Поиск с возвратом🔗
Если лимит W огромен (например, при дробных весах высокой точности), таблица DP становится избыточной. Если при этом количество элементов невелико (n<20), удобнее применить направленный перебор. Процесс выглядит как дерево решений: на каждом узле мы решаем, включать ли конкретный груз в комплект.
Диаграмма загружается…
Этот метод позволяет отсекать ветви, где вес уже превысил лимит, не проверяя все 2n комбинаций. Хотя теоретическая асимптотика остается экспоненциальной — O(2n), такой вариант незаменим, когда структура данных не позволяет задействовать динамическое программирование.
Механизмы отсечения вычислений и оценку производительности мы подробнее исследуем в блоке про Big O.
Анализ сложности и типичные ошибки🔗
Выбор стратегии — это всегда поиск компромисса между точностью ответа и вычислительными затратами. Пока жадный алгоритм проходит по данным один раз, бэктрекинг исследует дерево состояний, которое экспоненциально разрастается с каждым новым элементом.
Сравнительная сложность подходов🔗
Ниже сопоставлена асимптотика для решения классических проблем (например, дискретной задачи о рюкзаке).
| Метод |
Временная сложность (Time) |
Пространственная сложность (Space) |
Тип задачи |
| Жадный |
O(nlogn) или O(n) |
O(1) или O(n) |
Непрерывная / Дробная |
| Динамика (DP) |
O(n⋅W) |
O(n⋅W) или O(W) |
Дискретная (целая) |
| Бэктрекинг |
O(2n) или O(n!) |
O(n) (стек вызовов) |
Поиск всех решений |
n — количество элементов, W — ограничение по вместимости.
Типичные ловушки при реализации🔗
-
Неуместное использование жадной стратегии
Распространенный просчет — выбор локального оптимума там, где он блокирует путь к глобальному результату. В дискретном рюкзаке взятие самого дорогого предмета может занять весь объем, не оставив места для комбинации менее ценных, но в сумме более выгодных вещей. Такой путь оправдан только при наличии свойства жадного выбора (структуры матроида).
-
Экспоненциальный взрыв и отсутствие Pruning
При бэктрекинге алгоритм строит дерево решений. Без «обрезки ветвей» (pruning) программа проверяет заведомо тупиковые сценарии. Если текущий вес уже превысил лимит W, перебор в этой ветке бессмысленен — узел нужно отсечь.
def solve_knapsack(idx, current_weight, current_value, items, capacity):
# 1. Базовый случай: предметы закончились
if idx == len(items):
return current_value
# 2. Pruning: если предмет не влезает, ветку не развиваем
res = solve_knapsack(idx + 1, current_weight, current_value, items, capacity)
item_w, item_v = items[idx]
if current_weight + item_w <= capacity:
# Ветвление только при соблюдении инварианта
res = max(res, solve_knapsack(idx + 1, current_weight + item_w,
current_value + item_v, items, capacity))
return res
- Ошибки инициализации в DP
Динамическое программирование требует четкого «дна» рекурсии. Без начальных значений (например,
dp[0] = 0) программа зациклится или обратится к несуществующему индексу. В таблицах это часто приводит к ошибке «off-by-one» (сдвиг на единицу), когда итог искажается из-за неверной подготовки стартовой строки или столбца.
Диаграмма загружается…
Динамическое программирование — это упорядоченный перебор с кэшированием, тогда как жадный метод — быстрый выбор, требующий строгого доказательства. Если математического обоснования жадного шага нет, надежнее использовать DP, если позволяют лимиты памяти.
Алгоритм принятия решения🔗
Перед написанием кода важно проанализировать структуру проблемы по трем критическим точкам. Такой подход помогает сразу отсечь неподходящие инструменты и сэкономить время на реализации.
Диаграмма загружается…
Чек-лист из трех вопросов🔗
- Принцип жадного выбора. Гарантирует ли лучший шаг на текущем этапе итоговый успех? Если выбор элемента здесь и сейчас не блокирует доступ к оптимальному решению в будущем (как в задаче о дробном рюкзаке), логично использовать жадную стратегию. Её сложность обычно составляет O(nlogn) из-за предварительной сортировки.
- Наличие перекрывающихся подзадач. Можно ли разбить условие на части, которые вычисляются многократно? Прямая рекурсия в подобных случаях вызывает экспоненциальный рост нагрузки. Чтобы этого избежать, применяют динамическое программирование.
- Полнота выборки. Нужно найти одно экстремальное значение или перечислить все комбинации, подходящие под условие (например, расстановку фигур на доске)? Для генерации всех возможных конфигураций подходит Backtracking.
Оценка ресурсов (Space Complexity)🔗
Выбранный метод напрямую влияет на объем затрачиваемой памяти. Жадные сценарии часто обходятся O(1) дополнительного пространства, тогда как DP и перебор требуют больше ресурсов:
- Мемоизация (Top-down): к пространственной сложности добавляется O(N) для хранения кэша и стека рекурсии. Это плата за избавление от повторных вычислений.
- Табуляция (Bottom-up): итеративный подход часто позволяет оптимизировать память до O(1) или O(W), если для вычисления текущего состояния достаточно данных только с предыдущего шага.
Нюансы заполнения таблиц и инверсию управления в DP мы изучим в занятии №14.
