Условие задачи
Найти самый длинный путь от A до G в сетевом графике:
Необходимо:
1. Заполнить вершины сетевого графика по правилу определения условных оптимумов с выделением соответствующих стрелок.
2. Выделить итоговый оптимальный путь.
3. Записать в ответ координаты оптимального пути (по буквам всех вершин пути) и его продолжительность.
Кратко ответьте на теоретические вопросы и продемонстрируйте ответ на примере своего решения:
1. В чем специфика задач динамического программирования? Покажите это на примере своего решения.
2. Что такое условный оптимум в задачах динамического программирования? Покажите это на примере своего решения.
Ответ
Динамическое программирование это метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. При решении каждой подзадачи находится ее оптимальное решение, которое является условным оптимумом по отношение к решению задачи в целом.
Пусть на некотором этапе было получено следующее решение задачи:
