Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей

Фундаментальные циклы

 

Компактное представление пространства дает его базис. Если выписать все простые циклы графа , то это в большинстве случаев не будет его базисом, так как некоторые из этих циклов могут быть суммами других (см. пример на. Построить базис пространства , состоящий из простых циклов, можно следующим образом. Выберем в графе какой-нибудь каркас . Пусть - все ребра графа , не принадлежащие . Если добавить к ребро , то в полученном графе образуется единственный (простой) цикл . Таким образом, получаем семейство из циклов, они называются фундаментальными цикламиотносительно каркаса .

Теорема 2. Множество всех фундаментальных циклов относительно любого каркаса графа образует базис пространства циклов этого графа.Доказательство. Зафиксируем некоторый каркас и рассмотрим фундаментальные циклы относительно этого каркаса. В каждом из этих циклов имеется ребро , принадлежащее данному циклу и не принадлежащее никакому из остальных. Поэтому при сложении этого цикла с другими фундаментальными циклами данное ребро не "уничтожится" - оно будет присутствовать в суммарном графе. Следовательно, сумма различных фундаментальных циклов никогда не будет пустым графом, то есть фундаментальные циклы линейно независимы.Покажем теперь, что любой квазицикл графа является суммой фундаментальных циклов. Действительно, пусть - такой квазицикл. Пусть - все ребра , не принадлежащие . Рассмотрим граф . Каждое из ребер , , входит ровно в два слагаемых этой суммы - в и в . Следовательно, при сложении все эти ребра уничтожатся. Все остальные ребра, присутствующие в графах-слагаемых, принадлежат . Значит, - подграф графа . Так как все слагаемые являются квазициклами, значит, - тоже квазицикл. Но в нет циклов, поэтому имеется единственная возможность: , откуда получаем .Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его каркас. Так как каркас содержит ребер, где - число компонент связности графа, то эта размерность равна . Это число называют цикломатическим числом графа.

ПОТОКИ В СЕТЯХ

Сетью называется граф, элементам которого поставлены в соответст­вие некоторые параметры. Далее элементы множества N будем называть узлами, а множества А - дугами. Пусть каждой дуге некоторой сети G = [ N, а] поставлено в соответствие неотрицательное (действительное) число, называемое пропускной способностью дуги . Функ­ция С, отображающая множество А в множество неотрицательных чисел, называетсяфункцией пропускной способности. Пусть s и t - два различных узла из N. Стационарный поток величины v из s в t в сети [ N, а] есть функция f, отображающая множество А в множество неотрицательных чисел, удовлетворяющая линейным уравнениям и неравенствам

(4)

для всех , (5)

где («после x»), («перед x»)

Будем называть узел s- источником, узел t- стоком, а остальные уз­лы - промежуточными.

Если дан поток f, то число f( x, y) называется дуговым пото­ком f( x, y) или потоком по дуге (х,у). Поскольку f=0 и v=0 удовлетво­ряют условиям (4) и (5), вопрос о существовании потока не возникает. Система уравнений (4) избыточна, так как складывая все строки ее матри­цы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

Потоком в сети [ N, A] или [ N, C] назовем функцию f, сопоставляющую каж­дому ребру (х,у) сети целое число f( x, y)и обладающую следующимисвойствами:

(кососимметрия),

(допустимость).

Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей

Дана сеть G, состоящая из N вершин и M рёбер. У каждого ребра (вообще говоря, ориентированному, но по этому поводу см. ниже) указана пропускная способность (целое неотрицательное число) и стоимость единицы потока вдоль этого ребра (некоторое целое число). В графе указан исток S и сток T. Даётся некоторая величина K потока, требуется найти поток этой величины, причём среди всех потоков этой величины выбрать поток с наименьшей стоимостью ("задача min-cost-flow").

Иногда задачу ставят немного по-другому: требуется найти максимальный поток наименьшей стоимости ("задача min-cost-max-flow").

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

Описание

Алгоритм очень похож на алгоритм Эдмондса-Карпа вычисления максимального потока.

Простейший случай

Рассмотрим для начала простейший случай, когда граф - ориентированный, и между любой парой вершин не более одного ребра (если есть ребро (i,j), то ребра (j,i) быть не должно).

Пусть Uij - пропускная способность ребра (i,j), если это ребро существует. Пусть Cij - стоимость единицы потока вдоль ребра (i,j). Пусть Fij - величина потока вдоль ребра (i,j), изначально все величины потоков равны нулю.

Модифицируем сеть следующим образом: для каждого ребра (i,j) добавим в сеть так называемое обратное ребро (j,i) с пропускной способностью Uji= 0 и стоимостью Cji = - Cij. Поскольку, по нашему предположению, ребра (j,i) до этого в сети не было, то модифицированная таким образом сеть по-прежнему не будет мультиграфом. Кроме того, на всём протяжении работы алгоритма будем поддерживать верным условие: Fji = - Fij.

Определим остаточную сеть для некоторого зафиксированного потока F следующим образом (собственно, так же, как и в алгоритме Форда-Фалкерсона): остаточной сети принадлежат только ненасыщенные рёбра (т.е. у которых Fij < Uij), а остаточную пропускную способность каждого такого ребра как UPIij = Uij - Fij.

Собственно алгоритм min-cost-flow заключается в следующем. На каждой итерации алгоритма находим кратчайший путь в остаточной сети из S в T (кратчайший относительно стоимостей Cij). Если путь не был найден, то алгоритм завершается, поток F - искомый. Если же путь был найден, то мы увеличиваем поток вдоль него настолько, насколько это возможно (т.е. проходим вдоль этого пути, находим минимальную остаточную пропускную способность MIN_UPI среди рёбер этого пути, и затем увеличиваем поток вдоль каждого ребра пути на величину MIN_UPI, не забывая уменьшать на такую же величину поток вдоль обратных рёбер). Если в какой-то момент величина потока достигла величины K (данной нам по условию величины потока), то мы также останавливаем алгоритм (следует учесть, что тогда на последней итерации алгоритма при увеличении потока вдоль пути нужно увеличивать поток на такую величину, чтобы итоговый поток не превзошёл K, но это выполнить легко).

Нетрудно заметить, что если положить K равным бесконечности, то алгоритм найдёт максимальный поток минимальной стоимости, т.е. один и тот же алгоритм без изменений решает обе задачи min-cost-flow и min-cost-max-flow.

Другие способы описания

1. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

[править]Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

 

 

Детерминированный конечный автомат

· Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

 

· Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: , где:

· S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

[править]Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

24

Понятие конечного детерминированного автомата

К.Д.А. называется система , где - алфавит состояний, – входной алфавит, – выходной алфавит. Множества S, X, Y – конечные.

– функция переходов,

– функция выходов.

Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным.

4.2 Способы задания автоматов.

1.Таблица переходов–выходов.

S\X		…		…
M
M

2.С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .

Этой дуге приписывается пометка :

Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.

3.С помощью канонических уравнений:

 

в момент t=1 автомат находится в начальном состоянии . В каждый момент t=1,2,3,… дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала выдает выходной сигнал из множества Y, согласно функции выходов l , а затем меняет свое состояние на s(t+1) согласно функции переходов d.

Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.

После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях ,, ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом "запомнить". В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t.

Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:

 

 

Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:

={"на первом такте поступил 0"};

={"на первом такте поступила 1"}.

И –начальное состояние.

Построим таблицу переходов–выходов:

 

Для нарисуем диаграмму Мура:

И дополним таблицу переходов–выходов:

Свойства алгоритмов

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

Фундаментальные циклы

 

Компактное представление пространства дает его базис. Если выписать все простые циклы графа , то это в большинстве случаев не будет его базисом, так как некоторые из этих циклов могут быть суммами других (см. пример на. Построить базис пространства , состоящий из простых циклов, можно следующим образом. Выберем в графе какой-нибудь каркас . Пусть - все ребра графа , не принадлежащие . Если добавить к ребро , то в полученном графе образуется единственный (простой) цикл . Таким образом, получаем семейство из циклов, они называются фундаментальными цикламиотносительно каркаса .

Теорема 2. Множество всех фундаментальных циклов относительно любого каркаса графа образует базис пространства циклов этого графа.Доказательство. Зафиксируем некоторый каркас и рассмотрим фундаментальные циклы относительно этого каркаса. В каждом из этих циклов имеется ребро , принадлежащее данному циклу и не принадлежащее никакому из остальных. Поэтому при сложении этого цикла с другими фундаментальными циклами данное ребро не "уничтожится" - оно будет присутствовать в суммарном графе. Следовательно, сумма различных фундаментальных циклов никогда не будет пустым графом, то есть фундаментальные циклы линейно независимы.Покажем теперь, что любой квазицикл графа является суммой фундаментальных циклов. Действительно, пусть - такой квазицикл. Пусть - все ребра , не принадлежащие . Рассмотрим граф . Каждое из ребер , , входит ровно в два слагаемых этой суммы - в и в . Следовательно, при сложении все эти ребра уничтожатся. Все остальные ребра, присутствующие в графах-слагаемых, принадлежат . Значит, - подграф графа . Так как все слагаемые являются квазициклами, значит, - тоже квазицикл. Но в нет циклов, поэтому имеется единственная возможность: , откуда получаем .Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его каркас. Так как каркас содержит ребер, где - число компонент связности графа, то эта размерность равна . Это число называют цикломатическим числом графа.

ПОТОКИ В СЕТЯХ

Сетью называется граф, элементам которого поставлены в соответст­вие некоторые параметры. Далее элементы множества N будем называть узлами, а множества А - дугами. Пусть каждой дуге некоторой сети G = [ N, а] поставлено в соответствие неотрицательное (действительное) число, называемое пропускной способностью дуги . Функ­ция С, отображающая множество А в множество неотрицательных чисел, называетсяфункцией пропускной способности. Пусть s и t - два различных узла из N. Стационарный поток величины v из s в t в сети [ N, а] есть функция f, отображающая множество А в множество неотрицательных чисел, удовлетворяющая линейным уравнениям и неравенствам

(4)

для всех , (5)

где («после x»), («перед x»)

Будем называть узел s- источником, узел t- стоком, а остальные уз­лы - промежуточными.

Если дан поток f, то число f( x, y) называется дуговым пото­ком f( x, y) или потоком по дуге (х,у). Поскольку f=0 и v=0 удовлетво­ряют условиям (4) и (5), вопрос о существовании потока не возникает. Система уравнений (4) избыточна, так как складывая все строки ее матри­цы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

Потоком в сети [ N, A] или [ N, C] назовем функцию f, сопоставляющую каж­дому ребру (х,у) сети целое число f( x, y)и обладающую следующимисвойствами:

(кососимметрия),

(допустимость).

Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей

Дана сеть G, состоящая из N вершин и M рёбер. У каждого ребра (вообще говоря, ориентированному, но по этому поводу см. ниже) указана пропускная способность (целое неотрицательное число) и стоимость единицы потока вдоль этого ребра (некоторое целое число). В графе указан исток S и сток T. Даётся некоторая величина K потока, требуется найти поток этой величины, причём среди всех потоков этой величины выбрать поток с наименьшей стоимостью ("задача min-cost-flow").

Иногда задачу ставят немного по-другому: требуется найти максимальный поток наименьшей стоимости ("задача min-cost-max-flow").

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

Описание

Алгоритм очень похож на алгоритм Эдмондса-Карпа вычисления максимального потока.

Простейший случай

Рассмотрим для начала простейший случай, когда граф - ориентированный, и между любой парой вершин не более одного ребра (если есть ребро (i,j), то ребра (j,i) быть не должно).

Пусть Uij - пропускная способность ребра (i,j), если это ребро существует. Пусть Cij - стоимость единицы потока вдоль ребра (i,j). Пусть Fij - величина потока вдоль ребра (i,j), изначально все величины потоков равны нулю.

Модифицируем сеть следующим образом: для каждого ребра (i,j) добавим в сеть так называемое обратное ребро (j,i) с пропускной способностью Uji= 0 и стоимостью Cji = - Cij. Поскольку, по нашему предположению, ребра (j,i) до этого в сети не было, то модифицированная таким образом сеть по-прежнему не будет мультиграфом. Кроме того, на всём протяжении работы алгоритма будем поддерживать верным условие: Fji = - Fij.

Определим остаточную сеть для некоторого зафиксированного потока F следующим образом (собственно, так же, как и в алгоритме Форда-Фалкерсона): остаточной сети принадлежат только ненасыщенные рёбра (т.е. у которых Fij < Uij), а остаточную пропускную способность каждого такого ребра как UPIij = Uij - Fij.

Собственно алгоритм min-cost-flow заключается в следующем. На каждой итерации алгоритма находим кратчайший путь в остаточной сети из S в T (кратчайший относительно стоимостей Cij). Если путь не был найден, то алгоритм завершается, поток F - искомый. Если же путь был найден, то мы увеличиваем поток вдоль него настолько, насколько это возможно (т.е. проходим вдоль этого пути, находим минимальную остаточную пропускную способность MIN_UPI среди рёбер этого пути, и затем увеличиваем поток вдоль каждого ребра пути на величину MIN_UPI, не забывая уменьшать на такую же величину поток вдоль обратных рёбер). Если в какой-то момент величина потока достигла величины K (данной нам по условию величины потока), то мы также останавливаем алгоритм (следует учесть, что тогда на последней итерации алгоритма при увеличении потока вдоль пути нужно увеличивать поток на такую величину, чтобы итоговый поток не превзошёл K, но это выполнить легко).

Нетрудно заметить, что если положить K равным бесконечности, то алгоритм найдёт максимальный поток минимальной стоимости, т.е. один и тот же алгоритм без изменений решает обе задачи min-cost-flow и min-cost-max-flow.