假设您有一组节点。有些节点是生产者,有些是消费者,有些是路由器。每个节点都有一个最大吞吐量,它定义了它每天可以接受的最大单位数,以及它每天可以发送的最大单位数(在这种情况下,接受和发送不会相互干扰)。每个节点还具有单元存储容量,允许它们处理流量变化。此外,每个节点最多只能与最多 8 个附近节点(在一个平面上)进行外连接,并且相同的限制适用于内连接。
我已经有一个启发式算法,给定一个图表,枚举节点并完成将单元推送到后续节点的足够好的工作。它枚举每个节点,向每个目标节点发送 max(ceil(remaining-sendable-units/remaining-following-nodes), remaining-receivable-units-at-receiver)。
现在我需要一种方法来自动查看节点,并决定图形拓扑应该是什么以获得足够好的流量。我的基本想法是为每个节点分配一个“责任”,最初相当于他们消耗了多少单位。然后将一条边从 n1 添加到 n2 会将 n2 的一些责任交给 n1。但我很快发现节点可以消耗的数量和节点可以接受的数量之间的差异混淆了算法并让我陷入困境。
编辑 每个生产者/消费者消耗的数量会随时间变化(低于某个最大值),并且可以添加或删除节点。
有什么简单的想法吗?