Минимизация фактов выплат/перевозок?

Question

[apodavalov]

Доброе время суток!


Сразу к делу.
Задача: Некоторая группа людей в количестве N человек, где каждый в разное время занимал у кого-то из этой же группы некоторую сумму денег. Необходимо выяснить каким минимальным количеством фактов выплат можно обойтись, чтобы раздать все долги. На входе подаются транзакции задолжностей. Например:


Вход:

7

D A 2

A D 10

A E 7

A F 6

B F 1

B G 5

C G 2


Выход:

5

A E 7

A F 7

A G 7

B D 2

C D 6


На данный момент я делаю следующее.

1) Ввожу понятие баланса. Изначально у всех баланс нулевой. При считывании очередной транзакции баланс того, кто должен уменьшается, баланс того, кому должны — увеличивается (оба на сумму задолжности).

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

3) Строится транспортная сеть: добавляется исток и соединяется ребрами с каждым поставщиком, максимальная пропускная способность каждого ребра равна значению отдачи, тоже самое делается с потребителями: от них строятся ребра к добавленному стоку. Максимальная пропускная способность каждого такого ребра: значение получения. Между каждой парой поставщика и потребителя строится ребро с бесконечной пропускной способоностью (или с общей суммой отдачи/получения).

4) запускается алгоритм Форда-Фалкерсона — получаем некоторый базис. Он в общем случае еще не оптимален.

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

Вопрос: как минизировать количество выплат? Спасибо!


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

Answer 1

[apodavalov]

Добрый день!


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

Во-первых, спасибо большое!

Во-вторых, портировал на C#. Я напишу тут несколько замечаний, чтобы исправить ошибки, которые (возможно) есть в коде.

equalizer.cpp


Строка 268:

for (int i = 0; i < sorted_balance.length() — 1; i++)

Почему "- 1"?

Строка 87:

Строка 239:

if (temp.isEmpty() || temp_list.length() + 1 < temp.length())

Почему "+ 1"?

Строка 119:

Вот это:

if (!used.contains(first_key))

{

for (int j = i + 1; j < balance.keys().length(); j++)

Нужно сделать так:

for (int j = i + 1; j < balance.keys().length() && !used.contains(first_key); j++)

Так как first_key может попасть в массив used внутри цикла по j


В третьих, по поводу кода: пока среди моих тестов проходят все. Подготовлю тесты побольше. И буду вкуривать теперь логику работы. Еще раз спасибо =)

Добавлено спустя два года:
Для того, чтобы решить задачу достаточно найти все минимальные подгруппы в которых сумма балансов равна 0 (в таких группах не содержатся другие подгруппы сумма балансов которых равна 0). Затем просто раздать балансы внутри полученных подгрупп "в лоб".
Для решения первой подзадачи можно использовать: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

Answer 2

[mithraen]

Вы усложнили себе задачу.

В этой задаче цепочки передачи денег не имеют смысла — они не уменьшают количество транзакций. Скажем у A и B баланс отрицательный, у C — положительный. A может передать деньги B, чтобы он передал C все одной транзакций, а могут передавать их каждый сам напрямую C, от этого ничего не изменится.

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

Я бы предложил простой алгоритм, хотя доказать его оптимальность я не могу:

1. Ищем есть ли у нас пары получатель/отправитель с одинаковым по модулю балансу. Если есть — прекрасно, делаем платежку и обнуляем их балансы (забываем про них).
2. Находим того, кто должен больше всех (отправитель)
3. Находим того, кому должны наибольшую сумму (получатель)
4. Делаем платежку на сумму, наименьшую из этих двух (если у нас есть отправитель который должен суммарно 20, а самый крупный получатель должен получить 11 — делаем платежку от отправителя к получателю на 11)
5. Повторяем, пока не останется ни одной задолженности

Comments

[apodavalov]

По поводу первого абзаца: в моей транспортной сети нет ребер между поставщиками. а также нет ребер между потребителями. Есть только ребра между любой парой (поставщик, потребитель).

К сожалению, я это тоже пробовал. Следующий пример (в скобкх уже указаны балансы): A (-21), B(-6), C(-2), D(8), E(7), F(7), G(7) не даст верного ответа:
1) Одинаковых по модулю балансов нет;
2) A — должен больше всех
3) D — должны больше всех.
4) делаем платеж A -> D (8). D уходит. У A остается 13.
5) A должен больше всех. Из оставшихся потребителей — выбираем любого (7). Одинаковых по модулю балансов нет.
6) A -> E (7). У A осталось 6. E уходит.
7) A должен больше всех (или так же как B). Балансов одинаковых по модулю снова нет.
8) F должны больше всех. A -> F (6). A уходит. У F остается баланс 1.
9) B должен больше всех. G должны больше всех. Одинаковых по модулю балансов нет.
10) B->G (6). B уходит.
11) Оставшиеся у C (2) передаются F (1) и G (1). Итого: 6 выплат.

