动态规划:在有障碍物的网格中寻找最短路径
动态规划:在有障碍物的网格中寻找最短路径
提问于 2017-01-04 07:22:33
我试图从Skiena的算法设计手册中解决以下问题
8-16考虑一个城市，其街道由X，x，Y网格定义。我们感兴趣的是从网格的左上角走到右下角。不幸的是，这座城市有着糟糕的社区，我们不想走进这些街区的十字路口。给出了一个坏的X×Y矩阵，其中BADi，j=“是”当且仅当街道i和j之间的交点在一个邻域以避免。(c)给出一个O(XY)算法，以在网格中找到避免不良邻域的最短路径。您可以假设所有块都具有相同的长度。对于部分信用，给出了O(X^2*Y^2)算法。
这个问题来自于关于动态规划的章节，在“图问题”的标题下。我知道我可以把它建模成一个无向无权图，它包含所有“好”交点和相邻“好”顶点之间的边的顶点。考虑到这是一个未加权的图，我可以从左上角开始进行宽度优先搜索，一旦到达右下角顶点，我就有了最短的路径。
鉴于这个问题来自于动态规划一章，我试图找出如何使用动态规划来解决这个问题。相交(i，j)的最短路为1+交叉口(i，j-1)，(i-1，j)，(i，j+1)，(i+1，j)的最短路径的最小路径。这个公式似乎不符合动态规划的重叠子问题性质。这个问题能用动态规划来解决吗？
回答 1
Stack Overflow用户
发布于 2017-01-04 07:40:39
实际上，这个公式完全符合动态规划的重叠子问题的性质。
在一阶中，相交的最短路径可以用相邻交叉口的最短路径来表示。因此，子问题。
在第二阶，多个交叉口可以共享相同的相邻交叉口，其最短路径是其他每个交叉口最短路径函数中的输入。因此，重叠子问题。
另外，Dijkstra的算法和Bellman算法都是动态规划算法的例子，它们将在给定的大O复杂度约束下解决您的示例问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41458292
复制相关文章
相似问题
腾讯云开发者
