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

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

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

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

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

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


algorithm flow-control
person Craig Gidney    schedule 25.04.2009    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

person j_random_hacker    schedule 25.04.2009
comment
Стационарное решение, вероятно, даст хорошее приближение, но причина, по которой я сказал динамическое, заключается в том, что количество, потребляемое потребителями, может меняться изо дня в день (вплоть до некоторого максимума). То же самое и с производителями. Кроме того, узлы добавляются и удаляются относительно часто. - person Craig Gidney; 25.04.2009
comment
ХОРОШО. В таком случае, есть ли какая-то причина не просто загружать каждый узел до полной емкости хранилища, когда это возможно? - person j_random_hacker; 25.04.2009
comment
Это было бы эквивалентно отсутствию хранилища. Узлы опустеют, когда потребление возрастет, и заполнятся, когда оно уменьшится. Но общая идея о том, что заполнение узла лучше, чем ничего не делать, верна. - person Craig Gidney; 25.04.2009
comment
Верно, ноды будут пустеть, когда потребление увеличивается, и заполняться, когда оно уменьшается — разве это не то, чего вы хотите? Я предполагаю, что единственный способ, которым это может привести к неоптимальному результату, — это если емкость хранилища узла может со временем уменьшаться, и в этом случае это может привести к нелегальным потокам (но так же будет с любым методом в этих условиях). Не могли бы вы привести небольшой пример, в котором жадное заполнение узлов приводит к неоптимальному поведению? - person j_random_hacker; 28.04.2009