Алиса, Боб и их друзья-лексикографы активно торговали. Конечно, все вне сети. Теперь они должны выполнить следующие обязательства:

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

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

Тактика

Комбинировать мульти-кромки

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

Обрезать петли

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

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

Конечно, сейчас я покажу вам неоптимально направленный лес!

Удалить сквозные узлы

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

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

А как насчет этого?

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

Но как мы туда доберемся?

Решение

Вычислить чистое изменение остатков

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

Также обратите внимание, что сумма всех изменений баланса равна нулю. Это правда, потому что деньги не входят и не покидают систему, мы их только перемещаем. Давайте попробуем подход «разделяй и властвуй». Мы разбиваем задачу на подмножества, сумма которых равна нулю, решаем их, а затем объединяем эти решения в глобальное.

Найдите группы, сумма которых равна нулю

Нахождение этих групп связано с суммой подмножества и проблемой разбиения. Это NP-полные проблемы. Трудно найти набор, который суммируется до нуля, но легко проверить, что это так. Для небольших значений, представленных здесь, динамическое программирование будет работать в разумные сроки. Для 256-битных балансов Ethereum это не сработает. Грубая сила - достойная стратегия для небольшого количества участников.

Интересный факт: NP-полные задачи идеально подходят для Blockchain! Попросите пользователей вычислить решения вне сети и опубликовать их вместе с транзакцией. Тогда смарт-контракт может легко проверить их правильность и осуществить переводы.

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

На практике я ожидаю двух основных источников нулевых наборов. Во-первых, сквозные счета. Во-вторых, непересекающиеся группы, которые не передаются между собой. Суммирование изменений баланса до нуля по совпадению кажется маловероятным.

Сортировка изменений баланса от большого к мелкому

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

Создавайте транзакции сверху вниз

Начните с максимально возможной транзакции между двумя верхними узлами. Теперь ровно по одному из них будет учитываться баланс, он погашен. Повторите процесс для остальных узлов, каждый раз вынимая по одному узлу. В финальной транзакции оба оставшихся узла завершатся, всего n — 1 транзакции.

Это оптимально. Доказательство: мы знаем, что набор не содержит строгих подмножеств, сумма которых равна нулю. Предположим, мы можем решить эту проблему с помощью менее n — 1 транзакций, это создаст граф транзакций с n узлами и менее n — 1 ребрами. Этот граф транзакций не имеет достаточного количества ребер для соединения и, следовательно, имеет как минимум два несвязанных компонента. Сумма этих отключенных компонентов по отдельности равна нулю, что противоречит отсутствию строгих подмножеств, суммирующих до нуля. Поэтому n - 1 транзакций оптимально. ∎

Глобальное решение

Объединение этих частичных решений также является глобальным решением. Общее количество транзакций равно n — m, где m - количество нулевых подмножеств. Доказательство: предположим, что существует решение с меньшим количеством транзакций, чем n — m. Этот граф решения должен содержать более m компонентов. Каждый компонент имеет сальдо, суммирующее до нуля, поэтому существует более m подмножеств суммирования нуля. Противоречит нашему определению m, поэтому n — m транзакций является оптимальным. ∎

Уникальность

Решение не является уникальным, следующее также является оптимальным решением для последнего подмножества:

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

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

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

Несмотря на небольшой поиск, я не смог найти подобную проблему в области алгоритмов графа или оптимизации. Ссылки на литературу приветствуются!