Динамическое программирование
Наше изучение алгоритмических методов началось с жадных алгоритмов, которые в определенном смысле представляют наиболее естественный подход к разработке алгоритма.
Как вы видели, столкнувшись с новой вычислительной задачей, иногда можно легко предложить для нее несколько возможных жадных алгоритмов; проблема в том, чтобы определить, дают ли какие-либо из этих алгоритмов верное решение задачи во всех случаях.
В таких случаях важно иметь наготове другие методы. Принцип «разделяй и властвуй» иногда выручает, однако реализации этого принципа, которые мы видели в предыдущей главе, часто недостаточно эффективны для сокращения экспоненциального поиска «грубой силой» до полиномиального времени.
Как было замечено в главе 5, его применения чаще позволяют сократить излишне высокое, но уже полиномиальное время выполнения до более быстрого.
В этой главе мы обратимся к более мощному и нетривиальному методу разработки алгоритмов — динамическому программированию.
Охарактеризовать динамическое программирование будет проще после того, как вы увидите его в действии, но основная идея базируется на интуитивных представлениях, лежащих в основе принципа «разделяй и властвуй», и по сути противоположна жадной стратегии: алгоритм неявно исследует пространство всех возможных решений, раскладывает задачу на серии подзадач, а затем строит правильные решения подзадач все большего размера.
В некотором смысле динамическое программирование может рассматриваться как метод, работающий в опасной близости от границ перебора «грубой силой»: хотя оно систематически прорабатывает большой набор возможных решений задачи, это делается без явной проверки всех вариантов.
Именно из-за этой необходимости тщательного выдерживания баланса динамическое программирование бывает трудно освоить; как правило, вы начинаете чувствовать себя уверенно только после накопления немалого практического опыта.
Разработка алгоритма динамического программирования для этой задачи будет проводиться в два этапа: сначала как рекурсивная процедура, которая сильно напоминает поиск «грубой силой», а затем, после переосмысления этой процедуры, — как итеративный алгоритм, который строит решения последовательно увеличивающихся подзадач.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу