4

我正在实施一种算法来找到一组房间中的最小跨度走廊。目前我已经弄清楚了算法，我只是想实现它。其中一部分涉及找到给定房间的所谓“特殊点”。矩形的“特殊点”是与另一个矩形的最远点的距离最小的点。例如：在此处输入图像描述

房间 R1 的特殊点是 v6 或 v7，因为它们与 R1 以外的矩形中最远点的最小距离相同。同样，矩形 R8 的特殊点是 v13 或 v14，因为它们到矩形中除 R8 之外的最远点的最小距离相同。目前我有邻接列表中表示的点，列表中的每个相邻点。此外，我在邻接列表中的每个房间都将其每个边界点作为值。我也对它所属的每个房间都有每一分。

目前，我正在通过查看到该点周围每个矩形中最远点的距离来计算特殊点。虽然速度很快，但在以下示例中显然失败了： 在此处输入图像描述

由于我当前的实现将 V1 和 V2 识别为 R9 的特殊点的平局，当显然 V2 是特殊点时（因为从 V2 到 R3 中最远点的距离明显小于从 V1 到最远点的距离在 R2)。我可以通过计算图中所有矩形的最远点的距离并选择最小值来实现它，但是我觉得有一种更有效的方法。我的想法是对房间进行排序并只检查一些房间，但是我仍然没有完整的算法。有任何想法吗？

提前致谢。

4

2 回答 2

2

总之，我建议同时从源矩形上的所有点运行 Dijkstra 算法，并修改停止条件。该算法在搜索过程中跟踪目前找到的当前最低特殊距离，并且不会进一步搜索已经比目前最低特殊距离更远的点。下面的一些伪代码，它使用字典来存储目标点 =>（最佳距离，源点）映射。

enqueue all points on source rectangle
special distance = infinity
while (queue not empty) {
    point = dequeue
    if (distance to point < best distance found to point AND 
        distance to point < special distance) {
        best distance found to point = distance to point
        rect = rectangle of point
        if (all points found in rect) {
            special distance to this rect = max(distances found to this rect)
            if (special distance to this rect < special distance) {
                special distance = special distance to this rect
            }
        } 
    }
}

激励细节如下：

您可以运行Dijkstra 的算法来查找从源矩形上的每个源点到一组目标点的所有点。本质上，Dijkstra 的算法是广度优先搜索，如果它满足从源点到该点的最短路径的条件，则仅从队列头部的点开始搜索。

如果你使用这个条件，你会找到到所有点的最短路径。然后，您可以计算每个目标矩形的最长距离，并取其中的最小值——该源点的“特殊距离”（然后为源矩形上的每个点重新运行并找到最低的特殊距离）。然而，这是太多的工作，因为您将在搜索中包含许多远离源点且您不需要考虑的点。

您可以做的是保持在算法运行期间找到的当前最低特殊距离，通过发现何时找到矩形的所有点并相应地更新当前最低特殊距离（它从某个高数字开始，如INT_MAXC ）。然后，您可以通过说它们与源点的距离也必须小于当前的最低特殊距离来增加获取点的条件（显然，如果当前点比当前最低特殊距离更远，那么您将无能为力更好地考虑从它引出的路径。）

如果您要为每个矩形寻找特殊点，您可能需要考虑运行Floyd–Warshall 算法，该算法将计算每对点之间的最短距离。

于 2013-06-01T22:34:35.703 回答
1

这不是一个完整的答案。它旨在确认/制定“特殊点”的定义。

来自OP的报价：

矩形的“特殊点”是与另一个矩形的最远点的距离最小的点。

这是我的理解。v*房间的特殊之处r在于：

在此处输入图像描述

在哪里

  • V_r是房间周围的顶点集r
  • R是所有房间的集合
  • D(v,v')是两个给定顶点之间的距离

所以，可以看出：

  • 目标顶点v'被选择为尽可能远离v
  • 但v'必须在目标房间内r'，选择该房间以最小化距离

如果我对这个定义不太了解，那么您应该能够v*(r)仅使用 3 个嵌套循环进行蛮力搜索。

当然，您对更有效的方法感兴趣。但是，首先要确保我正确理解“特殊点”。

于 2013-06-02T15:43:53.277 回答