algorithm - 瑞士奶酪有多防水？

Question

想象一块立方体形状的瑞士奶酪。我们通过 20x20x20 的网格对奶酪进行建模。为简单起见，我们假设每个网格立方体完全由奶酪或完全由空气组成。然后我们在瑞士奶酪立方体的上侧倒入水，水只能通过立方体中的气孔渗入奶酪。水可能会从顶部流到底部的连续通道，但如果两个立方体通过面（不仅仅是边缘或角落）连接，它可能只会从一个空气立方体流到下一个空气立方体。水也可以在弯道上流动，例如在水槽排水管中，但它可能不会在奶酪块的侧壁上流出。

现在让我们以编程方式实现瑞士奶酪的模型，如上所述，空气和奶酪块的随机分布，奶酪的概率为p，空气的概率为1 - p，并模拟水流过奶酪，以找出，水是否流到瑞士奶酪块的底部。

通过以不同的奶酪和空气概率反复模拟流过瑞士奶酪立方体的水，我们可以确定 p 与水流到瑞士奶酪立方体底部的概率之间的关系，我们将其命名为q。结果如下所示：

q
1   ************************
0.8                          *
0.6                           *
0.4                            *
0.2                             *
0                                 ***********
    0       0.2     0.4     0.6     0.8     1   p

我的问题：为什么会有这么奇怪的曲线？

本题摘自德国第 23 届联邦信息学竞赛（2004/2005）。网络上没有提供“为什么这么奇怪的曲线”的答案（提供的解决方案）。

我希望我在正确的地方提出这类问题。

Answer 1

也许你会发现下面的解释很直观：

在您的情况下，20 * 20 * 20 个单元格，除非您至少有 20 个孔，否则水流的概率正好为 0。如果您有 20 个孔，如果您将它们排列成一列，水可以流动，但概率这样随机出现的顺序非常低，20*20/Comb(20^3, 20) ~= 1e-57。随着孔数的增加，出现连续路径的可能性越来越大。

当除了 20*20 的所有单元格都是孔时，阻止流动的唯一方法是将所有奶酪单元格排列成一个“阻塞”层，例如水平 20*20 层。（还有其他可能的配置，但不太可能。每个 (x, y) 坐标都需要一个奶酪块，并且每个奶酪块必须与其所有 (x, y) 邻居接触。但它们可能是沿 z 轴分布）。

一旦你有少于 20*20 的奶酪块，你就不能形成一个完整的层，流动概率正好变成 1。

Answer 2

这是Zhenya评论的延伸。

如前所述，您的瑞士奶酪是渗透理论的一个例子。当我们考虑相变的主题时，这是统计力学的一个基本概念。渗透理论的典型例子之一与您发布的问题非常相似。

Erdős-Rényi 模型

在Erdős–Rényi 模型中，您从一个空图开始，并以概率 将节点与一条边连接起来p。在某个临界p值下，图的结构从一堆不连贯的集群变为一个包含大部分节点的大型跨越结构。事实上，如果您要绘制最大集群的平均大小，您会得到与您的瑞士奶酪模型非常相似的图片！示意图如下所示：

你会在应用数学和物理学的许多例子中找到它。图片的功劳来自Frontiers中的这篇文章，它更详细地讨论了这种现象。