现在已经有一段时间了，我一直在侵犯这个问题，但从未设法提出一个完全令人满意的解决方案。它涉及网络流 - 您拥有一个节点图，这些节点被认为可以在它们之间流动某种资源，例如管道中的水，道路系统上的交通等。
此类网络流问题似乎通常仅以三种类型的节点给出：来源（IE资源是生成或至少将其集中到那里的网络中），路由器或连接器（拆分或保守的资源）和下沉（消耗，消耗，消耗，资源的处置等）。然后，我们做一些事情，例如询问如何解决边缘上的流量，以尝试找出使用来自源的可用物品以满足水槽需求的最佳方法，即计算最大流量。
但是，我感兴趣的是，当您将第四个组件添加到混音中时，您如何处理： tanks ，或可以“填充”资源以稍后将其“填充”的零件。从网络的角度来看，根据它们所包含的资源数量，它们似乎可以像其他三个组件一样，取决于其容量以及它们如何挂接 - 请注意，坦克都可以让东西喂食和事物。同时从中绘制，或者只有喂食器或仅绘制，因此它可以在上面的所有三个角色中起作用。此外，根据它是否包含内容还是空白空间，它也可以改变角色 - 空的坦克不能充当源它。
例如，如果给出了类似的流求解器：
然后，它应该在左边缘将50单位/秒的速率放在左边缘，5个单位/秒在右边缘，因为坦克可以吸收45个单位/秒。
但是，如果坦克像这样挂钩：
然后，求解器应将45个单元放在垂直边缘，从储罐中流出，而从源流出的5个单位则满足50的总需求从水槽。
也就是说，在涉及储罐的图中，储罐应“补充”来源提供的流量以满足水槽的需求，否则应“吸收”没有相应需求的多余流量。但是，它只能在尊重它可以达到的目标或可以从边缘提供的连接中达到的东西时做到这一点。请注意，在这里，由于它们忽略边缘方向时，我的图纸也许过于简单，但目的是，第二个坦克从坦克引向的边缘将其定向到交界处。因此，在源宣传+50和水槽-5的不同情况下的行为应该只是从源到水槽的5 u/s，即通常的最大流量，坦克不会贡献任何流程。如果它具有双向边缘，则在这种情况下，应从源中吸收45 u/s，而在原始情况下，与单向情况没有什么不同。
如何创建一种算法来可靠地生成此类解决方案，只有图形和哪些节点是储罐，交界器，来源和水槽，以及从水槽来源和需求的供应是什么？
For quite some time now, I've been hacking away at this problem but never have managed to come up with an entirely satisfactory solution. It concerns network flow - where you have a graph of nodes which are imagined to have some kind of resource flowing between them, like water in pipes, or traffic on a road system, and so forth.
Such network flow problems seem to be usually given in terms of three types of nodes only: sources (i.e. resource is generated or at least emplaced into the network there), routers or junctions (splits or combines resource conservatively), and sinks (consumes, disposes, etc. of resource). And then we do something like ask how we can solve for the flows on the edges so as to try and figure out the best way to use what is available from the sources to meet the demand from the sinks, i.e. to compute the maximum flow.
But what I am interested in is how you deal with this when you add a fourth component into the mix: tanks, or parts which can "fill up" with resource to later discharge it. From the perspective of the network and depending on the amount of resource they contain, they can seemingly act like all three of the other components depending on their capacity and how they are hooked up - note that a tank can both have things feeding it and things drawing from it simultaneously, or have only feeders or only draws, so it can act in all three roles above. Moreover, depending on whether it contains content or empty space, it can likewise also change role - an empty tank cannot act as a source, obviously, nor can a full tank act as a sink, as it can't fit any more stuff into it.
For example, if the flow solver is given something like this:
then it should put a rate of 50 units/sec of flow on the left edge, 5 units/sec on the right edge, because the tank can absorb 45 units/sec.
But if the tank is hooked like this:
then the solver should put 45 units on the vertical edge as flowing out from the tank, and 5 units flowing from the source, to meet the total demand of 50 from the sink.
That is, in a graph involving a tank, the tank should "supplement" flow provided from sources to meet demand from sinks, or else should "absorb" excess flow that did not have corresponding demand. However, it must only do this while respecting what it can reach or what can reach it from the connections provided by the edges. Note here my drawings are perhaps oversimplified as they ignore the edge directions, but the intent is that the edge leading up from the tank in the second one is directed into the junction. Thus, the behavior in a different case where the source were to advertise +50 and the sink -5 should just be to route 5 U/s from the source to the sink, i.e. the usual max-flow, and the tank would not contribute any flow. If it had a bidirectional edge, then in this case it should absorb 45 U/s from the source, while in the original case behaving no different from the unidirectional case.
How can one create an algorithm to reliably generate such solutions, given only the graph and which nodes are tanks, junctions, sources, and sinks and what the supply from the sources and demand from the sinks are?
发布评论
评论（1）
如果您假设储罐具有无限的容量（它们可以以“生产”速率吸收无限量，并以“消耗”速率以无限的数量吸收，那么您可以使用正常的图流量算法解决问题
。储罐具有有限的容量，即它们在干燥或饱满时会改变其行为，然后解决方案随时间和时间而变化，取决于储罐的初始水平，如果储罐能力相对于流速很大，则解决方案。将是稳态的，因此您可以创建多个图形，代表每个坦克的所有可能组合（全部，空或部分），并使用图理论解决每个储罐。坦克是适度的，
坦克，并且您对系统的时间行为感兴趣。
如果您有许多 挑战是解释结果，这项任务需要对统计数据有很好的理解。
您还可以考虑编码自己的特殊用途模拟器。您不会提及自己喜欢的编码语言，但是如果您知道C ++，则可以从
If you assume that your tanks have infinite capacity ( they can absorb an infinite quantity at the 'produce' rate AND be drawn down for an infinite quantity at the 'consume' rate, then you can solve the problem using normal graph flow algorithms.
If the tanks have finite capacity, i.e. they change their behavior when they run dry or become full, then the solution changes with time and times depend on the initial levels of the tank. If the tank capacities are large relative to the flow rates, the solutions will be steady state for significant periods. So you create multiple graphs, representing every possible combination of the three tanks states ( full, empty, or partial ) for each tank and solve each using graph theory. This will only be feasible if the number of tanks is modest.
If you have many tanks, and you are interested in the time behavior of your system. you will have to use a simulation approach.
There are many generic simulation packages available that can be configured to solve this problem. The challenge is to interpret the results, a task which requires good understanding of statistics.
You might also consider coding your own special purpose simulator. You do not mention your preferred coding language, but if you know C++ you can get a good start from https://github.com/JamesBremner/tankfill