Кто должен кому деньги оптимизация

Question

Скажем, у вас есть n человек, каждый из которых должен друг другу деньги.В общем, должно быть возможно уменьшить количество транзакций, которые должны иметь место.то есть, если X должен Y £ 4, а Y должен X £ 8, то Y должен заплатить только X £ 4 (1 транзакция вместо 2).

Это становится сложнее, когда X должен Y, но Y должен Z, которыйдолжен и Х тоже.Я вижу, что вы можете легко рассчитать один конкретный цикл.Это помогает мне, когда я думаю о нем как о полностью связанном графе, с ребрами, являющимися суммой, которую должен каждый человек.

Проблема кажется NP-полной, но какой алгоритм оптимизации я мог бы сделать, тем не менее, чтобы уменьшить общее количество транзакций?Не обязательно быть таким эффективным, так как N для меня достаточно мало.

Редактировать:

Цель этой проблемы состоит в том, чтобы иметь в системе учета то, что можетСкажите каждому человеку, когда он входит в систему: «Вы можете удалить M сумму транзакций, просто заплатив кому-то сумму X, а кому-то еще Y».Следовательно, банковское решение (хотя и оптимальное, если все платят одновременно) не может быть использовано здесь.

Answer 1

Обязаны ли люди погашать свои долги, платя кому-то, кому они действительно должны деньги?Если нет, то кажется, что следующие действия работают подозрительно легко:

Для каждого человека определите чистую сумму, которую он должен заплатить или должен получить.

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

Если предположить, что я что-то упустил, какие ограничения применяются (или допускается грубая ошибка)

Answer 2

Я создал приложение для Android, которое решает эту проблему. Вы можете ввести расходы во время поездки, он даже рекомендует «кто должен платить дальше». В конце он вычисляет «кто должен кому сколько отправлять». Мой алгоритм вычисляет минимально необходимое количество транзакций, и вы можете установить «допуск транзакций», который может еще больше сократить транзакции (вам не нужны транзакции в 1 доллар). Попробуйте, это называется Settle Up:

https://market.android.com/details?id=cz.destil.settleup

Описание моего алгоритма:

У меня есть базовый алгоритм, который решает проблему с n-1 транзакциями, но он не оптимален. Это работает так: Из платежей я вычисляю баланс для каждого участника. Баланс - это то, что он заплатил, минус то, что он должен заплатить. Я сортирую членов по балансу все чаще. Тогда я всегда беру самых бедных и самых богатых и сделка совершается. По крайней мере один из них заканчивается нулевым балансом и исключается из дальнейших расчетов. При этом количество транзакций не может быть хуже, чем n-1. Это также минимизирует количество денег в транзакциях. Но это не оптимально, потому что он не обнаруживает подгруппы, которые могут располагаться внутри.

Найти подгруппы, которые могут обосноваться внутри, сложно. Я решаю это путем генерации всех комбинаций членов и проверки, равна ли сумма остатков в подгруппе нулю. Я начинаю с 2 пар, затем с 3 парами ... (n-1) пар. Доступны реализации комбинированных генераторов. Когда я нахожу подгруппу, я вычисляю транзакции в подгруппе, используя базовый алгоритм, описанный выше. Для каждой найденной подгруппы экономится одна транзакция.

Решение является оптимальным, но сложность возрастает до O (n!). Это выглядит ужасно, но хитрость в том, что в реальности будет только небольшое количество членов. Я протестировал его на Nexus One (процессор с частотой 1 ГГц) и получил следующие результаты: до 10 участников: <100 мс, 15 участников: 1 с, 18 участников: 8 с, 20 участников: 55 с. Так что до 18 членов время выполнения хорошо. Обходной путь для> 15 участников может заключаться в использовании только базового алгоритма (он быстрый и правильный, но не оптимальный).

Исходный код:

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

http://settleup.destil.cz/report.pdf

Answer 3

Назначьте одного человека произвольно в качестве банкира.

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

Там будет максимум (n-1) транзакций, что довольно мало.Это быстро.Это просто.

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

