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

Ответ 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.