Сравнение алгоритмов жадности, разделяй и властвуй и динамического программирования
Жадный алгоритм:
Жадный алгоритм определяется как метод решения задач оптимизации путем принятия решений, которые приводят к наиболее очевидной и непосредственной выгоде независимо от конечного результата. Это простой, интуитивно понятный алгоритм, который используется в задачах оптимизации.
Разделяй и властвуй Алгоритм:
Разделяй и властвуй — это алгоритмическая парадигма, в которой проблема решается с помощью стратегии «Разделяй, властвуй и комбинируй». Типичный алгоритм «разделяй и властвуй» решает проблему, используя следующие три шага:
Divide: This involves dividing the problem into smaller sub-problems.
Conquer: Solve sub-problems by calling recursively until solved.
Combine: Combine the sub-problems to get the final solution of the whole problem.
Динамическое программирование:
Динамическое программирование - это в основном оптимизация простой рекурсии. Везде, где мы видим рекурсивное решение, которое иногда повторяет вызовы одних и тех же входных состояний, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто хранить результаты подзадач, чтобы нам не приходилось пересчитывать их позже, когда это потребуется. Эта простая оптимизация снижает сложность времени с экспоненциальной до полиномиальной.
Жадный алгоритм против алгоритма «разделяй и властвуй» против динамического алгоритма:
| Сл.№ | Жадный алгоритм | Разделяй и властвуй | Динамическое программирование |
|---|---|---|---|
| 1 | Следует подходу «сверху вниз» | Следует подходу «сверху вниз» | Применяет подход «снизу вверх» |
| 2 | Используется для решения задачи оптимизации | Используется для решения проблемы принятия решения | Используется для решения задачи оптимизации |
| 3 | Оптимальное решение генерируется без повторного обращения к ранее сгенерированным решениям; таким образом, он избегает повторного вычисления | Решение подзадачи вычисляется рекурсивно более одного раза. | Решение подзадач вычисляется один раз и сохраняется в таблице для дальнейшего использования. |
| 4 | Он может генерировать или не генерировать оптимальное решение. | Используется для получения решения поставленной задачи, не стремится к оптимальному решению | Он всегда генерирует оптимальное решение. |
| 5 | Итеративный характер. | Рекурсивный характер. | Рекурсивный характер. |
| 6 | эффективно и быстро, чем разделяй и властвуй. | менее эффективен и медленнее. | эффективнее и быстрее, чем жадный. |
| 7 | дополнительная память не требуется. | требуется некоторая память. | требуется больше памяти для хранения подзадач для последующего использования. |
| 8 | Примеры: задача о дробном рюкзаке, Проблема выбора деятельности, Проблема последовательности выполнения заданий. | Примеры: сортировка слиянием, Быстрая сортировка, Умножение матриц Штрассена. | Примеры: 0/1 Рюкзак, Все пары кратчайший путь, Матрично-цепочное умножение. |