В этом руководстве вы узнаете, что такое жадный алгоритм. Также вы найдете пример жадного подхода.
Жадный алгоритм - это подход к решению проблемы путем выбора наилучшего варианта, доступного на данный момент, не беспокоясь о будущем результате, который он принесет. Другими словами, лучший выбор на местном уровне направлен на достижение наилучших результатов в глобальном масштабе.
Этот алгоритм может быть не лучшим вариантом для всех проблем. В некоторых случаях это может привести к неверным результатам.
Этот алгоритм никогда не возвращается, чтобы отменить принятое решение. Этот алгоритм работает по принципу «сверху вниз».
Основное преимущество этого алгоритма:
- Алгоритм описать проще .
- Этот алгоритм может работать лучше, чем другие алгоритмы (но не во всех случаях).
Возможное решение
Возможное решение - это то, которое обеспечивает оптимальное решение проблемы.
Жадный алгоритм
- Для начала набор решений (содержащий ответы) пуст.
- На каждом шаге в набор решений добавляется элемент.
- Если набор решений возможен, текущий элемент сохраняется.
- В противном случае товар отклоняется и больше не рассматривается.
Пример - жадный подход
Проблема: вы должны изменить сумму, используя минимально возможное количество монет. Сумма: 28 долларов Доступные монеты: 5 долларов монета 2 доллара монета 1 доллар
Решение:
- Создайте пустой набор решений = ().
- монеты = (5, 2, 1)
- сумма = 0
- Пока сумма 28, проделайте следующее.
- Выберите монету C из таких монет, чтобы sum + C <28.
- Если C + sum> 28, решение не возвращается.
- В противном случае сумма = сумма + C.
- Добавьте C в набор решений.
До первых 5 итераций набор решений содержал 5 монет по 5 долларов. После этого мы получаем монету 1 доллар 2 и, наконец, монету 1 доллар.
Жадные приложения алгоритмов
- Выбор Сортировка
- Проблема с рюкзаком
- Минимальное связующее дерево
- Проблема кратчайшего пути с одним источником
- Проблема с расписанием работы
- Алгоритм минимального связующего дерева Прима
- Минимальный алгоритм связующего дерева Краскала
- Алгоритм минимального остовного дерева Дейкстры
- Кодирование Хаффмана
- Алгоритм Форда-Фулкерсона