Какой алгоритм использовать для определения минимального количества действий, необходимых для приведения системы в состояние «Ноль»?

Question

Это более общий вопрос, не зависящий от языка. Подробнее об идее и алгоритме использования.

Система работает следующим образом:

Он регистрирует небольшие кредиты между группами друзей. Alice и Bill собираются на обед, карточка Билла не работает, поэтому Алиса платит за еду, 10 долларов.
На следующий день Bill и Charles встречают друг друга на железнодорожной станции, у Чейлза нет денег на билет, поэтому Bill покупает его один за 5 долларов. Позже в тот же день Alice занимает 5 долларов у Charles и 1 доллар у Bill, чтобы купить ее подруге.

Теперь, если все они зарегистрировали, что транзакций в системе, это выглядит так:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

Итак, теперь единственное, что нужно сделать, это Bill дать Alice 4 доллара (он дал ей 1 доллар, а Charlie перевел свои 5 долларов на Alice кредит) и они " в исходном состоянии.

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

Answer 1

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

Ваши транзакции могут быть структурированы как бухгалтерские записи следующим образом:

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0

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

В этом простом случае это простой перевод в 4 доллара от Билла к Алисе. Вам нужно уменьшить хотя бы одну учетную запись (но предпочтительно две) до нуля для каждой добавленной транзакции. Допустим, у вас было более сложное:

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0
Charles -> Bill     $1       4     5-       1        0

Тогда необходимые транзакции будут:

Bill     -> Alice   $4       0     1-       1        0
Bill     -> Charles $1       0     0        0        0

---

К сожалению, в некоторых штатах эта простая жадная стратегия не дает наилучшего решения (спасибо j_random_hacker за указание на это). Один пример:

                 Alan  Bill  Chas  Doug  Edie  Fred  Bal
Bill->Alan   $5    5-    5     0     0     0     0    0
Bill->Chas  $20    5-   25    20-    0     0     0    0
Doug->Edie   $2    5-   25    20-    2     2-    0    0
Doug->Fred   $1    5-   25    20-    3     2-    1-   0

Ясно, что это можно изменить за четыре хода (так как четыре шага - это все, что нужно, чтобы добраться туда), но, если вы выберете свой первый ход неразумно (Edie->Bill $2), пять - это минимум, с которым вам сойдет. *

Вы можете решить эту конкретную проблему с помощью следующих правил:

• (1), если вы можете уничтожить два баланса, сделайте это.
• (2) в противном случае, если вы можете стереть один баланс и настроить себя, чтобы стереть два в следующем ходу, сделайте это.
• (3) в противном случае уничтожить любой баланс.

Это приведет к следующей последовательности:

• (a) [1] не применимо, [2] может быть достигнуто с Alan->Bill $5.
• (b) [1] можно сделать с помощью Chas->Bill $20.
• (c) и (d), аналогичные рассуждения с Дагом, Эди и Фредом, для четырех полных ходов.

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

Я думаю, это то, что потребуется, чтобы дать вам наименьшее количество транзакций при любых обстоятельствах. Тем не менее, может оказаться, что это не требуется для ответа best (лучший в данном случае означает максимальный «удар за доллар»). Вполне возможно, что даже базовый набор правил 1/2/3 даст вам достаточно хороший ответ для ваших целей.

Answer 2

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

1. Выведите все позиции, т. Е. Из приведенного выше примера:

   Алиса = 4 $ Счет = $ -4 Чарльз = 0

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

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

Это займет что-то вроде O (n log n) (опять же, необходимы правильные доказательства).

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

Answer 3

Я создал приложение для 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://www.settleup.info/files/master-thesis-david-vavra.pdf

Answer 4

Я нашел практическое решение, которое я реализовал в Excel:

• выясните, кто должен больше всего

• пусть этот человек заплатит всю сумму, которую он должен тому, кто должен получить больше всего

• , что делает первого человека нолем

• повторить этот процесс, принимая во внимание, что один из (n-1) человек изменил сумму

Это должно привести к максимуму (n-1) переводов, и приятно то, что никто не делает более одного платежа. Возьмите (модифицированный) пример jrandomhacker:

a = -5 b = 25 c = -20 d = 3 e = -2 f = -1 (сумма должна быть равна нулю!)

1. c -> b 20. результат: a = -5 b = 5 c = 0 d = 3 e = -2 f = -1

2. a -> b 5 результат: a = 0 b = 0 c = 0 d = 3 e = -2 f = -1

3. e -> d 2 результат a = 0 b = 0 c = 0 d = 1 e = 0 f = -1

4. f -> d 1

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

Answer 5

Я разработал решение, используя несколько иной подход к тем, которые были упомянуты здесь. Он использует линейную программную формулировку проблемы, опираясь на литературу по Compressed Sensing, особенно из этой работы Donoho and Tanner (2005) .

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

