Жадный алгоритм
Жадный алгоритм (по-английски greedy algorithm), также называемый жадным методом, — это алгоритмическая стратегия, которая на каждом шаге делает лучший или оптимальный (то есть наиболее выгодный) выбор в текущем состоянии, надеясь прийти к глобально лучшему или оптимальному результату.
Жадный алгоритмКак мы часто говорим, он заботится только о сиюминутной выгоде и не учитывает общий оптимум; сделанный выбор является лишь локально оптимальным решением в некотором смысле.
Представьте, что у вас есть куча монет разных номиналов (например, 1 yuan, 5 jiao, 1 jiao), и вам нужно набрать 1.8 yuan, используя наименьшее количество монет.
Очень естественная идея такова:Всегда сначала брать монету наибольшего номинала,。
Сначала взять монету в 1 yuan, останется 0.8 yuan; затем взять монету в 5 jiao, останется 0.3 yuan; наконец, взять три монеты по 1 jiao.
На протяжении всего процесса на каждом шаге мы делалиВыбор, который сейчас кажется наилучшимЭто и есть основная идея жадного алгоритма.
Жадный алгоритмОн похож на близорукого, но решительного человека:
- Выбор на каждом шагеВ текущем состоянии сделать выбор, который кажется оптимальным.
- Не учитывает общую картину: не учитывая влияние этого выбора на будущее
- Ожидаемый результатНадежда, что локально оптимальный выбор может привести к глобально оптимальному решению.
Примеры из реальной жизни:
- Размен монет: всегда сначала использовать монету наибольшего номинала
- Восхождение на холм: всегда двигаться в самом крутом направлении
- Покупки: всегда покупать наиболее выгодный в данный момент товар
- Выбор маршрута: всегда выбирать текущий кратчайший путь
Характеристики жадного алгоритма
- Свойство жадного выбораОптимальное решение на каждом шаге может быть получено из локально оптимальных решений предыдущих шагов. Последующие выборы не влияют на предыдущие выборы.
- Оптимальная подструктураОптимальное решение задачи содержит оптимальные решения её подзадач. Это также свойство динамического программирования, но жадный алгоритм на каждом шаге жадно выбирает оптимальное решение подзадачи.
| Особенности | Описание | Преимущества | Недостатки |
|---|---|---|---|
| Локальный оптимум | Выбирать текущее оптимальное решение на каждом шаге | Простой и интуитивно понятный | Может не быть глобально оптимальным |
| Необратимый | Нельзя пожалеть о сделанном выборе | Быстрое принятие решений | Склонность застревать в локальных оптимумах |
| Эффективность | Обычно имеет низкую временную сложность | Высокая практичность | Ограниченная применимость |
| Простая реализация | Логика ясна и проста для понимания | Простота в написании кода | Требуется доказать корректность |
Отличия от динамического программирования
Это момент, который часто смущает новичков. Давайте сравним их с помощью таблицы:
| Особенности | Жадный алгоритм | Динамическое программирование |
|---|---|---|
| Основа принятия решения | Делать текущий оптимальный выбор на каждом шаге,Без откатов。 | Выбор на каждом шаге зависит от решения подзадач, сохраняет промежуточные результаты и позволяет сравнивать несколько вариантов. |
| Гарантия оптимального решения | Может не дать глобально оптимального решения; сама задача должна обладать свойством жадного выбора. | Обычно позволяет получить глобально оптимальное решение. |
| Эффективность | Эффективен, обычно с меньшей временной сложностью. | Относительно низкая, потому что приходится решать перекрывающиеся подзадачи. |
| Применимые сценарии | Задача обладает свойством жадного выбора и оптимальной подструктурой, например кодирование Хаффмана и минимальные остовные деревья. | Задача обладает оптимальной подструктурой и перекрывающимися подзадачами, например задача о рюкзаке и кратчайшие пути. |
Проще говоря,динамическое программирование — это «семь раз отмерь, один раз отрежь» и жертвование сиюминутными интересами ради долгосрочных выгод; жадные алгоритмы — это «жить сегодняшним днём» и погоня только за сиюминутной выгодой.
Базовый каркас жадного алгоритма
У жадных алгоритмов нет фиксированного шаблона кода, но их идею можно свести к следующим шагам:
- Построить математическую модель: абстрагировать реальную задачу в математическую задачу.
- Определите жадную стратегиюОпределите критерий выбора «оптимального решения» на каждом шаге. Это ядро и сложность алгоритма.
- Докажите жадную стратегиюДокажите, что определённая жадная стратегия может привести к глобально оптимальному решению (необязательно, но важно; в задачах на алгоритмы обычно нужно понимать её корректность).
- Итеративное решениеСогласно стратегии, начиная с начального состояния, делайте жадные выборы шаг за шагом, пока не будет получено решение задачи.
Общий каркас псевдокода выглядит так:
Пример
# 1. Инициализация: может включать сортировку, создание контейнера результата и т. д.
solution = []
# 2. Переберите все варианты; обычно сначала нужно отсортировать по некоторому правилу.
for item in sorted(problem.items, key=Правило жадной стратегии):
# 3. Жадный выбор: если текущий выбор удовлетворяет условию, примите его.
if is_feasible(solution, item):
solution.append(item)
# 4. Вернуть окончательно построенное решение
return solution
Классические задачи и примеры кода
Рассмотрим применение жадных алгоритмов на нескольких классических задачах. Для каждой задачи мы: 1) проанализируем задачу и жадную стратегию; 2) приведём полный код; 3) дадим построчное объяснение.
Пример 1: задача о размене монет
Описание задачи: Предположим, система монет — [100, 50, 20, 10, 5, 1] (единица: центы), и нам нужно разменятьamountцентов, найдите минимальное количество необходимых монет.
Жадная стратегия:Каждый раз выбирать наибольшую монету, номинал которой не превышает оставшуюся сумму.Для денежной системы женьминьби эта стратегия эффективна.
Реализация кода:
Пример
"""
Использовать жадный алгоритм для решения задачи о размене монет (для конкретной системы монет)
:param coins: list[int], список номиналов монет, должен быть отсортирован по убыванию
:param amount: int, общая сумма, для которой нужно выдать сдачу
:return: list[int], список использованных номиналов монет
"""
coins.sort(reverse=True) # Убедитесь, что монеты отсортированы по номиналу от наибольшего к наименьшему
result = [] # Используется для хранения монет для выдачи сдачи
remaining = amount # Оставшаяся сумма, для которой нужна сдача
for coin in coins:
# Когда текущий номинал монеты меньше или равен оставшейся сумме, используйте его как можно больше
while remaining >= coin:
result.append(coin)
remaining -= coin # Вычтите текущий номинал монеты из оставшейся суммы
# Проверьте, выдана ли сдача точно
if remaining == 0:
return result
else:
# Для случаев, когда точную сдачу выдать нельзя (хотя в этой монетной системе такого не произойдёт)
return None
# Тестовые данные
test_coins = [100, 50, 20, 10, 5, 1]
test_amount = 186 # 1 yuan 8 jiao 6 fen
change = coin_change_greedy(test_coins, test_amount)
print(f"Сдача для {test_amount} fen, нужно монет: {change}")
print(f"Количество монет: {len(change)}")
# Вывод: сдача для 186 fen, нужно монет: [100, 50, 20, 10, 5, 1]
# Количество монет: 6
Пояснение кода:
- Строка 8:
coins.sort(reverse=True)Это ключевая подготовка для жадной стратегии, гарантирующая, что мы всегда сначала рассматриваем более крупные номиналы. - Строки 12-15:
whileЦикл гарантирует, что пока текущий номинал всё ещё можно использовать, мы продолжаем его использовать; это реализует жадный выбор «как можно больше». - Строки 18-22: Проверьте окончательный результат, чтобы убедиться, что сумма совпадает точно.
Важное замечание: Жадный алгоритм для решения задачи о размене монетНе всегда даёт оптимальное решениеНапример, если система монет [25, 20, 10, 5, 1] и нужно разменять 40 центов, жадный метод выберет 25+10+5 (три монеты), но оптимальное решение — 20+20 (две монеты).Жадная стратегия эффективна только в определённых денежных системах (например, RMB).
Пример 2: Задача планирования интервалов
Описание задачиДано множество встреч (у каждой есть время начала и время окончания). Как их организовать, чтобы максимизировать количество встреч, которые можно провести в одной переговорной?
Жадная стратегия:Каждый раз выбирайте встречу с самым ранним временем окончанияЭто оставляет больше времени для последующих встреч.
Реализация кода:
Пример
"""
Решение задачи о максимальном количестве непересекающихся интервалов (планирование интервалов)
:param intervals: список [start, end], список интервалов
:return: список [start, end], список выбранных интервалов
"""
# 1. Отсортировать по времени окончания по возрастанию
intervals_sorted = sorted(intervals, key=lambda x: x[1])
selected = [] # Сохранить выбранные интервалы
last_end_time = -float('inf') # Инициализировать время окончания предыдущего выбранного интервала
for interval in intervals_sorted:
start, end = interval
# 2. Жадный выбор: Если время начала текущего интервала не раньше времени окончания предыдущего выбранного интервала, выбрать его
if start >= last_end_time:
selected.append(interval)
last_end_time = end # Обновить последнее время окончания
return selected
# Тестовые данные: каждый подсписок представляет встречу [время начала, время окончания]
test_intervals = [
[1, 3], [2, 4], [3, 5], [4, 6], [5, 7],
[1, 2], [2, 3], [1, 4]
]
result = interval_scheduling(test_intervals)
print(Максимальное количество встреч, которые можно запланировать (после сортировки по времени окончания):)
for meeting in result:
print(fВстреча [{meeting[0]}, {meeting[1]}])
print(fВсего {len(result)} встреч)
# Один из возможных вариантов вывода (поскольку порядок после сортировки может отличаться, но количество оптимально):
# Встреча [1, 2]
# Встреча [2, 3]
# Встреча [3, 5] или [4, 6], и т.д.
# Всего 4 встреч
Пояснение кода:
- Строка 10:
sorted(intervals, key=lambda x: x[1])Это суть реализации жадной стратегии: сортировка по времени окончания. - Строки 16-19:
if start >= last_end_timeЭто проверка допустимости, гарантирующая, что текущая встреча не пересекается с выбранными встречами. - Временная сложность этого алгоритма — O(n log n), в основном из-за сортировки.
Пример 3: кодирование Хаффмана — концепция и упрощённая реализация
Кодирование Хаффмана — это жадный алгоритм для сжатия данных без потерь. Его основная идея:назначать более короткие коды символам с более высокой частотой и более длинные коды символам с более низкой частотой.。
Жадная стратегияПовторно объединяйте два узла с наименьшими частотами, чтобы построить двоичное дерево.
Поскольку полная реализация довольно длинная, здесь мы показываем её основной процесс жадного слияния:
Пример
class Node:
"""Класс узла дерева Хаффмана"""
def __init__(self, char, freq):
self.char = char # Символ (только листовые узлы)
self.freq = freq # Частота
self.left = None
self.right = None
# Чтобы обеспечить сравнение в куче, определите методы сравнения
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(char_freq):
"""
Построить дерево Хаффмана
:param char_freq: dict, символы и их частоты, например {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
:return: Node, корневой узел дерева Хаффмана
"""
# 1. Инициализация: создать листовой узел для каждого символа и поместить его в минимальную кучу (приоритетную очередь)
heap = [Node(char, freq) for char, freq in char_freq.items()]
heapq.heapify(heap) # Преобразовать список в минимальную кучу
# 2. Жадное слияние: когда в куче больше одного узла
while len(heap) > 1:
# Извлечь два узла с наименьшими частотами
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# Создать новый внутренний узел, частота которого равна сумме частот дочерних узлов
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
# Добавить новый узел обратно в кучу
heapq.heappush(heap, merged)
# Последний оставшийся узел в куче — корень дерева Хаффмана
return heap[0] if heap else None
# Тестовые данные
test_freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
root = build_huffman_tree(test_freq)
print("Построение дерева Хаффмана завершено! Частота корня =", root.freq if root else 0)
# Вывод: Построение дерева Хаффмана завершено! Частота корня = 100
Визуализация алгоритмаНа следующем рисунке показаны первые несколько шагов слияния при построении дерева Хаффмана с использованием приведённых выше тестовых данных:

