![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Динамическое программирование. Задача о построении кратчайшего пути на графе.
Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами: 0. Задача 1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: 2. Вывод уравнения Беллмана. 3. Решение семейства задач. 3.1. Находим более простые задачи и решаем их. 3.2 Находим значение функции Беллмана B(t) и Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи. Частным случаем задачи об оптимальном потоке является задача построения кратчайшего пути между двумя вершинами пути. Пусть дан граф Рассмотрим теперь сеть, вершина s которой является источником единичной интенсивности, t – стоком единичной интенсивности, остальные вершины – нейтральные. Дугам приписываются неограниченные пропускные способности, а стоимость перевозок по дуге полагается равной длине дуги. Для потока Пусть имеется некоторый конечный граф
|