algorithm - 在连续渗透中处理大量数据

Question

对于我目前参与的小组项目，我们必须模拟以下内容: 取一个边长为 n 的正方形。在正方形上均匀分布一定数量的单位圆盘。找到从正方形的左侧延伸到右侧的连接的磁盘组件之前所需的磁盘数。然后求直到方格完全被磁盘填满所需的磁盘数。

它没有明确说明，但我们假设这是在 Matlab 中完成的，因为我们在本类(class)的其他部分使用它。对于第一个问题，找到一条从左到右的路径，我编写了两种可行的方法。一个使用邻接列表和 Matlab 中的图形工具来查找连接的节点。这种方法足够快，但是对于我们需要做的事情来说占用了太多的内存。另一种方法使用递归搜索算法而不存储邻接信息，但速度太慢。

当我们需要正方形的大小为 n=1000 和 n=10000 时，问题就出现了。我们预测这将需要数千万个圆，或者更多，我们根本看不出我们应该如何处理这个，因为任何邻接列表或矩阵都会大得离谱，不使用一个似乎需要大量的时间。任何想法和想法都会受到赞赏，谢谢

Answer 1

让我们将您的问题重新表述为这样的决策问题:

Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they make a connected path from the left side to the right.

和:

Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they cover the entire square.

如果您可以解决这些决策问题，那么您可以通过对可能值进行二分搜索来找到 m 的最小值。

通过像这样生成磁盘，您可以在不使用大量 RAM 的情况下解决这些决策问题:

1. 使用给定的种子 s 初始化您的 PRNG
2. 对于每个圆盘 1 ... m，随机选择它将进入的列(即 floor(center.x))。累加所有列的计数以确定每个列中将放入多少个磁盘。设 COUNT(col) 为要在列 col
中生成的磁盘数
3. 对于 0 ... n-1 中的每个列，生成在该列内均匀分布的 COUNT(col) 个磁盘。

现在您主要是从左到右生成磁盘。上面的两个决策问题都有从左到右的解决方案，一次只需要看到一两列的磁盘，所以你只需要记住一两列的磁盘。

对于完全覆盖问题，从左到右计算并确定正方形中的每一列是否被完全覆盖，使用该列和相邻列的磁盘。没有其他磁盘可能到达。

对于左右路径问题，使用 union-find 从左到右计算以跟踪当前列中的哪些磁盘连接到左侧以及彼此连接。当您到达最后一列时，您可以检查最后一列中的任何磁盘是否连接到左侧并超出右侧。