Пояснение с иллюстрациейАлгоритм всегда выбирает два узла с наименьшими частотами из всех доступных узлов (сначала листовых, а позже включая внутренние узлы) и объединяет их в новый внутренний узел. Этот процесс повторяется до тех пор, пока не будет сформировано полное двоичное дерево. Листовые узлы этого дерева соответствуют исходным символам, а путь от корня до листа (левая ветвь — 0, правая ветвь — 1) является кодом Хаффмана для этого символа.
Доказательство корректности жадного алгоритма
Как определить, можно ли решить задачу с помощью жадного алгоритма? Обычно нужно доказать следующие два пункта:
- Свойство жадного выбораМетодом математической индукции или доказательством от противного можно доказать, что оптимальный выбор на первом шаге содержится в некотором глобальном оптимальном решении.
- Оптимальная подструктураДокажите, что после первого жадного выбора исходная задача сводится к задаче меньшего масштаба.Подзадачи того же типа。
withЗадача о расписании интерваловИдея доказательства на примере ...:
- Жадный выборПусть интервал с самым ранним временем окончания среди всех интервалов будет
i. Существует оптимальное решение, содержащее интервал ...i。- Доказательство: Предположим, что некоторое оптимальное решение не содержит его.
i. Пусть первый интервал в этом оптимальном решении — ...j. Потому чтоiзаканчивается раньше всех, поэтому заменим ... на ...iзаменаjон не конфликтует с другими интервалами, и размер решения остаётся неизменным, поэтому оно содержитiПолученное решение также оптимально.
- Доказательство: Предположим, что некоторое оптимальное решение не содержит его.
- Оптимальная подструктура: При выборе интервалов
iПосле этого оставшаяся задача состоит в том, чтобы среди всех интервалов, которые ... с ...iнайти оптимальное решение среди неперекрывающихся интервалов. Это представляет собой подзадачу исходной задачи.
Практические упражнения
Теперь попробуйте решить следующие задачи, используя жадный алгоритм, чтобы закрепить понимание.
Упражнение 1: Jump Game
Задача: Дан массив неотрицательных целых чиселnumsИзначально вы находитесь на первом индексе массива. Каждый элемент массива представляет максимальную длину прыжка с этой позиции. Определите, можете ли вы достичь последнего индекса.Пример:nums = [2,3,1,1,4], возвращаетTrue(Прыжок на 1 шаг с индекса 0 на индекс 1, затем прыжок на 3 шага к последнему индексу).Подсказка о жадной стратегииВместо моделирования того, насколько далеко прыгать на каждом шаге, поддерживайтесамую дальнюю достижимую позицию。
Упражнение 2: Раздать печенье
ЗадачаЕсть группа детей и куча печенья; у каждого ребёнка есть значение аппетитаg[i], каждое печенье имеет размерs[j]Ребёнок считается удовлетворённым, только если размер печенья >= аппетита ребёнка. Найдите максимальное количество детей, которых можно удовлетворить.Пример:g = [1,2,3], s = [1,1], вывод1。
Подсказка о жадной стратегии: Чтобы удовлетворить больше детей,используйте наименьшее печенье, чтобы удовлетворить ребёнка с наименьшим аппетитом.(или подумайте об этом наоборот).
Упражнение 3: Лучшее время для покупки и продажи акций II
Задача: Дан массивprices, гдеprices[i]— это ... данной акции в ...iЦена за каждый день. Вы можете совершить сколько угодно транзакций (то есть купить и продать одну акцию), но вы не можете участвовать в нескольких транзакциях одновременно (вы должны продать предыдущую акцию перед повторной покупкой). Рассчитайте максимальную прибыль, которую вы можете получить.Пример:prices = [7,1,5,3,6,4], вывод7(Купить по 1 и продать по 5, прибыль 4; купить по 3 и продать по 6, прибыль 3; общая прибыль 7).Подсказка о жадной стратегииПрибыль можно разложить на ежедневные разницы цен. Покасегодняшняя цена выше вчерашней, берите эту разницу как прибыль.。