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

Это название, вероятно, не имеет смысла. Предположим следующее:

Обязателен B $5
C owes B $10
B должен D $15

В этой базовой ситуации есть три транзакции, но ее можно свести к двум транзакциям:

A дает D $5
C дает D $10

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

Ответ 1

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

A :  -5
B :   0
C : -10
D : +15

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

Ответ 2

Это может быть неэффективно, но вы можете использовать Integer Programming.

Прекомпретировать чистый поток в/из node i, то есть Fi = общая задолженность + сумма кредитов

Пусть M - большое число.

Пусть Yij - переменная решения, обозначающая сумму node я платит до node j (упорядоченные пары).

Пусть Xij - двоичная переменная, указывающая, что транзакция имела место между я и j (неупорядоченные пары)

Оптимизируйте следующее:

min sum_ {i, j} Xij

sum_ {j!= i} Yij = Fi

Yij + Yji = <= M * Xij

Ответ 3

Вы можете попробовать жадный метод. Итак,

Если A должен деньги B и B значит C, то A обязано C минимумом (A- > B, B- > C). А → В - = мин (А- > В, В- > С). Если после этой операции A- > B станет zero, вы удалите его. Loop, пока вы не сможете выполнить дальнейшую операцию, т.е. На графике нет cycles.:

do{
    bool stop = true;
    G.init() // initialize some sort of edge iterator
    while(edge = G.nextedge()){  //assuming nextedge will terminate after going through all edges once

        foreach(outedge in edge.Dest.Outedges){ //If there any node to 'move' the cost
            minowed = min(edge.value, outedge.value)
            G.edge(edge.Src, outedge.Dest).value += minowed
            edge.value -= minowed
            outedge.value -= minowed
            if(edge.value == 0) G.remove(edge)
            if(outedge.value == 0) G.remove(outedge)
            stop = false
        }
    }
}while(!stop)

Это сводится к практически удалению любых циклов из графика, чтобы сделать его DAG.

Ответ 4

Это типичный максимальный поток с минимальной стоимостью. Жадные методы все придут в ближайшее время.

В качестве примера мы используем следующую настройку:

Обязателен B $5
C owes B $10
C owes A $1
D должен E $5
E должен C $5

Тогда...

Рассчитайте "чистую стоимость" каждого человека - то есть, насколько этот человек должен другим, или сколько других человек должен этот человек. В нашем примере A ~ -4, B ~ 15, C ~ -6, D ~ -5, E ~ 0.
Чтобы упростить, мы создаем полностью связанный график для всех лиц. Нам фактически не нужно (мы можем создать двудольный граф), но здесь мы просто оставляем всю работу алгоритму.
Для графика присвойте value = 1 каждому ребру. Все ребра здесь имеют бесконечные емкости.
Создайте источник node. Источник node будет иметь направленные ребра от него всем лицам с отрицательными значениями. Края имеют стоимость = 0, а емкость = abs (значение человека). S- (4) → A, S- (6) → C, S- (5) → D. Затем создайте раковину node, node будет иметь направленные ребра от всех лиц с положительными значениями, указывающими на нее. Края к раковине будут иметь стоимость = 0 и емкость = abs (значение человека), то есть B- (15) → T
Выполнить алгоритм максимального потока/минимальной стоимости на графике. Каждый поток на внутренних ребрах преобразуется в одну транзакцию. Цель состоит в том, чтобы минимизировать транзакцию, чтобы каждый край имел стоимость = 1.