А верный ответ A -> E (7), A -> F(7), A -> G(7), B->D(6), C->D(2). 5 вылпат.

Спасибо за ответ!

[mithraen]

Да, действительно. Тогда сдаюсь :)

Answer 3

[alan_mun]

Приветствую!

Попробовал решить Вашу задачку, и вот результат в виде кода на Qt.

Предлагаю решать её так:
1. С полной уверенностью находим баланс для транзакций.
2. Удаляем все совпадения из баланса (записывая транзакцию в ответ) и все объекты с нулевым балансом.
3. Находим самый маленький по модулю баланс.
4. А сейчас начинается милая сердцу рекурсия: для каждого из баланса другого знака создаём и проводим транзакцию. И запускаем эту же функцию с новыми значениями баланса.
5. Если получившийся результат в пункте 4 самый короткий по числу транзакций — радостно сохраняем его и передаём наверх.

Естественно пугаюсь того что рекурсия будет очень прожорливой.

Comments

[alan_mun]

За тавтологию во втором и третьем предложении заранее извиняюсь.

[apodavalov]

Доброе время суток!

Скачал, переписал на C# (у меня на C# подготовлено все). Все текущие тесты проходит. Сделаю еще больших тестов — отпишусь. Похоже, что Ваша рекурсия не такая прожорливая =) Спасибо =)

[apodavalov]

Да, чуть не забыл. в equal_search небольшая ошибочка закралась — я ее исправил — там оба раза i используется. Вот тут:

    for (int i = 0; i < balance.keys().length() - 1; i++)
    {
        QString first_key = balance.keys().at(i);
        for (int j = i + 1; j < balance.keys().length(); j++)
        {
            QString second_key = balance.keys().at(i);

[alan_mun]

Ох, как-то я совсем не доглядел.

Буду ждать результатов тестирования и верить в лучшее.

[apodavalov]

На 17 транзакциях уже работает довольно долго. У меня у самого был вариант тоже с перебором связанный, но он загибался на 10. Оставлю пока как наилучший вариант.
P.S. Где-то еще одна бага зарылась, хотя возможно, что это я виноват при переводе на C#.
Вот такой тест (кстати, тот самый):
17
A D 8
A E 7
A F 6
B F 1
B G 5
C G 2
Z X 3
Z W 2
Z V 50
Z U 55
Y V 5
M Y 67
K L 65
L M 6
Y H 7
Дает ответ:
13
F W 2
C W 0
M L 59
K V 55
Z U 53
Z Y 34
A Y 21
Z G 16
Z H 7
K E 7
M J 2
B J 6
K X 3

Обратите внимание сколько C должен W.

[alan_mun]

Согласен, тест на 17 выполняется безумно долго.
Но у меня ответ получился другим, и стоит сказать он выглядит правильным:
12
C W 2
K U 55
A H 7
M L 53
Z Y 55
Z V 55
M D 8
A G 7
A F 7
K E 7
B L 6
K X 3

Возникла пара мыслей на тему оптимизации, сейчас попробую их проверить и выложу результат.

[alan_mun]

Вот например «Попытка № 2»
У меня радостно выдаёт результат меньше чем за секунду. Для всё тех же 17 транзакций.

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

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

[apodavalov]

Прошу прощения, я не полный тест Вам дал. Две транзакции последние у меня куда-то подевались. Попробуйте, пожалуйста, на обоих Ваших вариантах (тест ниже). Попытку #2 пока не портировал на C#.
17
A D 8
A E 7
A F 6
B F 1
B G 5
C G 2
Z X 3
Z W 2
Z V 50
Z U 55
Y V 5
M Y 67
K L 65
L M 6
Y H 7
F G 9
D J 8

[alan_mun]

Снова добрался до. Запустил полный тест на 17 транзакций, но исключительно на второй версии пока. Вот резултат, с указанием времени начала работы и окончания.

16:03:03
12
c->w value = 2
z->v value = 55
z->u value = 55
k->y value = 55
k->x value = 3
k->e value = 7
a->h value = 7
a->g value = 7
a->f value = 7
m->l value = 59
m->j value = 2
b->j value = 6
16:03:03

[alan_mun]

Оп. Тоже ошибся, при запуске. Так что вот правильный вывод:

16:08:06
12
c->w value = 2
z->v value = 55
z->u value = 55
k->y value = 55
k->x value = 3
k->e value = 7
a->h value = 7
a->g value = 14
m->l value = 59
m->j value = 2
b->j value = 6
f->g value = 2
16:08:06