algorithm - 计算具有给定大小的非循环路径的不同矩形网格迷宫

Question

我正在尝试解决以下问题:

An mn maze is an mn rectangular grid with walls placed between grid cells such that there is exactly one path from the top-left square to any other square. The following are examples of a 912 maze and a 1520 maze:

Let C(m,n) be the number of distinct mn mazes. Mazes which can be formed by rotation and reflection from another maze are considered distinct.

It can be verified that C(1,1) = 1, C(2,2) = 4, C(3,4) = 2415, and C(9,12) = 2.5720e46 (in scientific notation rounded to 5 significant digits).
Find C(100,500)

现在，有一个给出正确结果的明确公式，而且它是完全可计算的。然而，据我所知，欧拉计划问题的解决方案应该更像是聪明的算法，而不是明确的公式计算。试图将解决方案表述为递归，我只能得到一个线性系统，其中变量的数量随着迷宫的大小呈指数增长(更准确地说，如果有人试图为 mxn 迷宫的数量写一个递归，其中 m 保持固定, 一个线性系统使得其变量的数量随 m 呈指数增长:其中一个变量是具有问题 380 声明中给出的属性的 mxn 迷宫的数量，而其他变量是 mxn 迷宫的数量在某些特定“配置”中接触迷宫边界的多个连接组件 - 并且此类“配置”的数量似乎随 m 呈指数增长。因此，虽然这种方法在 m = 2,3,4 等情况下是可行的，它似乎不适用于 m=100)。

我还想把问题简化为更容易解决的子问题，然后在构建更大子问题的解决方案(动态规划方法)时重用子问题的解决方案，但在这里我偶然发现子问题似乎涉及不规则形状的迷宫，而且这种迷宫的数量在 m,n 中呈指数级增长.

如果有人知道除了使用显式公式或一些特定定理之外的可行方法 (m=100, n=500)，并且可以提示去哪里寻找，对我来说这将非常有趣。

Answer 1

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

计算网格图中的生成树

来自维基百科条目的“计数生成树”部分:

The number t(G) of spanning trees of a connected graph is a well-studied invariant. In some cases, it is easy to calculate t(G) directly. For example, if G is itself a tree, then t(G)=1, while if G is the cycle graph C_n with n vertices, then t(G)=n. For any graph G, the number t(G) can be calculated using Kirchhoff's matrix-tree theorem...

相关算法

这里有一些与计算网格图中生成树的数量相关的论文或帖子:

• "Counting Spanning Trees in Grid Graphs ", Melissa Desjarlais 和 Robert Molina阿尔玛学院数学与计算机科学系，2012 年 8 月 17 日？ (发布日期不确定)
• “Counting the number of spanning trees in a graph - A spectral approach”，来自大学。 CMSC858W 的马里兰类笔记:生物序列分析算法，2010 年 4 月 29 日
• “Automatic Generation of Generating Functions for Counting the Number of Spanning Trees for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width”，作者:Shalosh B. Ekhad 和 Doron Zeilberger

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

If you want to see explicit expressions (as rational functions in z) for the formal power series whose coefficient of zn in its Maclaurin expansion (with respect to z) would give you the number of spanning trees of the m by n grid graph (the Cartesian product of a path of m vertices and a path of length n) for m=2 to m=6, the the input gives the output.

具体请参见 output .

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