Жадный алгоритм

Жадный алгоритм (по-английски greedy algorithm), также называемый жадным методом, — это алгоритмическая стратегия, которая на каждом шаге делает лучший или оптимальный (то есть наиболее выгодный) выбор в текущем состоянии, надеясь прийти к глобально лучшему или оптимальному результату.

Жадный алгоритмКак мы часто говорим, он заботится только о сиюминутной выгоде и не учитывает общий оптимум; сделанный выбор является лишь локально оптимальным решением в некотором смысле.

Представьте, что у вас есть куча монет разных номиналов (например, 1 yuan, 5 jiao, 1 jiao), и вам нужно набрать 1.8 yuan, используя наименьшее количество монет.

Очень естественная идея такова:Всегда сначала брать монету наибольшего номинала,。

Сначала взять монету в 1 yuan, останется 0.8 yuan; затем взять монету в 5 jiao, останется 0.3 yuan; наконец, взять три монеты по 1 jiao.

На протяжении всего процесса на каждом шаге мы делалиВыбор, который сейчас кажется наилучшимЭто и есть основная идея жадного алгоритма.

Жадный алгоритмОн похож на близорукого, но решительного человека:

  • Выбор на каждом шагеВ текущем состоянии сделать выбор, который кажется оптимальным.
  • Не учитывает общую картину: не учитывая влияние этого выбора на будущее
  • Ожидаемый результатНадежда, что локально оптимальный выбор может привести к глобально оптимальному решению.

Примеры из реальной жизни:

  • Размен монет: всегда сначала использовать монету наибольшего номинала
  • Восхождение на холм: всегда двигаться в самом крутом направлении
  • Покупки: всегда покупать наиболее выгодный в данный момент товар
  • Выбор маршрута: всегда выбирать текущий кратчайший путь

Характеристики жадного алгоритма

  • Свойство жадного выбораОптимальное решение на каждом шаге может быть получено из локально оптимальных решений предыдущих шагов. Последующие выборы не влияют на предыдущие выборы.
  • Оптимальная подструктураОптимальное решение задачи содержит оптимальные решения её подзадач. Это также свойство динамического программирования, но жадный алгоритм на каждом шаге жадно выбирает оптимальное решение подзадачи.
Особенности Описание Преимущества Недостатки
Локальный оптимум Выбирать текущее оптимальное решение на каждом шаге Простой и интуитивно понятный Может не быть глобально оптимальным
Необратимый Нельзя пожалеть о сделанном выборе Быстрое принятие решений Склонность застревать в локальных оптимумах
Эффективность Обычно имеет низкую временную сложность Высокая практичность Ограниченная применимость
Простая реализация Логика ясна и проста для понимания Простота в написании кода Требуется доказать корректность

Отличия от динамического программирования

Это момент, который часто смущает новичков. Давайте сравним их с помощью таблицы:

Особенности Жадный алгоритм Динамическое программирование
Основа принятия решения Делать текущий оптимальный выбор на каждом шаге,Без откатов。 Выбор на каждом шаге зависит от решения подзадач, сохраняет промежуточные результаты и позволяет сравнивать несколько вариантов.
Гарантия оптимального решения Может не дать глобально оптимального решения; сама задача должна обладать свойством жадного выбора. Обычно позволяет получить глобально оптимальное решение.
Эффективность Эффективен, обычно с меньшей временной сложностью. Относительно низкая, потому что приходится решать перекрывающиеся подзадачи.
Применимые сценарии Задача обладает свойством жадного выбора и оптимальной подструктурой, например кодирование Хаффмана и минимальные остовные деревья. Задача обладает оптимальной подструктурой и перекрывающимися подзадачами, например задача о рюкзаке и кратчайшие пути.

Проще говоря,динамическое программирование — это «семь раз отмерь, один раз отрежь» и жертвование сиюминутными интересами ради долгосрочных выгод; жадные алгоритмы — это «жить сегодняшним днём» и погоня только за сиюминутной выгодой.


Базовый каркас жадного алгоритма

У жадных алгоритмов нет фиксированного шаблона кода, но их идею можно свести к следующим шагам:

  1. Построить математическую модель: абстрагировать реальную задачу в математическую задачу.
  2. Определите жадную стратегиюОпределите критерий выбора «оптимального решения» на каждом шаге. Это ядро и сложность алгоритма.
  3. Докажите жадную стратегиюДокажите, что определённая жадная стратегия может привести к глобально оптимальному решению (необязательно, но важно; в задачах на алгоритмы обычно нужно понимать её корректность).
  4. Итеративное решениеСогласно стратегии, начиная с начального состояния, делайте жадные выборы шаг за шагом, пока не будет получено решение задачи.

Общий каркас псевдокода выглядит так:

Пример

def greedy_algorithm(problem):
    # 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центов, найдите минимальное количество необходимых монет.

Жадная стратегия:Каждый раз выбирать наибольшую монету, номинал которой не превышает оставшуюся сумму.Для денежной системы женьминьби эта стратегия эффективна.

Реализация кода:

Пример

def coin_change_greedy(coins, 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: Задача планирования интервалов

Описание задачиДано множество встреч (у каждой есть время начала и время окончания). Как их организовать, чтобы максимизировать количество встреч, которые можно провести в одной переговорной?

Жадная стратегия:Каждый раз выбирайте встречу с самым ранним временем окончанияЭто оставляет больше времени для последующих встреч.

Реализация кода:

Пример

def interval_scheduling(intervals):
    """
Решение задачи о максимальном количестве непересекающихся интервалов (планирование интервалов)
: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: кодирование Хаффмана — концепция и упрощённая реализация

Кодирование Хаффмана — это жадный алгоритм для сжатия данных без потерь. Его основная идея:назначать более короткие коды символам с более высокой частотой и более длинные коды символам с более низкой частотой.。

Жадная стратегияПовторно объединяйте два узла с наименьшими частотами, чтобы построить двоичное дерево.

Поскольку полная реализация довольно длинная, здесь мы показываем её основной процесс жадного слияния:

Пример

import heapq

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) является кодом Хаффмана для этого символа.


Доказательство корректности жадного алгоритма

Как определить, можно ли решить задачу с помощью жадного алгоритма? Обычно нужно доказать следующие два пункта:

  1. Свойство жадного выбораМетодом математической индукции или доказательством от противного можно доказать, что оптимальный выбор на первом шаге содержится в некотором глобальном оптимальном решении.
  2. Оптимальная подструктураДокажите, что после первого жадного выбора исходная задача сводится к задаче меньшего масштаба.Подзадачи того же типа。

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).Подсказка о жадной стратегииПрибыль можно разложить на ежедневные разницы цен. Покасегодняшняя цена выше вчерашней, берите эту разницу как прибыль.。

Другие расширения