Оптимальность алгоритма минимизации жадных транзакций - PullRequest
Новая
       18

Оптимальность алгоритма минимизации жадных транзакций

0 голосов
/ 29 марта 2020

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

Чаще всего я сталкивался с решением жадный итеративный алгоритм , который, во-первых, вычисляет net результат каждого человека (деньги, которые он должен - деньги, которые он должен), а затем повторяет следующее: 

1. take max. debtor X and max. creditor Y
2. if X owes more than Y is owed
     then X pays Y Y's value
          reduce X's debt by Y's value
          set Y's value to 0
     else X pays Y X's value
          reduce Y's value by X's debt
          set X's debt to 0

... до тех пор, пока значение каждого не станет равным 0.

Мой вопрос (ы):

  • Является ли этот алгоритм действительно оптимальным с точки зрения суммы транзакции, которую он производит? Если да, как это можно доказать?
  • Если нет, то каков контрпример к оптимальности этого алгоритма, т. Е. Ситуация, когда долги можно минимизировать с меньшим количеством транзакций, чем те, которые он выводит?

1 Ответ

1 голос
/ 29 марта 2020

Похоже, этот алгоритм не является оптимальным. Рассмотрим случай [-3, -2, -2, 3, 4], где положительное значение указывает на кредитора, а отрицательное указывает на должника. Используя описанный алгоритм, мы требуем четыре операции транзакции, чтобы выбить все долги: 

>> [-3, -2, -2, 3, 4]
>> [0, -2, -2, 3, 1]    ([0] pays [4])
>> [0, 0, -2, 1, 1]     ([1] pays [3])
>> [0, 0, -1, 1, 0]     ([2] pays [4])
>> [0, 0, 0, 0, 0]      ([2] pays [3])

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

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

...