4

有一个博物馆组织为 NxN 房间。部分房间上锁且无法进入。其他房间是开放的，有些房间有警卫。守卫只能通过开放的房间和博物馆内的南北东和西移动。对于每个房间，找出到警卫的最短距离。你的算法的时间复杂度是多少？

4

8 回答 8

3

首先，考虑一种相对幼稚的方法。

将每个守卫 G 作为房间集合中的一个顶点，R=N*N，以及相邻房间（边）E 之间的可能路径。

如果必须知道所有房间的最小距离，则从每个警卫到每个房间的 BFS。

这应该需要时间G * (R+E)，或者类似G*(N*N+E)，或者G*(N*N)。

这当然可以通过记忆来优化，因为每个 BFS 将重复计算已经完成的子树。根据房间配置，这可以大大降低上述时间复杂度的 G。但是，我确信一定有比这更好的东西。

于 2010-07-24T21:27:00.313 回答
2

图形解决方案 每个房间都是一个节点 只有在门打开的房间之间才有边，使用 Floyd–Warshall 算法，然后检查每个房间和每个警卫之间的最小距离

房间数量 - R = N^2

守卫人数 - G

时间复杂度为 O(R^3 +R*G)= O(R^3) = O(N^6)

弗洛伊德-沃歇尔的 R^3

于 2010-07-24T21:32:32.887 回答
2

如果我们用人工源和从源到每个警卫的零长度边来扩充博物馆图，那么单源最短路径树，可通过 BFS（未加权）/Dijkstra（加权）在时间Õ(n 2 + g )，给出从每个房间到最近警卫的距离。

于 2010-07-25T02:22:52.277 回答
2

这是IVlad和throwawayacct提到的最佳解决方案 ( O(N^2) ) 的摘要。出于某种原因，他们的声音没有被听到:)

将 NxN 网格视为一个图形，其中节点代表房间，边代表相邻房间之间的门。所有边的权重为 1。一组节点 U 被标记为“守卫房间”。

这个想法是使用 BFS 遍历，它从连接到所有受保护房间的新节点开始，并从 v0 开始按距离递增的顺序扫描房间。每次访问一个节点时，到达该节点所走的步数代表了到一个被看守的房间的距离，并且由于路径扩展顺序，它保证是最小的：

Add an artificial node v0 and connect it to all nodes in U
Create a simple queue Q, that stores pairs <node, dist>
Q.enqueue(<v0, -1>) 
Create a hash set S, that contains all visited nodes
S.add(v0)
while not Q.isEmpty() {
    pathTail := Q.dequeue()
    output distance pathTail.dist for node pathTail.node
    for all neighbours v of pathTail.node
        if not S.contains(v)
            Q.add(<v, pathTail.dist + 1>)

    S.add(pathTail.node)

}

复杂性分析

请注意，该图是平面的，所以我们有 |V|+|E|=O(|V|)。因此，这个 BFS 在 O(|V|)=O(N^2) 时间内运行。

我们对边有统一的权重这一事实使事情变得简单；保证队列具有单调的距离值。以 dijkstra 为例，边的权重可能不同，因此需要优先级队列，这会影响时间复杂度。这里提出的相同问题，房间之间的权重不同，需要 O(N N log N) 时间。

于 2010-07-25T09:58:23.497 回答
0

您只需将该博物馆视为一张图并使用 Dijikstra 算法。

维基链接

您在给定页面上讨论了复杂性。

于 2010-07-24T21:24:52.903 回答
0

您可以在本系列文章中找到 Dijkstra 的最短路径算法：

广度和深度优先搜索

于 2010-07-24T21:25:31.640 回答
0

我假设一个函数 edgeCost(i,j) 返回从房间 i 到房间 j 的转换成本（如果没有，则为无限，否则为 1）。edgeCost(i,i) = 0 并且没有负循环。设 R 为房间数（在您的情况下，R = N^2）：

int path[R][R];
/*
 * Each path[i][j] is initialized to
 * edgeCost(i,j) or infinity if there is no 
 * edge between i and j.
 */

function play():
 for k = 1 to R:
  for i = 1 to R:
   for j = 1 to R:
    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

或者您可能知道，Floyd-Warshall 算法（所有对最短路径），时间复杂度为 O(|R|^3)。

于 2010-07-24T21:47:35.920 回答
0

有一个队列，每个条目都包含一个正方形的地址和一个整数。将所有守卫的位置放在一个队列中，每个都用整数“0”标记。每个方格都应该有一个数字的空间，并且它们最初都应该是空白的。

然后，只要队列中有东西，就从队列中拉出一个条目，并检查有问题的方块是否有标记值。如果是这样，只需忽略该队列条目并继续下一个。否则，用队列中的值标记方格，并将所有可直接到达的相邻方格放入队列中，其值比当前当前条目的值高一个（以便从队列中拉出第一批方格，他们将获得值“1”）。每个方块在空白时只会被访问一次，并且每个被访问的方块最多会导致四个更多的方块被排队，因此通过队列的物品总数将是方块数量的四倍，再加上守卫的数量. 通过在将每个正方形添加到队列之前检查它是否为空白，可以轻松地将这个值减少一个常数因子；这不会消除所有冗余排队，但会消除一些。

于 2010-07-25T02:29:16.723 回答