0

我正在尝试生成一个具有可遍历和不可遍历位置的随机网格，并确保在 4 个方向之一{右、上、左、下}中存在从一个可遍历位置到任何其他可遍历位置的路径。可遍历位置表示为“[ ]”，不可遍历位置表示为“[X]”

Here is a grid I have generated: 
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][ ][X]
[ ][ ][X][ ][ ][ ][X][ ][ ][X][X][ ][ ][ ]
[X][ ][ ][ ][ ][X][X][X][ ][ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ][X][ ][ ][ ][X][ ][ ][X][ ]
[ ][X][ ][ ][ ][X][ ][ ][ ][ ][X][X][X][X]
[ ][ ][X][X][X][ ][ ][ ][X][X][X][X][X][X]
[ ][X][ ][ ][ ][X][ ][ ][ ][X][X][ ][ ][X]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][ ]
[ ][ ][X][ ][ ][ ][X][ ][X][X][ ][ ][ ][ ]
[ ][X][ ][X][ ][ ][ ][ ][ ][ ][X][X][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][X][ ]

我可以使用什么算法来查找网格中的不相交集并在不相交集之间创建路径？谢谢！

4

1 回答 1

3

要查找不相交的组件，您可以使用从任何可遍历位置开始的广度优先搜索（使用队列）或深度优先搜索（使用堆栈）。当搜索终止时，它将标记整个组件。然后，如果有未标记的位置，则将其用作另一个搜索的起点，等等，直到您标记了所有可遍历的位置。

为了弄清楚必须删除哪些不可遍历的位置，如果您希望（几乎）尽可能少地删除，请将每个“不相交集”（最好称它们为“连接组件”）视为一个节点中的单个节点图表，并查看连接它们的各种路径。计算将节点连接到另一个节点的每条路径必须删除的 X 的数量，并将其用作图中边的权重。然后你想找到该图的最小生成树，例如使用克鲁斯卡尔算法。

该方法不能保证找到要移除的最小 X 数以连接可遍历位置；例如，在您给出的图表中，删除右上角附近的单个 X 连接三个组件，而我的建议可能会导致删除两个 X。但是，您的问题含糊不清，因此我认为差异并不重要。

要找到要删除的 X 的确切最小数量，您必须解决“节点加权施泰纳树问题”，我相信这通常是 NP 难的。鉴于您的图形是平面的，您可能能够得到一个很好的近似值：http ://www-math.mit.edu/~hajiagha/NodePlanarSteiner.pdf 。

于 2015-04-10T05:13:40.253 回答