4

我试图解决以下问题：

mn 迷宫是一个 mn 矩形网格，其墙壁放置在网格单元之间，这样从左上角的正方形到任何其他正方形都只有一条路径。以下是 912 迷宫和 1520 迷宫的示例：

在此处输入图像描述

令 C(m,n) 为不同的 mn 迷宫的数量。可以通过旋转和从另一个迷宫反射形成的迷宫被认为是不同的。

可以验证 C(1,1) = 1, C(2,2) = 4, C(3,4) = 2415, 和 C(9,12) = 2.5720e46（科学计数法四舍五入到 5 位有效位数）。
找到 C(100,500)

现在，有一个明确的公式可以给出正确的结果，并且它是完全可计算的。但是，据我了解，欧拉计划问题的解决方案应该更像是聪明的算法，而不是显式的公式计算。试图将解决方案表述为递归，我只能得到一个线性系统，其中变量的数量随着迷宫的大小呈指数增长（更准确地说，如果有人试图为 mxn 迷宫的数量编写一个递归，并且 m 保持固定，到达一个线性系统，其变量的数量随着 m 呈指数增长：其中一个变量是 mxn 迷宫的数量，具有问题 380 声明中给出的属性，而其他变量是 mxn 迷宫的数量在某些特定的“

我还想将问题简化为可以更容易解决的子问题，然后在构造更大的子问题的解决方案时重用子问题解决方案（动态编程方法），但在这里我偶然发现了子问题似乎涉及不规则迷宫的事实形状，同样，这种迷宫的数量是 m,n 的指数。

如果有人知道一种可行的方法（m=100，n=500），而不是使用显式公式或一些特别定理，并且可以提示在哪里寻找，对我来说这将非常有趣。

4

4 回答 4

5

这基本上是一个生成树计数问题。具体来说，它是计算网格图中生成树的数量。

计算网格图中的生成树

从维基百科条目的“计算生成树”部分：

连通图的生成树数量 t(G) 是一个经过充分研究的不变量。在某些情况下，直接计算 t(G) 很容易。例如，如果 G 本身是一棵树，则 t(G)=1，而如果 G 是具有 n 个顶点的循环图 C_n，则 t(G)=n。对于任何图 G，数字 t(G) 可以使用基尔霍夫矩阵树定理来计算...

相关算法

以下是一些与计算网格图中的生成树数量相关的论文或帖子：

Ekhad 和 Zeilberger 的后者提供了以下内容，其答案与手头的问题相匹配：

如果您想查看形式幂级数的显式表达式（作为 z 中的有理函数），其 Maclaurin 展开式中的 zn 系数（相对于 z）将为您提供 m x n 网格图的生成树数（对于 m=2 到 m=6，m 个顶点的路径和长度为 n) 的路径的笛卡尔积，输入 给出输出。

具体来说，请参见输出。

旁注：如果没有提供的解决方案值表明其他情况，一个有效的解释可能是迷宫的外部结构很重要。在这种情况下，两个或多个具有相同路径的迷宫将不同且截然不同，因为在拐角处进入和退出迷宫可能有 3 个选项，其中左上角将在顶部打开，左上角在左侧打开，或在左侧和顶部都打开，对于拐角出口也类似。如果试图将这些迷宫的可能性表示为一棵树，两个节点可能会在入口处收敛，而不仅仅是从开始到结束发散，并且会有一个或多个额外的节点用于退出可能性。这将增加 C(m,n) 的值。

于 2013-02-28T15:15:04.933 回答
4

这里的见解来自问题（强调我的）

.. 迷宫是一个矩形网格，其墙壁放置在网格单元之间，因此从左上角的正方形到任何其他正方形只有一条路径。

如果你想到迷宫的对偶，即一个人可以占据的空间，很明显迷宫必须形成一个图形。也不只是任何图，因为要存在单一路径，该图不能包含任何使其成为树的循环。这种对组合问题的简化表明了一种算法。本着 Project Euler 的精神，其余部分留给读者作为练习。

于 2013-02-28T21:46:25.957 回答
1

前方剧透

我错了，在其中一条评论中说“现在，有一个关于在图中生成树的一般定理，但它似乎没有给出一种计算上可行的方法来计算所寻求的数字”。“一般定理”，即矩阵树定理，归因于 Kirchhoff，并在此处的答案之一中提到，不仅给出了图拉普拉斯算子的非零特征值除以图的阶数的乘积，但也作为拉普拉斯算子的任何辅因子的绝对值，在这种情况下，它是 49999x49999 矩阵的行列式的绝对值。但是，尽管矩阵非常稀疏，但在我看来它仍然遥不可及。

然而，参考

http://arxiv.org/pdf/0712.0681.pdf

（Luca Guido Molinari 的“块三对角矩阵的行列式”）允许将问题简化为对整数 100x100 密集矩阵的行列式的评估，该矩阵具有非常大的整数作为其条目。

此外，参考

http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf

作者：Erwin H. Bareiss（通常只说“Bareiss 算法”，但我使用的递归在参考文献中被称为公式（8），似乎是由于 Charles Dodgson，又名 Lewis Carroll :)） ，然后允许我评估最后一个决定因素，从而获得原始问题的答案。

于 2013-04-04T08:02:04.600 回答
0

我想说找到一个明确的公式是解决欧拉问题的正确方法。它会很快，可以扩展。去吧：）

于 2013-02-25T11:38:27.490 回答