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

Лекция 7

Внешнеполитическое положение России после Октября 1917. Брестский мир и его последствия.

Перед Октябрем 1917 большевики обращались к народу с призывом «Конец войне! Мир!». Советское правительство обратилось ко всем воюющим странам заключить мир, на что откликнулась только Германия, т.к. она воевала на два фронта. Переговоры в Брест-Литовске, их возглавлял Троцкий, у к-го была инструкция затягивать переговоры, но при ультиматуме подписывать немедленно. В вопросе о мире не было единства: Ленин стоял за мир, объясняя тем, что вооружения, продовольствия нет. Оппозиция: левые коммунисты (Коллонтай, Бухарин) считали, что для молодого советского гос-ва позорно заключать мир с немецким кайзером. Троцкий, нарком иностранных дел, нарушил инструкцию. Переговоры затянулись, к удивлению делегации, Троцкий сказал, что мир подписан не будет, но и продолжать войну страна тоже не будет. Ультиматум Ленина (грозил выйти из партии и бороться как простой воин), переговоры возобновлены, возглавил Чичерин. Началось создание отрядов Рабоче-крестьянской Красной Армии (23 февраля). Требования советской партии ужесточены, но 3 марта 1918 в Бресте подписан мир с Германией.

Значение: выход советской России из Первой мировой войны, страна получила возможность организовать хозяйство и др. VII съезд коммунистической партии принял решение с секретным пунктом: при изменении условий прервать мир. В Германии правительство кайзера было свергнуто, в свою очередь советское правительство посчитало себя свободным по обязательствам заключенного мира (разрывает мир).

Последствия Брестского мира: левые эсеры подняли контрреволюционный мятеж в Ярославле, убийство германского посла Мирбаха в надежде сорвать Брестский мирный договор, арестован Дзержинский, введены военные части (латвийские стрелки), с помощью к-х мятеж левых эсеров был подавлен. Германия не пошла на разрыв отношений с РСФСР.

 

Как уже отмечалось, в некоторых случаях рекурсивное решение может оказаться очень трудоемким, так как в процессе его выполнения одна и та же задача может решаться несколько раз. Простой анализ примера вычисления дистанции Левенштейна позволяет выявить такие повторные вычисления. Например, функция вычислялась в шагах 7, 8, 7, 16 алгоритма.

Если в процессе выполнения рекурсивного алгоритма одна и та же задача решается несколько раз, то говорят, что алгоритм содержит перекрывающиеся подзадачи. Например, задача вычисления функции , рассмотренная выше, является перекрывающейся подзадачей задачи вычисления функции

Метод решения задачи оптимизации, реализующей рекурсивный алгоритм с перекрывающимися подзадачами, в котором каждая такая подзадача решается один раз, а ее результат сохраняется для последующего применения, называется динамическим программированием.

На рис. 1 приведен пример реализации алгоритма вычисления члена последовательности Фибоначчи методом динамического программирования.

 

 

Рис. 1. Функция вычисления члена последовательности Фибоначчи, реализующая алгоритм динамического программирования

 

Обратите внимание, что новой реализацией функции fibдля хранения промежуточных значений используется статический массив. Применение массива позволяете избежать повторных рекурсивных вычислений, которые были в реализации, представленной в пред. лекции.

Заметим, что задачи вычисления факториала и наибольшего общего делителя не имеет смысла решать методом динамического программирования, так как при их рекурсивном решении не образуются перекрывающиеся подзадачи и, следовательно, нет необходимости запоминать промежуточные вычисления.

Следует отметить, что рассматриваемый здесь метод является частью более общей теории динамического программирования, основы которой разработаны Р. Беллманом. Эта теория исследует процесс пошагового решения задач оптимизации, в котором на каждом шаге из множества допустимых решений выбирается одно, оптимизирующее заданную целевую функцию.