java - 将 boolean 矩阵转换为图结构的有效方法？

Question

我正在研究一个迷宫问题，其中迷宫以二维数组表示，因此，如果元素为false，则正方形将无法遍历，反之亦然。我实现了一种求解方法，该方法以深度优先的方式递归尝试遍历起点的所有相邻正方形，该方法应能正常工作。

但是，我想击败DFS算法，我想到了将迷宫简化为图形的想法（也许尝试为边缘分配权重），并在图形上执行DFS，而不是在图中的每个正方形迷宫。我遇到的问题是，我将迷宫变成抓斗的方式似乎效率很低。这是将布尔矩阵变成图形的方法的概述：

我从第0行开始，遍历从索引0、0到索引n，0的每一行，然后从0,1 .. n，1直到n，n。编辑：澄清：我让迷宫的x值先增加。然后，我在下一段中垂直链接节点。

我将矩阵的真值称为空心正方形。
*如果板的边缘上有一个白色正方形，我将在Node类中创建一个新的子类Opening。我将保留对该节点的引用。继续向右，如果我遇到一个十字路口，或者如果下一个正方形是黑色，则在两者之间建立一个节点和一个桥。如果我从一个黑色的正方形过渡到一个白色的正方形，并且如果右边的下一个正方形不是黑色，则创建一个节点，并在该节点和该行的下一个节点之间建立一条边。

将所有节点添加到节点列表中。然后，我遍历（0，0），（0，1），...，（0，n），（1，0），（1，1）..（1，n）的所有列。并在所有未用黑色正方形分隔的节点之间制作边线。

这似乎是处理事情的一种非常昂贵的方法。我很想听听有关如何正确执行此操作的任何建议。

F F F F F F F F F F F F F
T T F T T T T T T T T T F
F T F F F F F F F T F F F
F T T T F T T T F T F T F
F F F T F T F T F F F T F
F T F T F T F T T T T T F
F T F T F T F F F F F F F
F T T T F T T T T T T T F
F T F F F F F F F F F T F
F T F T T T T T T T T T F
F T F T F F F F F F F T F
F T T T F T T T T T T T T
F F F F F F F F F F F F F

将使这些节点：

. . . . . . . . . . . . .
O O . O . . . . . O . O .
. . . . . . . . . . . . .
. O . O . O . O . . . . .
. . . . . . . . . . . . .
. . . . . . . O . . . O .
. . . . . . . . . . . . .
. O . O . O . . . . . O .
. . . . . . . . . . . . .
. . . O . . . . . . . O .
. . . . . . . . . . . . .
. O . O . O . . . . . O O
. . . . . . . . . . . . .

这没有显示边缘，但是也许您知道了。

Answer 1

我有两个解决方案，其中一个已经实施。在我开始解释第一种算法之前，这里要假设该算法所基于的一些假设：

假设条件


就以下方面而言，迷宫是最小的：迷宫的边界砖包含可行走的瓦片T，或者整个迷宫仅由不可行走的瓦片F组成。
迷宫定义了一个矩形或换句话说：迷宫的每一行都有相同数量的列。


算法

我将通过使用一个更简单的示例来解释该算法，仍然涉及许多重要情况。考虑以下由5行3列组成的迷宫：



步行瓷砖T为绿色，而墙面瓷砖F为蓝色。

该算法的第一阶段从（x，y）=（0，0）开始，通过访问顺时针移动的边界砖来寻找可步行的边界砖。它更喜欢具有少于或多于2个开放边缘的可步行瓷砖。开放边缘是我们知道一个节点但不知道另一个伙伴节点的边缘。

它从图块（x，y）=（0，0）开始，并找到具有2个开放边（以白色箭头表示）的可行走节点。它存储候选节点（用橙色圆圈表示）并继续，以期找到如上所述的首选节点。

在步骤5，找到具有3个开放边缘的由瓦片（2、2）表示的优选节点。它将节点标记为unprocessed（表示为带有白色或灰色背景的圆圈），并终止第一阶段。

第二阶段将选择一个任意的unprocessed节点并通过确定开放边缘的伙伴节点对其进行处理，直到不再有unprocessed节点为止。之后，它将节点标记为processed。确定伙伴节点可能导致将其他节点标记为unprocessed。



唯一可以选择的unprocessed节点是第一阶段中位于（2，2）的边界节点。该算法将其选中（由背景为灰色的圆圈表示）。任意选择的开放边缘表示为灰色箭头（在我们的示例中为南方）。

现在，该算法通过沿walkable磁贴移动直到找到一个节点（一个边缘少于或多于2个或作为算法开始的磁贴）来搜索伙伴节点。

在我们的案例中，算法在步骤6中找到了可步行图块（0，2）表示的伙伴节点。由于此节点既未标记为processed也未标记为unprocessed，因此将其标记为unprocessed（由具有白色背景的圆圈表示）。现在，开放边缘的伙伴节点为linked（用黑色箭头表示），反之亦然。



该算法继续选择所选节点的开放边缘，直到所有开放边缘都链接到其伙伴节点。在我们的示例中，下一个任意拾取的开放边指向西。

该算法沿着可步行的图块移动，并找到由图块（0，2）表示的伙伴节点，该结点已在其之前找到并且已标记为unprocessed。因此，它链接了两个节点的开放边缘，并继续指向北的最后一个开放边缘。

它找到与以前相同的节点，并链接最后一个开放边。现在，在（2，2）处的选定节点不再具有开放的边缘，因此算法将其标记为processed（由具有绿色背景的圆圈表示）。

该算法继续选择任意一个unprocessed节点，在（0，2）处找到由图块表示的唯一一个可用节点。但是由于该节点没有任何开放边缘，因此将其立即标记为processed并继续。

没有更多的unprocessed节点可用，因此算法终止。

适用于OP示例

如果应用于您提供的示例，则结果图将更小，而不会丢失有关导航迷宫的任何信息。让我们看一下您的图形（由于缺少一些节点，我必须完成它）：



左图显示了示例和建议的算法得出的图形。右图显示了我所描述的算法找不到的节点，因为可以在不丢失任何导航信息的情况下对其进行优化。它们要么被边缘取代，要么被完全消除。结果如下所示：



左图显示了替换项，而右图只是其压缩版本。该图从25个节点减少到8个节点，从23个边缘减少到7个边缘。总体上减少了2/3个节点和边缘。

有趣的角落案例

在实施算法时，我发现了一些有趣的特例，我想与您分享。我将匆忙完成算法以保持图像较小。希望您已经了解该算法的工作原理。


单个可行走的瓷砖，因此完全没有边缘：





仅寄宿生砖是可步行的：





所有瓷砖都可以步行：





较好的边界砖具有单边：