Уравнение для управления невзвешенным потоком

Question

У меня есть график, подобный приведенному ниже.

Это представляет узлы, связанные путем. Один узел обозначает начало (слева), а другой - конец (справа).

Моя цель - отправить войска от начала до конца по следующим правилам:

• Узлы могут содержать только одну единицу (за исключением начала и конца, которые не ограничены)
• Юнит может продвигаться только на один узел за ход
• Когда юнит продвигается на узле, отличном от стартового, он должен двигаться на каждом ходу, не может быть заторов.

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

Например, на моем графике для отправки 2 юнитов потребовалось бы 3 хода, я бы использовал путь только сверху.

Но для 15 юнитов было бы более оптимизировано посылать некоторые юниты на пути посередине и, может быть, тоже внизу моего графика.

Мне трудно найти уравнение для управления моим потоком.

Надеюсь, вы поняли мою проблему и спасибо за чтение!

Answer 1

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

Answer 2

Для каждого из путей подсчитайте, сколько узлов на них (исключая начало и цель). Затем путь с k узлами начнет предоставлять одну единицу за ход после k поворотов. Затем сортируйте ваши пути по k и выполняйте пошаговое моделирование. Поддерживать текущее количество единиц на цели и текущую скорость единиц (количество путей с k <= currentTime). Затем увеличивайте текущий номер единицы на единицу скорости, пока не достигнете желаемого целевого числа.

По сути, ваша единица измерения является кусочно-постоянной функцией (со временем). Следовательно, количество единиц является постоянной линейной функцией (с течением времени). Но я думаю, представлять это как функцию не очень полезно.