* Исключениеэто банкир сами.Быстрая оптимизация заключается в том, чтобы убедиться, что назначенный банкир не является тем, кто занимает нейтральную позицию.

** Объясняя мою верхнюю границу логики далее:

Предположим, что оптимальный случай равен A, дает 1 $ Bи C дает $ 1 для D, а E нейтрально = две транзакции.

Тогда с этой логикой, если E назначенный банкир, A дает $ 1 для E, E дает $ 1 для B, C дает $ 1 для Eи E дает от $ 1 до D = четыре транзакции.

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

Answer 4

for each debt in debts
  debt.creditor.owed -= debt.amount
  debt.deptor.owed += debt.amount
end

for each person in persons
  if person.owed > 0 then
    deptors.add person
  else if person.owed < 0 then
    creditors.add person
  end
end

deptors.sort_by_owed_desc
creditor.sort_by_owed_asc

for each debtor in deptors
  while debtor.owed > 0
    creditor = creditors.top
    amount = min( debtor.owed, -creditor.owed)
    creditor.owed += amount
    debtor.owed -= amount
    if creditor.owed == 0 then
      creditors.remove_top
    end
    write debtor.name " owes " creditor.name " " amount "€"
  end
end

Answer 5

Вот решение Python, которое я использовал;это та же идея, что и у поста Ганнера, с несколькими изменениями строки:

for i in N:
    for j in N:
        if i!=j and owes[i][j] > owes[j][i]:
            owes[i][j] -= owes[j][i]
            owes[j][i] = 0
for k in N:
    for i in N:
        for j in N:
            if k == i or i == j or k == j:
                continue
            if owes[j][k] > owes[i][j]:
                owes[i][k] += owes[i][j]
                owes[j][k] -= owes[i][j]
                owes[i][j] = 0;

Работает угощение.

Вы можете проверить это с помощью:

owes = [[0,2,11], [4,0,7], [2,3,0]]
N = range(len(owes))

Answer 6

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

Answer 7

У меня есть решение проблемы, написанное в Matlab.Он основан на матрице того, кто кому должен.Число в (i, j) означает, что человек j должен человеку i номер.Например,

B должен A 2, а A должен B 1

. Конечно, в этом случае тривиально, что B просто дает A 1

.,Тем не менее, с помощью алгоритма, который я написал, я могу гарантировать, что в этом случае происходит не более N-1 транзакций, где N - это количество человек 2.

Вот код, который я написал.

1012 * конец *

Answer 8

Я думаю, что вы должны удалить все циклы, уменьшая ребра на минимальное значение ребра и удаляя ребра со значением 0. После этого вы получите график без циклов. Я думаю, вы должны найти вершины, у которых нет указателей на них (человек, который должен только чужие деньги). Этот человек должен платить деньги, потому что нет никого, кто заплатил бы за них деньги. Поэтому я хочу сказать, что вы должны как-то найти, кому они должны платить.

Answer 9

Эту проблему можно решить с помощью алгоритма Варшалла.

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if ( i!= j && owes[i][j] > owes[j][i] )
owes[i][j] -= (owes[i][j] - owes[j][i]), owes[j][i] = 0;

for(k=0;k<n;k++)
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
if( k == i || i == j || k == j ) continue;
if ( owes[j][k] > owes[i][j] )
{
int diff = owes[j][k] - owes[i][j]; 
owes[i][j] = 0;
owes[i][k ] += diff;
owes[j][k] -= diff;
} 
}

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

Я еще не проверял, будет ли работать алгоритм, исходя из характера проблемы, с которой он может работать.Решение O (N ^ 3).

Answer 10

Я думаю, вам нужно построить другую структуру данных (дерево, каждый раз, когда один человек является корневым узлом), который будет проверять для каждого человека, сколько «транзакций» вы можете «убить», чем выбрать лучшую, сделайте цикл и восстановите его снова. это не o (N), я думаю, что это N ^ 2, и это не даст вам лучший результат. это просто стратегия.