Отрицательные циклы во взвешенных орграфах: различия между версиями

Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией <math>wt: E \rightarrow \mathbb{R} \;</math>. Стоимость, wt(P), пути P в графе G равна сумме стоимостей ребер, входящих в P. Простой путь C, начальная и конечная вершины которого совпадают, называется [[цикл|циклом]]. Если wt(C) < 0, то C называется [[отрицательный цикл|отрицательным циклом]]. Необходимо определить, существует ли подобный цикл в данном орграфе G с ребрами вещественной стоимости, и если существует – вывести этот цикл.

В случае орграфов общего вида лучшим алгоритмом для решения задачи нахождения отрицательного цикла (или вычисления дерева кратчайших путей в случае, если такого цикла не существует) является классический [[алгоритм Форда|алгоритм Беллмана-Форда]] с временем исполнения O(nm) (см, например, [1]). Другие алгоритмы с той же временной сложностью приводятся в [4, 7, 12, 13]. Кроме того, в [11, глава 7] описано расширение алгоритма Беллмана-Форда, которое помимо обнаружения существующих отрицательных циклов и вывода их (при наличии) строит дерево кратчайших путей с корнем в некоторой вершине s, достигающих такие вершины u, у которых кратчайшие пути s-u не содержат отрицательного цикла. Для случая, когда стоимости дуг являются целыми числами не менее <math>- L (L \ge 2) \;</math>, в [6] предложен более оптимальный алгоритм, исполняющийся за время <math>O(m \sqrt{n} log \; L)</math> и основанный на битовом масштабировании.

Простой детерминированный алгоритм с ожидаемым временем исполнения <math>O(n^2 log \; n)</math> с высокой вероятностью был приведен в [10]; он предназначен для широкого класса распределений входных данных, у которых стоимости ребер выбираются случайным образом в соответствии с независимой от конечных точек моделью (эта модель включает общий случай, при котором все стоимости ребер выбираются независимым образом из одного и того же распределения).

Лучшие результаты были получены для нескольких важных классов разреженных орграфов (т.е. орграфов, имеющих m = O(n) ребер) – [[таких как планарный граф|планарные]] и [[внешнепланарный граф|внешнепланарные]] орграфы, орграфы малого рода и малой [[древесная ширина графа|древесной ширины]].

Для разреженных орграфов общего вида в [8] был предложен алгоритм для решения задачи нахождения отрицательного цикла за время <math>O(n + \tilde{ \gamma } ^{1.5} log \; \tilde{ \gamma } )</math>, где <math>\tilde{ \gamma } \;</math> – топологическая мера входного разреженного орграфа G, значение которой меняется от 1 до <math>\Theta (n) \;</math>. Неформально <math>\tilde{ \gamma } \;</math> представляет минимальное количество внешнепланарных подграфов, удовлетворяющих определенным свойствам отделимости и полученных в результате декомпозиции графа G. В частности, <math>\tilde{ \gamma } \;</math> пропорционально <math>\gamma (G) + q \;</math>, где G предполагается вложенным в ориентируемую поверхность рода <math>\gamma (G) \;</math> таким образом, чтобы минимизировать количество q граней, совместно покрывающих все вершины. Например, если граф G является внешнепланарным, то <math>\tilde{ \gamma } = 1 \;</math>, в результате для такого случая получаем оптимальный алгоритм с временем исполнения O(n). Алгоритм в [8] не требует необходимого наличия такого вложения входного графа. В той же статье показано, что случайные графы <math>G_{n,p} \;</math> с пороговой функцией 1/n являются планарными с вероятностью 1, а ожидаемое значение <math>\tilde{ \gamma } \;</math> для них равно O(1). Кроме того, в [8] предложено эффективное распараллеливание алгоритма на базе модели вычислений CREW PRAM.

Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [9] предложен алгоритм с временем исполнения <math>O(n^{4/3} \; log (nL))</math>. В случае ребер с вещественными значениями стоимости алгоритм с временем исполнения <math>O(n \; log^3 \; n)</math> можно найти в работе [5].

Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем исполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает серийно-параллельные графы (t = 2) и внешнепланарные графы (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2].

Нахождение отрицательных циклов в орграфах представляет собой фундаментальную задачу комбинаторной и сетевой оптимизации, охватывающую широкий спектр приложений, включая следующие: нахождение кратчайшего пути, элементов двумерной упаковки, потоков минимальной стоимости, минимального соотношения стоимости и времени, а также верификация модели, создание компиляторов, разработка программного обеспечения, проектирование СБИС, планирование, производство интегральных схем, программирование с учетом ограничений и обработка изображений. Скажем, изоляция циклов отрицательной обратной связи исключительно важна при проектировании СБИС. Оказывается, такие циклы соответствуют циклам с отрицательной стоимостью в так называемом «графе коэффициентов усиления» схемы. В процессе программирования с учетом ограничений необходимо проверять применимость множеств ограничений. Системы разностных ограничений могут быть представлены в виде графов ограничений, и можно показать, что такая система является применимой в том и только том случае, если в соответствующем графе ограничений не имеется циклов с отрицательной стоимостью. В планировании с нулевым уровнем предварительных знаний задача определения того факта, существует ли для данной системы достоверный план, может быть сведена к нахождению отрицательных циклов в соответствующим образом определенном графе. Дополнительную информацию об этом и других вариантах применения можно найти в [1, 12, 14].

 

Задача нахождения отрицательного циклв тесно связана с задачей нахождения кратчайшего пути. Существование отрицательных стоимостей ребер делает решение задачи нахождения отрицательных циклов или вычисления дерева кратчайших путей более сложной и требует больше времени по сравнению с решением задачи нахождения дерева кратчайших путей в орграфах с неотрицательными стоимостями ребер. В качестве примера можно рассмотреть орграфы с вещественными стоимостями ребер и сравним алгоритм с временем исполнения O(nm) для первого случая с алгоритмом с временем O(m + n log n) для второго (алгоритмом Дейкстры, реализованным с эффективной очередью с приоритетами; см., например, [1]).

Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [3]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер.

== Наборы данных ==

Генераторы наборов данных и семейств начальных условий описаны в работе [4] и доступны на сайте http://www.avglab.com/ andrew/soft.html. Там же доступен код, используемый в [ ].

* ''[[Алгоритм поиска кратчайших путей в разреженных графах]]

* ''[[Алгоритм поиска кратчайших путей при помощи матричного произведения]]