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

Ответ 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 выше, но расширены для обработки большей глубины).

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

Ответ 2

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

• Отключите все позиции, например, от вашего примера выше:

  Алиса = $4 Билл = $-4 Charles = $0

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

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

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

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

Ответ 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 Ghz procesor), и результаты: до 10 членов: < 100 мс, 15 членов: 1 с, 18 членов: 8 с, 20 членов: 55 с. Таким образом, до 18 членов время исполнения в порядке. Обходным решением для > 15 членов может быть использование только базового алгоритма (это быстро и правильно, но не оптимально).

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

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

http://www.settleup.info/files/master-thesis-david-vavra.pdf

Ответ 4

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

• узнать, кто из них наиболее

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

• который делает первого человека нулевым

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

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

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

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

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

• e → d 2 результат a = 0 b = 0 c = 0 d = 1 e = 0 f = -1

• f → d 1

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Ответ 9

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