Алгоритм для упрощения взвешенного ориентированного графика долгов

Я использовал небольшой python script, который я написал, чтобы управлять долгом среди моих соседей по комнате. Это работает, но есть некоторые недостающие функции, одна из которых упрощает излишне сложные структуры долга. Например, если следующий взвешенный ориентированный граф представляет некоторых людей, а стрелки представляют собой долги между ними (Алиса должна Бобу 20 долларов США и Чарли 5 долларов, Боб должен Чарли 10 долларов США и т.д.):

Ясно, что этот график следует упростить до следующего графика:

Нет смысла в 10 долларов, начиная от Алисы до Боба, а затем от Боба до Чарли, если Алиса может просто передать его Чарли напрямую.

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

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

Под "потоком" подразумевается значение всех входов минус все выходы (есть ли для этого технический термин? Я не эксперт по теории графов). Таким образом, в приведенном выше примере значения потока для каждого node:

Боб: +10
Алиса: -25
Чарли: +15

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

Это:

следует упростить:

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

Ответ 1

Простой алгоритм

В O (n) вы можете найти, сколько денег ждет или будет платить. Таким образом, вы можете просто создать два списка: один для дебетования, а другой для кредита, а затем сбалансировать заголовок двух списков, пока они не будут пустыми. В первом примере:

Начальное состояние: Дебет: (A: 25), Кредит: (B: 15, C: 10)
Первая транзакция, A: 15 → B: Дебет: (A: 10), Кредит: (C: 10)
Вторая транзакция, A: 10 → C: Дебет:(), Кредит:()

Операции определяют границы вашего графика. Для n вовлеченных лиц будет не более n-1 транзакций = ребра. Вначале общая длина обоих списков равна n. На каждом шаге по крайней мере один из списков (дебет/кредит) становится короче на один, а в последнем оба списка исчезают сразу.

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

Меньше транзакций

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

EDIT. Благодаря j_random_hacker для указания того, что решение с ребрами меньше n-1 возможно, если есть группа лиц, общая задолженность которых соответствует кредиту другой группы лиц: Тогда, проблему можно разбить на две подзадачи с общей стоимостью n-2 ребер для графика транзакций. К сожалению, проблема суммирования подмножества является NP-трудной.

Проблема потока?

Возможно, это также можно преобразовать в проблему min-cost flow. Если вы хотите просто упростить свой первоначальный график, вы создаете поток на нем, предельные емкости - это оригинальные суммы дебетов/кредитов. Дебиторы служат в качестве притока (через соединитель node, который обслуживает всех дебиторов с краями емкости, равными их общей задолженности), кредиторы используются как узлы оттока (с аналогичным коннектором node).

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

Ответ 2

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

Верхофф, Т. (2004). Эффективное урегулирование нескольких долгов: приглашение в информатику. Информатика в образовании, 3 (1), 105-126.

Ответ 3

Я действительно столкнулся с этой проблемой в той же ситуации, что и вы:)

Я думаю, что любое решение krlmlr не совсем решает проблему. Я подумаю о том, как его точно решить (в смысле минимальных границ), но в то же время практическое альтернативное решение вашей проблемы - придумать нового человека, Стив:

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

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

Если все согласны с самого начала выплачивать Стива только полную сумму, то каждый net-ower делает ровно один депозит, и каждый чистый игрок делает ровно один вывод (хотя для проверки может потребоваться несколько проверок, чтобы увидеть, в настоящее время имеется достаточное количество наличных денег). Хорошая вещь о Стиве заключается в том, что он всегда рядом и никогда не слишком занят, чтобы разобраться в финансах. К сожалению, он очень легковерный, поэтому Алисе, Бобу и Чарли нужно доверять друг другу, чтобы не воспользоваться им.