管理非加权流量的公式

Question

我有一个如下图所示的图表。

这表示按路径链接的节点。一个节点代表开始（在左侧），另一个节点代表结束（在右侧）。

我的目标是按照一些规则从开始到结束派兵：

• 节点只能包含一个单元（开始和结束除外）
• 单位每回合只能前进一个节点
• 一旦一个单位在不同于开始的节点上前进，它必须在每个转弯处移动，不会有拥塞。

我试图找到一个方程式，根据我需要发送的部队数量来计算实现该目标的最小转弯次数。这也有助于我知道我应该使用多少路径来优化我的部队流量。

例如，在我的图表中，发送2个单位需要3个回合，我只会使用顶部的路径。

但是对于15个单位，在中间的路径中发送一些单位，也可能在图表的底部发送一个单位会更加优化。

我很难找到一个方程来管理我的流程。

我希望你理解我的问题并感谢阅读！

Answer 1

对于每个路径，计算它们上的节点数（不包括开始和目标）。然后，在k转向后，具有k节点的路径将开始每回合提供一个单位。然后，通过k对路径进行排序并进行转向模拟。保持目标的当前单位数和当前单位费率（k <= currentTime的路径数）。然后，按单位速率增加当前单位数，直到达到所需的目标数。

从本质上讲，您的单位费率是一个分段常数函数（随着时间的推移）。因此，单位数是一个恒定的线性函数（随着时间的推移）。但我想，将此表示为一个函数并不是那么有用。

Answer 2

通过求解节点容量最大流问题，将流分解为单元路径，然后沿每条路径发送单元流，可以得到合理的近似值。吞吐量将是最佳的，但长路径可能会产生额外的延迟。