0

假设您有一组节点。有些节点是生产者，有些是消费者，有些是路由器。每个节点都有一个最大吞吐量，它定义了它每天可以接受的最大单位数，以及它每天可以发送的最大单位数（在这种情况下，接受和发送不会相互干扰）。每个节点还具有单元存储容量，允许它们处理流量变化。此外，每个节点最多只能与最多 8 个附近节点（在一个平面上）进行外连接，并且相同的限制适用于内连接。

我已经有一个启发式算法，给定一个图表，枚举节点并完成将单元推送到后续节点的足够好的工作。它枚举每个节点，向每个目标节点发送 max(ceil(remaining-sendable-units/remaining-following-nodes), remaining-receivable-units-at-receiver)。

现在我需要一种方法来自动查看节点，并决定图形拓扑应该是什么以获得足够好的流量。我的基本想法是为每个节点分配一个“责任”，最初相当于他们消耗了多少单位。然后将一条边从 n1 添加到 n2 会将 n2 的一些责任交给 n1。但我很快发现节点可以消耗的数量和节点可以接受的数量之间的差异混淆了算法并让我陷入困境。

编辑 每个生产者/消费者消耗的数量会随时间变化（低于某个最大值），并且可以添加或删除节点。

有什么简单的想法吗？

4

1 回答 1

0

如果您正在寻找“稳态”解决方案，即每天沿给定边缘发生相同流量的解决方案，那么节点上不能有任何资源“储存”（因为这意味着每个储存都在继续以稳定的速度增长，最终变得无限大）。

所以在这种情况下，我们可以忽略每个节点的存储容量，这个问题与最大流量问题非常相似，可以在多项式时间内精确地解决，没有太大的难度。Wikipedia 链接建议了多种算法——我建议从 Ford-Fulkerson 开始，这并不难实现（其他的可能更容易，但我自己还没有实现）。

要真正将您的问题转化为 Max Flow 问题，您需要做一件事：Max Flow 处理跨边流的约束，而不是节点上的约束。要将您的“节点吞吐量”约束转换为“边缘吞吐量”约束，只需将每个节点变成 3 个连接成一条线的节点（1 -> 2 -> 3），节点 1 和 2 之间的边的容量等于“节点的“输入容量”，节点 2 和 3 之间的边的容量等于节点的“输出容量”。然后确保节点的所有输入都连接到节点 1，并且所有输出都连接到节点 3。

正如我所说，这将为您提供“稳态”解决方案。通过预先指定天数并利用存储容量，您可能可以设计一种策略，在该天数内为您提供更多吞吐量，尽管我怀疑比我更聪明的人可以证明即使这不是可能的。在任何情况下，如果您希望每天在每条边上都有相同的流量，那么您无法比 Max Flow 解决方案做得更好。

于 2009-04-25T12:32:16.453 回答