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

В этом руководстве вы узнаете, что такое жадный алгоритм. Также вы найдете пример жадного подхода.

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

Этот алгоритм может быть не лучшим вариантом для всех проблем. В некоторых случаях это может привести к неверным результатам.

Этот алгоритм никогда не возвращается, чтобы отменить принятое решение. Этот алгоритм работает по принципу «сверху вниз».

Основное преимущество этого алгоритма:

  1. Алгоритм описать проще .
  2. Этот алгоритм может работать лучше, чем другие алгоритмы (но не во всех случаях).

Возможное решение

Возможное решение - это то, которое обеспечивает оптимальное решение проблемы.

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

  1. Для начала набор решений (содержащий ответы) пуст.
  2. На каждом шаге в набор решений добавляется элемент.
  3. Если набор решений возможен, текущий элемент сохраняется.
  4. В противном случае товар отклоняется и больше не рассматривается.

Пример - жадный подход

 Проблема: вы должны изменить сумму, используя минимально возможное количество монет. Сумма: 28 долларов Доступные монеты: 5 долларов монета 2 доллара монета 1 доллар

Решение:

  1. Создайте пустой набор решений = ().
  2. монеты = (5, 2, 1)
  3. сумма = 0
  4. Пока сумма 28, проделайте следующее.
  5. Выберите монету C из таких монет, чтобы sum + C <28.
  6. Если C + sum> 28, решение не возвращается.
  7. В противном случае сумма = сумма + C.
  8. Добавьте C в набор решений.

До первых 5 итераций набор решений содержал 5 монет по 5 долларов. После этого мы получаем монету 1 доллар 2 и, наконец, монету 1 доллар.

Жадные приложения алгоритмов

  • Выбор Сортировка
  • Проблема с рюкзаком
  • Минимальное связующее дерево
  • Проблема кратчайшего пути с одним источником
  • Проблема с расписанием работы
  • Алгоритм минимального связующего дерева Прима
  • Минимальный алгоритм связующего дерева Краскала
  • Алгоритм минимального остовного дерева Дейкстры
  • Кодирование Хаффмана
  • Алгоритм Форда-Фулкерсона

Интересные статьи...