Оглавление:
Определение - Что означает жадный алгоритм?
Жадный алгоритм - это алгоритмическая стратегия, которая делает лучший оптимальный выбор на каждой небольшой стадии, с целью, которая в конечном итоге приводит к глобально оптимальному решению. Это означает, что алгоритм выбирает наилучшее решение на данный момент без учета последствий. Он выбирает лучший немедленный результат, но не учитывает общую картину, поэтому считается жадным.
Техопедия объясняет жадный алгоритм
Жадный алгоритм работает, выбирая наилучший из возможных ответов на каждом шаге, а затем переходя к следующему шагу, пока не дойдет до конца, без учета общего решения. Он только надеется, что путь, который он выберет, является глобально оптимальным, но, как доказано снова и снова, этот метод не часто предлагает глобально оптимальное решение. На самом деле, вполне возможно, что наиболее оптимальные краткосрочные решения приводят к худшему из возможных глобальных результатов.
Думайте об этом, как о том, что в производственном бизнесе нужно много сокращений: в краткосрочной перспективе большие суммы экономятся на производственных затратах, но это в конечном итоге приводит к падению, поскольку качество ухудшается, что приводит к возврату продукта и низким продажам, когда клиенты знакомятся с «Дешевый» продукт. Но это не всегда так, есть много приложений, где жадный алгоритм работает лучше всего, чтобы найти или аппроксимировать глобально оптимальное решение, такое как построение дерева Хаффмана или дерева обучения принятию решений.
Например: выберите путь с наибольшей суммой. Жадный алгоритм выбрал бы синий путь в результате близорукости, а не оранжевый путь, который дает наибольшую сумму.
Компоненты:
- Набор кандидатов данных, который нуждается в решении
- Функция выбора, которая выбирает лучшего участника для окончательного решения
- Функция технико-экономического обоснования, которая помогает функции выбора, определяя, может ли кандидат участвовать в решении
- Целевая функция, которая присваивает значение частичному решению.
- Функция решения, которая указывает, что было найдено оптимальное решение
