Улучшенная реализация

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

Например, можно просто перебрать все вершины первой доли, и для каждой из них найти произвольное ребро, которое можно добавить в паросочетание, и добавить его. Даже такая простая эвристика способна ускорить алгоритм Куна в несколько раз.

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

В реализации изменится только код в функции main():

int main() {

... чтение графа ...

 

mt.assign (k, -1);

vector<char> used1 (n);

for (int i=0; i<n; ++i)

for (size_t j=0; j<g[i].size(); ++j)

if (mt[g[i][j]] == -1) {

mt[g[i][j]] = i;

used1[i] = true;

break;

}

for (int i=0; i<n; ++i) {

if (used1[i]) continue;

used.assign (n, false);

try_kuhn (i);

}

 

for (int i=0; i<k; ++i)

if (mt[i] != -1)

printf ("%d %d\n", mt[i]+1, i+1);

}

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

 

    Циркуляция (см. вики-конспекты)

Циркуляцией называется поток в сети   нулевой величины (см. рисунок 1).

Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)

То есть закон сохранения потока   должен выполняться для всех вершин графа, а значит нет нужды в истоке и стоке.

Содержание  [убрать]  1 Постановка задачи 2 Решение 3 Псевдокод 4 Источники

[Править]Постановка задачи

Рассмотрим сеть  , в которой про каждое ребро   известны величины:   — минимальная пропускная способность и   — максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.

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