1

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

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

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

4

1 回答 1

0

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

从 PRNG 的种子s开始，在n x n方格中随机分布m个单位圆盘，并确定它们是否形成从左侧到右侧的连通路径。

和：

从PRNG的种子s开始，在n x n方格中随机分布m个单位圆盘，并确定它们是否覆盖整个方格。

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

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

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

现在您主要从左到右生成磁盘。上述两个决策问题都有从左到右的解决方案，并且一次只需要查看一两列中的磁盘，因此您只需要记住一两列磁盘。

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

对于左右路径问题，使用 union-find 从左到右工作，以跟踪当前列中的哪些磁盘连接到左侧并相互连接。当您到达最后一列时，您可以检查最后一列中的任何磁盘是否连接到左侧并延伸到右侧。

于 2017-05-05T13:54:16.673 回答