Publicado el

6 Динамическое Программирование

Для решения таких задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая. При этом осуществляется переход к еще более простым и так далее, пока не доходят до тривиальной. Рассмотрим некий необратимый процесс производства и представим его в виде ориентированного и ациклического графа. Началом производства (первым состоянием) обозначим вершину графа $S$, а конец производства (последнее состояние) $T$.

динамическое программирование

На практике динамическое программирование может пригодиться вам всего лишь 1–2 раза в жизни, но сам концепт помогает по-другому посмотреть на работу с алгоритмами. В качестве примера рассмотрим задачу о коммивояжере. Вычислить значение оптимального решения с помощью метода восходящего анализа. Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231». Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно $N$. https://iintel.ru/ позволяет нам избежать повторений, путем запоминания промежуточных результатов. То есть путем запоминания результатов проблем, которые мы уже решили. Большее понимание принципов ДП приходит в процессе решения динамических задач и многое еще будет рассказано в разборах задач данного раздела. Иногда вместо «уродливое число» я буду использовать аббревиатуру УЧ.

Программная Реализация Алгоритма

Алгоритму нужно понять, по какому маршруту и в каком порядке доставить данные во все пункты назначения. По аналогии вы находите решение и для задач большой размерности. Да, это легко сказать, но универсального ключика под все задачи, к сожалению, нет.

Одномерное Динамическое Программирование

В выходной файл ваша программа должна поместить одно число — количество программ для робота. Пользуясь полученной информацией, построить оптимальное решение. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач. Так как гитара весит всего один килограмм, то она влезет уже на первом шаге. Поэтому в каждой ячейке первой строки напишем — стоимость гитары.

Что Такое Динамическое Программирование?

Вверху показан кратчайший путь из i в j (через вершины 2 и 5). Так как путь через вершину k не является кратчайшим, мы можем ограничить поиск кратчайшего пути вершинами 1,…,k-1. Внизу показан кратчайший путь из i в j, лежащий через вершину k. Этот путь из i в j можно составить из кратчайших путей из i в k и из k в j. Этот метод выглядит просто замечательно, но его производительность хуже некуда.