algorithm - 复杂输送机运力计算(图)——趣味游戏算法

Question

我正在用 Javascript 开发一款游戏，人们可以在其中创建传送带。想象一下邮政服务，包裹进来，在传送带上移动，经过处理，最后用卡车结束。这些传送带可以很复杂，可以包含环路等。

相当复杂(且效率低下)的输送机示例 Example conveyor with bad graphics

输送机的示例图: Conveyor example

圆圈中的数字表示当前情况 - 该传送带“部分”上的包裹数量。

规则:

• IN 组件生成邮包并放入传送带组件。
• Belt 组件将邮政包裹推送到 OUT 组件。 OUT 从图中删除包。
• 每个组件在任何给定时刻都可以容纳 MAX 容量。
• 可以有 0..N IN 个组件。 (如果为 0，则传送带上可能已经有包裹)
• 可以有 0..N 个 OUT 组件。 (如果为 0，表示整个传送带将装满)
• 计算是基于滴答的，这意味着“一组包裹”一次只能走一步。
• 每次合并平均分配包。 (因此，如果有两条出线，则每条线都会收到 packages/2)
• 每个加入平均接受包裹。 (所以如果有两条输入线，每条可以给出 max/2 个包。)
• 包裹没有身份，它们只是总数。
• 包可以拆分，因此 1 个包可以变成 0.5 和 0.5 个包。 (因此 float 为数字类型)

问题:

如何分两步快速求解这样的图:

1. 生成必要的数据结构/图形(缓存)(性能:1000 个元素 <200 毫秒)。实际上，如果在下一次包裹旅行计算之前设置发生变化，则只需要重新计算。

2. 计算包裹旅行。 (性能:<20ms for 1000 elements)

一些有问题的解决方案

选项 A:按组件求解。 (for 循环每个组件并根据当前情况解决)不起作用，因为循环、连接、合并会导致无法按要求均匀移动包的情况。它也不遵守规则，即“包裹”只能从一个组件传输到另一个组件。根据循环顺序，包可能会立即结束)。此外，它可能一直只喜欢一个输入，另一个将始终被阻止。

选项 B:为每个组件计算他们想要做什么并找出冲突。 (例如，A 和 B 想向 C 推送 10 个包裹，但 C 总共只能接受 12 个。修正错误，因此 A 和 B 都只能移动 6 个，这意味着他们的库存在下一个刻度至少为 4 个. 这可能会导致更多的错误，因为 A 和 B 没有明确他们的内容，他们可以接受更少)。现在找到更多错误并修复。重复直到没有错误或“达到最大重复次数”，然后快速修复错误 = 这样它实际上不会根据规则按预期工作。问题是，我认为它会因某些设置而卡住并且可能会中断。

选项 C:从 OUT 元素开始并尝试将包移出。如果引入循环或没有 OUT 元素的区域，就会出现问题。

判决

我被困住了，甚至不知道要用谷歌搜索什么，所以欢迎所有想法 :)我认为这是一个图形问题，但也许还有其他方法。

Answer 1

只要你不需要问题的最优解，我认为你可以:

1. At the beginning, use a topological sort order of the graph, and "tag"
   each node with its position in that order so you have a criteria as to
    which node is better than others. The final node has the maximum "tag"
   (check link to learn more about topological sort, not hard)

2. Mark all nodes as not visited

3. Get the *node A* with max(tag) still not visited:

3.a. Get each *node B* that is a target from *node A* 
     (i.e. at the end of the arrow) starting from the one with maximum tag
     and finishing with the one with minimum tag:

3.a.a. push all packages from *node A* to *node B* until it is filled or 
       *node A* is empty.

您可以在https://en.wikipedia.org/wiki/Topological_sorting 中找到拓扑排序定义和一堆算法。

祝你好运:)