Похожие презентации:
Исследование операций. Лекция 5
1.
Крамаренко К.Е.Кафедра ВС
2.
ДП - определяет оптимальное решение n-мернойзадачи путем ее декомпозиции на n этапов, каждый
из которых представляет подзадачу относительно
одной переменной.
3.
Основные элементы модели ДП:1. Определение этапов.
2. Определение
на каждом этапе вариантов
решения(альтернатив).
3. Определение состояний на каждом этапе.
4.
Вычисления в ДП выполняются рекуррентно в томсмысле, что оптимальное решение одной подзадачи
используется в качестве исходных данных для
следующей.
5.
212
7
5
8
1
8
3
9
6
7
5
13
4
9
6
7
6.
77
2
2
8
8
3
3
12
7
0
1
8
5
Этап f0-f1
8
9
7
5
5
4
4
12
12
5
5
17
17
6
6
9
7
6
13
Этап f1-f2
21
Этап f2-f3
7.
Этап 1:Кратчайший путь к узлу 2 равен 7 (из узла 1)
Кратчайший путь к узлу 3 равен 8 (из узла 1)
Кратчайший путь к узлу 4 равен 5 (из узла 1)
8.
Этап 2:Кратчайший
= min
путь к узлу 5