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

Реферат.Справочник
Контрольные работы по высшей математике
Найти путь минимальной длины между начальной и конечной вершинами сети методом динамического программирования

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

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

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

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Представим задачу о кратчайшем пути как многошаговый процесс принятия решения. Разделим задачу этапы:
- на первом этапе из узла 1 без промежуточных узлов можно попасть только в узлы 2 и 3;
- на втором этапе из узла 1 не более чем с одним промежуточным узлом можно попасть в узлы 4, 5;
- на третьем этапе не более чем с 2 промежуточными узлами – в узлы 6, 7, 8;
- на четвертом – в узел 9.
Пусть fkxi – кратчайшее расстояние от узла x1 до узла xi на этапе k, тогда рекуррентное уравнение Беллмана будет иметь вид:
fkxi=minj,i∈Gfk-1xj+uji,k=1, 2, 3, 4,f0x0=0
Этап 1.
Вычисляем расстояния от начального узла до узлов первого этапа:
f1x2=6,
f1x3=7.
Этап 2.
Вычисляем кратчайшие расстояния до узлов второго этапа, используя информацию, полученную на первом этапе:
f2x4=minf1x2+u24; f1x3+u34=min6+39; 7+37=44
f2x5=minf1x2+u25; f1x3+u35=min6+38; 7+36=43.
Этап 3

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу