На этом шаге мы рассмотрим динамическое программирование.
Наиболее общей формой называют процесс пошагового решения задач, когда на каждом шаге выбирается одно значение из множества допустимых на этом шаге, причем такое, которое оптимизирует заданную цель. В основе программирования лежит принцип оптимальности Беномена. Суть метода:
Часто не удается разбить задачу на небольшое количество подзадач, объединенное решение которых позволяет получить решение искомых задач.
Возникают 2 возможности:
- Можно попытаться разделить задачу на столько задач, сколько необходимо, затем каждую на еще более мелкие и т.д. Если алгоритм сведется к именно такой последовательности, то мы получим задачу с экспоненциальным временем решением.
- Иногда удается получить алгоритм с полиномиальным числом подзадач, и ту или иную приходиться решать многократно. Если бы мы отслеживали каждую подзадачу и просто отыскивали их решения, то мы бы получили полиномиальное решение.
Иногда проще создать таблицу решения всех подзадач независимо от того, нужна она или нет.
Заполнение таблиц - решение подзадач для получения решения определенной задачи - в теории алгоритмов получило название динамического программирования. Формы алгоритмов динамического программирования могут быть разными, общими могут быть лишь заполненные таблицы и порядок заполнения ее элементов.
На следующем шаге мы рассмотрим метод балансировки.
