英文:
Pathfinding on a grid while blocking cells online
问题
假设我们有一个N*N的网格，起点和终点分别是A和B，并且我们收到了K < N^2的在线查询，告诉我们在网格上封锁一个单元格。我们希望在每次查询后找到并输出A和B之间的最短路径。
除了在每次查询后重新计算最短路径（如果没有其他更好的解决方案的话），还有没有更好的解决方法呢？由于网格每次只改变一个单元格，感觉应该有办法利用先前查询的信息，而不是每次都从头开始计算。
英文:
Suppose we have a N*N grid with start and end points A and B, and we're given K < N^2 queries online telling us to block a cell on the grid. We want to find and output the shortest path between A and B after each query.
Is there a better solution to this than to recalculate the shortest path after each query (or if not, proof that there isn't)? Since the grid only changes one cell at a time, it feels like there must be some way to make use of information from previous queries without starting from scratch each time.
答案1
得分: 0
以下是翻译好的部分：
如果被阻塞的单元格不在最短路径上，那么最短路径不会改变 - 无需重新计算。
- 计算最短路径
- 单元格 X 被阻塞
- 循环 C 遍历最短路径
如果 C == X
重新计算最短路径
从循环 C 中退出
以下是更快的算法，如果您满意近似最短路径：
- 计算最短路径
- 设置 approxCount = 0
- 单元格 X 被阻塞
- 循环 C 遍历最短路径
如果 C == X
- 如果 approxCount < 小的任意整数
- 从前一个单元格到 C 到路径中 C 后面的单元格计算路径
- 插入绕过障碍物的路径
- 增加 approxCount- 否则
- 重新计算最短路径
- 设置 approxCount = 0 - 从循环 C 中退出
- 否则
小的任意整数应设置为您可以容忍的近似值。
绕过障碍物的路径计算应基于广度优先搜索，以便在找到路径时能够迅速停止。
英文:
If the cell that is blocked is NOT on the shortest path, then the shortest path is not changed - doesn't need to be recalculated.
- Calculate shortest path
* Cell X is blocked
- LOOP C over cells in shortest path
IF C == X
recalculate shortest path
Break from loop C
Here is a faster algorithm, if you are content with an approximate shortest path:
- Calculate shortest path
- Set approxCount = 0
* Cell X is blocked
- LOOP C over cells in shortest path
IF C == X
- IF approxCount < small arbitrary integer
- Calculate path from previous cell to C to cell after C in path
- Insert path around block
- Increment approxCount
- ELSE
- recalculate shortest path
- Set approxCount = 0
- Break from loop C
The small arbitrary integer should be set to a value that gives you approximations that you can tolerate.
The path calculation around the block should be based on a breadth first search so it can be stoppped quickly when a path is found.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论