Компьютеры и Интернет
Динамическое программирование, применительно к сфере компьютерных наук, описывает группу аналогичных компьютерных алгоритмов предназначенных для решения сложных задач путём разбиения задачи на множества более мелких проблем. Динамическое программирование работает с проблемами, которые являются либо перекрывающимися подзадачами, либо оптимальными подструктурами. Чтобы понять, как работает динамическое программирование, лучше понять концепцию этих двух терминов.
Перекрывающиеся подзадачи описывают сложные уравнения, которые, разбившись на более мелкие группы уравнений, повторно используют части более мелких уравнений более одного раза, чтобы получить ответ. Например, математическое уравнение, предлагаемое для вычисления всех возможных результатов с использованием набора чисел, может вычислять один и тот же результат много раз, вычисляя другие результаты только один раз. Динамическое программирование рассказывает об этой проблеме, что после вычисления результата в первый раз он должен сохранить этот результат и затем включить ответ в уравнение позже, а не вычислять его снова. При работе с длинными сложными процессами и уравнениями это экономит время и создаёт более быстрое решение, используя гораздо меньше шагов.
Оптимальные подструктуры создают решение, что бы найти лучший ответ на все подзадачи, а затем создают лучший общий ответ. После разбиения сложной проблемы на более мелкие проблемы, в которых компьютер использует математические системы, чтобы определить, что является лучшим ответом для каждой проблемы. Он вычисляет ответ из исходной проблемы начиная с меньшего ответа. Но в действительности с этим процессом существуют недостатки. В то время как он даёт решение, которое работает лучше математически, это может или не может быть лучшим решением в реальной жизни, в зависимости от типа проблемы и как она относится к реальному миру.
При любой из этих операций, динамического программирования, алгоритм пытается найти кратчайший путь к решению. Для этого он может принять один из двух подходов. Подход “сверху вниз” разбивает уравнение на более мелкие уравнения и использует ответы этих уравнений, когда это необходимо. Подход “снизу вверх” пытается решить маленькое математическое значение после перехода в уравнении вниз, а затем работает начиная свой путь вверх к величине. Оба подхода позволяют экономить время, но и динамическое программирование работает только тогда, когда исходная задача может разбиваться на более мелкие уравнения, которые в какой-то момент используются, чтобы решить уравнение.
