Введение в жадный алгоритм

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

Что такое жадный алгоритм?

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

Определение основной концепции

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

Типы проблем

  1. Проблема минимизации: найти решение проблемы легко, если выполнены все условия. Однако, когда эта задача требует минимального результата, она называется проблемой минимизации.
  2. Проблема максимизации: проблема, которая требует максимального результата, известна как проблема максимизации.
  3. Проблема оптимизации: проблема называется проблемой оптимизации, когда она требует минимального или максимального результата.

Типы решений

  1. Возможное решение: теперь, когда возникает проблема, у нас есть много вероятных решений этой проблемы. Тем не менее, принимая во внимание условие, установленное для этой проблемы, мы выбираем решения, которые удовлетворяют данному условию. Такие решения, которые помогают нам получить результаты, удовлетворяющие данному условию, называются выполнимым решением .
  2. Оптимальное решение: решение называется оптимальным, когда оно уже выполнимо и достигает цели проблемы; лучший результат. Эта цель может быть как минимальным, так и максимальным результатом. Здесь следует отметить, что любая проблема будет иметь только одно оптимальное решение.

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

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

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

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

Где алгоритм Greedy работает лучше всего?

Алгоритм жадности может быть применен к перечисленным ниже проблемам.

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

преимущества

Самое большое преимущество алгоритма Greedy перед другими заключается в том, что он прост в реализации и очень эффективен в большинстве случаев.

Недостатки

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

  • Проблема с рюкзаком : Наиболее известная под названием проблема с рюкзаком - это повседневная проблема, с которой сталкиваются многие люди. Скажем, у нас есть набор предметов, и каждый из них имеет различный вес и ценность (прибыль) для наполнения в контейнер или должен собираться таким образом, чтобы общий вес был меньше или равен весу контейнера, в то время как общая прибыль максимальна,

Вывод

Жадный алгоритм лучше всего применять, когда нужно решение в режиме реального времени, а приблизительные ответы «достаточно хороши». Понятно, что жадный алгоритм минимизирует время, обеспечивая при этом оптимальное решение, поэтому его более целесообразно использовать в ситуации, когда требуется меньше времени. После прочтения этой статьи можно было бы иметь представление о жадных алгоритмах. Кроме того, в этом посте объясняется, почему он считается лучшей платформой, которая решает практически все задачи программирования, а также помогает вам выбрать наиболее оптимальное решение в данный момент времени.

Однако, с грубой стороны, для применения теории жадного алгоритма нужно усердно работать, чтобы знать правильные вопросы. Хотя это научная концепция, которая имеет логику, она также имеет суть творчества.

Рекомендуемые статьи

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

  1. Алгоритм в программировании
  2. Что такое Perl?
  3. Введение в алгоритм
  4. Что такое Agile Sprint?

Категория:

Разработка программного обеспечения