Приветствие.

Answer 6

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

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

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

Применение максимального расхода и / или минимального среза даст вам набор передач. Фактическая сумма потока будет тем, сколько денег будет переведено.

Answer 7

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

То есть простой набор - просто найти каждый баланс и погасить его. Это не больше, чем N! сделки.

Если A должен B и C, а некоторое подмножество B C должно друг другу, так что B должен C, тогда вместо: A -> B, A -> C (3 транзакции). Вы бы использовали: A -> B, B -> C (2 транзакции).

Другими словами, вы строите ориентированный граф и хотите обрезать вершины, чтобы максимизировать длину пути и минимизировать общее количество ребер.

Извините, у меня нет алгоритма для вас.

Answer 8

Это код, который я написал, чтобы решить эту проблему в Java. Я не уверен на 100%, дает ли это наименьшее количество транзакций. Ясность и структура кода могут быть значительно улучшены.

В этом примере:

• Сара потратила 400 долларов на прокат автомобилей. Машиной пользовались Сара, Боб, Алиса и Джон.

• Джон потратил 100 долларов на продукты. Продукты были потреблены Бобом и Алиса.

  import java.util.*;
  public class MoneyMinTransactions {
  
      static class Expense{
          String spender;
          double amount;
          List<String> consumers;
          public Expense(String spender, double amount, String... consumers){
              this.spender = spender;
              this.amount = amount;
              this.consumers = Arrays.asList(consumers);
          }
  
      }
  
      static class Owed{
          String name;
          double amount;
          public Owed(String name, double amount){
              this.name = name;
              this.amount = amount;
          }
      }
  
      public static void main(String[] args){
          List<Expense> expenseList = new ArrayList<>();
          expenseList.add(new Expense("Sarah", 400, "Sarah", "John", "Bob", "Alice"));
          expenseList.add(new Expense("John", 100, "Bob", "Alice"));
          //make list of who owes how much.
          Map<String, Double> owes = new HashMap<>();
          for(Expense e:expenseList){
              double owedAmt = e.amount/e.consumers.size();
              for(String c : e.consumers){
                  if(!e.spender.equals(c)){
                      if(owes.containsKey(c)){
                          owes.put(c, owes.get(c) + owedAmt);
                      }else{
                          owes.put(c, owedAmt);
                      }
                      if(owes.containsKey(e.spender)){
                          owes.put(e.spender, owes.get(e.spender) + (-1 * owedAmt));
                      }else{
                          owes.put(e.spender, (-1 * owedAmt));
                      }
                  }
              }
          }
          //make transactions.
          // We need to settle all the negatives with positives. Make list of negatives. Order highest owed (i.e. the lowest negative) to least owed amount.
          List<Owed> owed = new ArrayList<>();
          for(String s : owes.keySet()){
              if(owes.get(s) < 0){
                  owed.add(new Owed(s, owes.get(s)));
              }
          }
          Collections.sort(owed, new Comparator<Owed>() {
              @Override
              public int compare(Owed o1, Owed o2) {
                  return Double.compare(o1.amount, o2.amount);
              }
          });
          //take the highest negative, settle it with the best positive match:
          // 1. a positive that is equal to teh absolute negative amount is the best match.  
          // 2. the greatest positive value is the next best match. 
          // todo not sure if this matching strategy gives the least number of transactions.
          for(Owed owedPerson: owed){
              while(owes.get(owedPerson.name) != 0){
                  double negAmt = owes.get(owedPerson.name);
                  //get the best person to settle with
                  String s = getBestMatch(negAmt, owes);
                  double posAmt = owes.get(s);
                  if(posAmt > Math.abs(negAmt)){
                      owes.put(owedPerson.name, 0.0);
                      owes.put(s, posAmt - Math.abs(negAmt));
                      System.out.println(String.format("%s paid %s to %s", s, Double.toString((posAmt - Math.abs(negAmt))), owedPerson.name));
                  }else{
                      owes.put(owedPerson.name, -1 * (Math.abs(negAmt) - posAmt));
                      owes.put(s, 0.0);
                      System.out.println(String.format("%s paid %s to %s", s, Double.toString(posAmt), owedPerson.name));
                  }
              }
          }
  
  
  
  
      }
  
      private static String getBestMatch(double negAmount, Map<String, Double> owes){
          String greatestS = null;
          double greatestAmt = -1;
          for(String s: owes.keySet()){
              double amt = owes.get(s);
              if(amt > 0){
                  if(amt == Math.abs(negAmount)){
                      return s;
                  }else if(greatestS == null || amt > greatestAmt){
                      greatestAmt = amt;
                      greatestS = s;
                  }
              }
          }
          return greatestS;
      }
  
  
  }
  

Answer 9

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

Answer 10

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