Задача нахождения потока минимальной стоимости. Алгоритм Басакера-Гоуэна (постановка задачи, граф модифицированных стоимостей)

↑

⇐ ПредыдущаяСтр 20 из 28Следующая ⇒

25. Задача нахождения потока минимальной стоимости. Алгоритм Басакера-Гоуэна (постановка задачи, граф модифицированных стоимостей)

Пусть дополнительно каждой дуге сети приписан неотрицательный вес c_ij, равный стоимости транспортировки единицы потока по дуге (i, j)∈ E. Задача поиска s-t-потока заданной мощности v и минимальной стоимости имеет вид:

Алгоритм Басакера-Гоуэна:

Шаг 0. Положить все дуговые потоки и, следовательно, величину по-тока v = 0.

Шаг 1. Определить модифицированные дуговые стоимости , зави-сящие от величины найденного потока

Шаг 2. Найти путь из s в t минимальной длины (полагая длину каждой дуги (i, j), равной, C^*_ij ) и увеличить на единицу поток по этому пути. Если величина нового потока равна v, то алгоритм заканчивает работу. В противном случае перейти на шаг 1.

Заметим, что, когда задана неориентированная сеть с выделенными ис-точником s и стоком t, ориентация ребер, инцидентных s и t, определяется однозначно.

26. Задача нахождения потока минимальной стоимости. Алгоритм Клейна (постановка задачи, граф модифицированных стоимостей)

Пусть дополнительно каждой дуге сети приписан неотрицательный вес c_ij, равный стоимости транспортировки единицы потока по дуге (i, j)∈ E. Задача поиска s-t-потока заданной мощности v и минимальной стоимости имеет вид:

Алгоритм Клейна:

Шаг 1. Найти произвольный допустимый s-t-поток величины v., в которой нужно увеличивать поток, пока он не станет равным v.)

Шаг 2. Определить модифицированные дуговые стоимости

Шаг 3. Найти в сети цикл отрицательной стоимости. (Процедура нахо-ждения отрицательных циклов описана в замечании 6.1.). Если отрица-тельного цикла нет, то найденный поток оптимален. Иначе увеличить поток по отрицательному циклу на величину δ = min{b_ij – x_ij, x_ji}, где минимум берется по всем дугам цикла, и перейти на шаг 2. (Если в сети существует несколько отрицательных циклов, то увеличить поток по каждому из них.)

Теорема 6.2. Поток величины v оптимален только тогда, когда в сети с модифицированными дуговыми стоимостями c*ij не существует отрицательных циклов.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте