Что такое хорошая локальная эвристика для управления динамическим дискретным узлом?

Question

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

У меня уже есть эвристика, которая, учитывая график, перечисляет узлы и делает достаточно хорошее задание, нажимая единицы на следующие узлы. Он перечисляет каждый узел, отправляя на каждый целевой узел max (ceil (оставшиеся отправители-единицы/оставшиеся-следующие-узлы), оставшиеся-receivable-units-at-receiver).

Теперь мне нужен способ автоматического поиска узла и определения топологии графа для обеспечения достаточного потока. Моя основная идея заключалась в том, чтобы назначить «ответственность» каждому узлу, изначально эквивалентную количеству единиц, которые они потребляли. Тогда добавление ребра из n1 в n2 даст некоторую ответственность n2 за n1. Но я быстро обнаружил, что разница между суммой, которую может потреблять узел, и суммой, которую может принять узел, запутал алгоритм и повел меня по кругу.

Редактировать Сумма, потребляемая каждым производителем/потребителем, может меняться со временем (ниже некоторого максимума), а узлы могут быть добавлены или удалены.

Любые простые идеи?

Answer 1

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

Таким образом, в этом случае, мы можем забыть о емкости дисков для каждого узла, и проблема очень похожа на Maximum Flow problem, которая может быть решена точно за полиномиальное время, без особых трудностей. Ссылка Wikipedia предлагает множество алгоритмов - я предлагаю начать с Ford-Fulkerson, который не так уж сложно реализовать (другим может быть проще, но я сам их не реализовал).

Чтобы действительно превратить вашу проблему в проблему Max Flow, есть одна вещь, которую вы должны будете сделать: Max Flow имеет дело с ограничениями на потоки через кромками, а не в узлах. Чтобы преобразовать ограничения «пропускной способности узла» к ограничениям «пропускной способности границ», просто превратите каждый узел в 3 узла, связанных в строке (1 -> 2 -> 3), причем край между узлами 1 и 2 имеет емкость, равную " входной емкости "узла, а край между узлами 2 и 3 имеет емкость, равную« выходной емкости »узла. Затем убедитесь, что все входы к узлу подключены к узлу 1, и все выходы подключены к узлу 3.

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