如果需要重新访问 BFS 中访问过的节点,时间复杂度是多少?
What is the time complexity if it needs to revisit visited nodes in BFS?
我正在研究一道算法题。
为了简化,问题可以简化为:
给定一个m * n矩阵,有一堆特殊点,在这个矩阵中找到从A点到B点的最优路径。
最优路径是经过最少特殊点的路径。如果有多条特殊点最少的路径,则选择最短的一条。如果还有多条路径,select其中随机一条。
这个问题完全可以用BFS来解决。要保持队列,记录每个点的信息。如果找到更好的路径,则更新信息并将该点放入队列中。最后在B点输出信息
棘手的部分是一个点可能会被多次重新访问,我无法估计这种情况下的时间复杂度。有人可以帮我吗?
最终目标是不打任何特殊点或尽可能少。您可以通过以下设置使用 Dijkstra: 普通边缘成本 1. 特殊点与所有其他成本之间的边缘超过 m*n
(因此,即使您在没有特殊节点的情况下穿过整个迷宫,也比走一个更好步骤,但通过特殊节点)。
然后你 运行 Dijsktra 你就拥有了。由于每个节点的边数最多(其矩阵,因此最多有 4 个方向),因此边数约为 4*m*n,即 O(m*n)
.
所以你的 V=(m*n)
和 E=O(m*n)
以及 Dijkstra 是 O(V + E*log E)
。把它放在那里你会得到 O(m*n + m*n * log(m*n)) = O(m*n*log(m*n))
我正在研究一道算法题。
为了简化,问题可以简化为:
给定一个m * n矩阵,有一堆特殊点,在这个矩阵中找到从A点到B点的最优路径。 最优路径是经过最少特殊点的路径。如果有多条特殊点最少的路径,则选择最短的一条。如果还有多条路径,select其中随机一条。
这个问题完全可以用BFS来解决。要保持队列,记录每个点的信息。如果找到更好的路径,则更新信息并将该点放入队列中。最后在B点输出信息
棘手的部分是一个点可能会被多次重新访问,我无法估计这种情况下的时间复杂度。有人可以帮我吗?
最终目标是不打任何特殊点或尽可能少。您可以通过以下设置使用 Dijkstra: 普通边缘成本 1. 特殊点与所有其他成本之间的边缘超过 m*n
(因此,即使您在没有特殊节点的情况下穿过整个迷宫,也比走一个更好步骤,但通过特殊节点)。
然后你 运行 Dijsktra 你就拥有了。由于每个节点的边数最多(其矩阵,因此最多有 4 个方向),因此边数约为 4*m*n,即 O(m*n)
.
所以你的 V=(m*n)
和 E=O(m*n)
以及 Dijkstra 是 O(V + E*log E)
。把它放在那里你会得到 O(m*n + m*n * log(m*n)) = O(m*n*log(m*n))