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

МИНОБРНАУКИ РФ[pic 1]

федеральное государственное бюджетное образовательное учреждение высшего образования

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Институт автоматики и информационных технологий

Кафедра «Информационные технологии»

ОТЧЕТ

о выполнении лабораторной работы №2 на тему

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

по дисциплине «Теоретические основы автоматизированного управления»

Самара 2022г.

Цель работы – освоение методов решения задач динамического программирования при прокладке наивыгоднейшего пути между двумя пунктами.

Вариант № 21

[pic 2]

Выполнение работы:

Требуется проложить путь, соединяющий два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис.1)

[pic 3]

Рисунок 1 - Графическая иллюстрация к задаче прокладки пути

Для начала нужно разделить процесс перехода из А в В на отдельные шаги  (один шаг – один отрезок), и оптимизировать управление по шагам. Разделим расстояние от А до В  в восточном направлении на  шесть частей, а в северном – на пять ( в принципе дробление может быть гораздо более мелким ). Тогда любой путь из А в В состоит из 6+5=11 отрезков, направленных на восток или север. Поставим на каждом из отрезков число, выражающее ( в каких-то условных единицах ) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна (рис.2)