Алгоритм определения зависимостей

Question

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

Правила

1. Перестановки могут происходить параллельно, если нет зависимости
2. Свопы происходят партиями, например. сделки, которые зависят от другого должен ждать, пока не будет обработан зависимый своп из предыдущего партия.

Вот пример

• Джонни имеет 100 долларов и 5 яблок
• Папоротник имеет 150 долларов и 3 апельсина
• Билл имеет $ 0 и 3 персика

Очередь свопов

A) Папоротник торгует 50 $ за 5 яблок от Джонни

B) Джонни торгует 140 $ за 2 персика Биллу

C) Папоротник торгует $ 10 за 1 персик Биллу

Фактические зависимости

A -> B

C

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

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

Answer 1

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

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