Какой алгоритм я должен использовать, чтобы найти минимальный поток на орграфе, где существуют нижние, но не верхние границы потока?

Question

Какой алгоритм я должен использовать, чтобы найти минимальный поток на орграфе, где есть нижние границы, но не верхние границы потока? Например, этот простой пример:

В литературе это проблема минимальных затрат. Однако в моем случае стоимость такая же, как и ненулевая нижняя граница потока, необходимого для каждого ребра, поэтому я сформулировал вопрос, как указано выше. В литературе вопрос будет таким: каков наилучший алгоритм для нахождения минимального потока затрат для ориентированного ациклического графа с одним источником / одним стоком, в котором каждое ребро имеет бесконечную емкость, ненулевую нижнюю границу потока и стоимость равна нижней границе потока.

Из моего исследования кажется, что основной способ, которым люди справляются с любой минимальной стоимостью любой сети, состоит в том, чтобы определить проблему как проблему типа LP и решить ее таким образом. Моя интуиция, однако, заключается в том, что отсутствие верхних границ потока, т. Е. Наличие ребер с бесконечными емкостями, облегчает проблему, поэтому мне было интересно, есть ли алгоритм, специально предназначенный для этого случая, использующий больше "графических" методов, чем симплекс-метод и т. Д., и др.

Я имею в виду, если все затраты и нижние границы равны 1, как указано выше... тогда мы ищем поток, который покрывает все ребра, подчиняется правилам потока и не продвигает слишком большой поток через любой путь от s до t, Мне просто кажется, что для этого не нужно требовать решения для LP, и, действительно, в статье в Википедии о минимальных потоках затрат говорится, что "если ограничение емкости будет устранено, проблема сводится к проблеме кратчайшего пути", но я думаю, что они говорят о случай, когда все нижние оценки равны нулю.

Также есть ли где-нибудь открытый код C/C++ для минимального потока затрат? По поиску того, что доступно, я обнаружил, что я могу либо сам решить проблему как проблему LP и решить ее с помощью решателя LP с открытым исходным кодом, либо я мог бы использовать LEMON, который предоставляет несколько алгоритмов для минимизации затрат. Насколько я могу судить, библиотека графов наддува не включает реализацию.

Есть ли еще что-нибудь?

Answer 1

При отсутствии верхних границ самый простой способ - самый простой в реализации, понимании и достаточно эффективном - найти минимальный поток графа состоит в следующем:

1. Найдите выполнимый поток, т.е. поток, который удовлетворяет правилам потока и нижним пределам потока, но не обязательно является минимальным потоком. Это может быть достигнуто путем прохождения графа в глубину, отслеживания текущего пути во время прохождения и при посещении ранее обнаруженного узла или t, целевого узла, увеличения потока на текущем пути с максимальным меньшим привязка неудовлетворенных ребер на текущем пути вплоть до t.

2. Превратите допустимый поток в минимальный поток, решив проблему максимального потока. Вам нужно найти максимальный поток на графике, который имеет пропускную способность, равную потоку (e) - нижняя граница (e), где поток (e) означает поток из возможного потока. Этот максимальный поток, вычтенный из возможного потока, будет минимальным потоком.

Версия выше также может быть выполнена в случае, когда график также имеет верхние границы потока. В этом случае шаг 1. является более сложным, но может быть решен путем выполнения начального вычисления максимального потока на специально построенном графике.

Answer 2

Написание решателя нетривиально.

Смотрите библиотеку LEMON (часть COIN-OR). Он имеет ряд высоко оптимизированных алгоритмов для решения проблемы минимальных затрат. Вы можете выбрать, какой алгоритм лучше всего работает с вашими данными.

См. http://lemon.cs.elte.hu/trac/lemon для получения информации о LEMON.

См. http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html для получения подробной информации о минимальной стоимости сетевого потока.

Answer 3

Добавьте все "нижние границы" потоков на каждом ребре: в любом случае это будет необходимо для любого возможного решения.

Для каждого узла n в топологическом порядке (т.е. по краям) из раковины t, если сумма S- из того, что идет в краю, больше, чем сумма S+ из того, что выходит, затем добавить поток S+ - S- по всем краям кратчайшего пути между s а также t (составьте список кратчайшего пути, делая это для эффективности).

Затем у вас есть "минимальное" назначение (в том смысле, что оно необходимо в каждом возможном решении), такое как S+ - S- является неотрицательным в каждом узле, и минимальная емкость удовлетворяется на каждом ребре.

Затем проблема сводится к задаче с несколькими потоками на той же структуре графа:

• источник тот же;
• нет предела мощности;
• каждый узел, где S+ - S- строго положительно становится раковиной с требуемым потоком S+ - S-,
• начальная раковина (которая имела требуемый поток F) становится раковиной с потоком F - S- если F-S- неотрицательно (иначе начальное ограничение будет удовлетворено любым решением).

Изменить: для вашей проблемы график выглядит следующим образом

     x1 -- x2
   /   \     \
 s      \     t
   \     \   /
     x3 -- x4

с минимальной емкостью 1 для каждого ребра, и я предполагаю, что минимальный поток не требуется в приемнике t,

Сначала присвойте 1 каждому ребру.

Различия S+ - S- для каждого узла (кроме, конечно, s а также t) является:

x1: 1
x2: 0
x3: 0
x4: -1

единственный минус для x4; мы добавляем 1 к каждому краю на кратчайшем пути из x4 в tв таком случае к краю (x4, t),

Сейчас S+ - S- неотрицателен для каждого узла и положителен только для x1; проблема сводится к многопотоковой задаче (в этом случае это простая задача потока), где запрошенный поток 1 в x1и источник до сих пор s,