具有欺骗路径障碍物的矩阵中的最短路径
首先,这是一个保证,我不是在寻找直接的答案,而是您可能会想到的最佳解决方案的复杂性。
这是一个已知的问题,即矩阵中2个点(起点和终点)之间的路径" title="最短路径">最短路径有障碍物。向上,向下,向左和向右移动可接受的范围。可以说,移动时我携带某物,每次移动的成本为2。矩阵中有一些点(我将它们命名为B点),我可以在某一个B点中保留此点,然后从另一个B点中提取该点。B点的卸货成本为1,B点的卸货成本为1。每当我搬家时,现在搬家的成本是1。我认为解决方案是将矩阵转换为树并应用BFS。但是,没有B点也可以。
每当我考虑到B点的复杂性时,最坏的情况就是N ^ 2。这是一个例子:
S - - -- - - -
B - - B
- - O E
S =开始,E =结束,B = B点下降sth,O =障碍物因此,我从S开始向下移动到B点(2 * 2 = 4点),将sth留在B点(1点)右右(2 * 1
= 2分),拾起(1分),下移2分=总共10分。
我认为是用每个B点的节点构建树,但是这会创建一个几乎(V-1)*(V-1)边的非常密集的循环图,该图需要在N ^
2边界中采用算法才能创建图。那是上面最坏的情况:
S b b bb b b b
b b b b
b b b E
我认为的另一个选择是首先计算没有B点的最短路径。然后进行迭代,每次迭代时:首先在S上具有bfs,在E上具有BFS,在E上具有BFS,并且最接近B,然后查看在B上最接近S的B和B上最接近E的路径。如果有的话,我会看看路径是否小于带障碍的常规最短路径。如果那更大,那么就没有最短的路径(没有贪婪测试)。如果2个B点之间没有路径,请尝试第二个最接近S的点并重试。如果再次没有路径,则第二个最接近E且最接近S。但是,在最坏的情况下,我无法计算出这种复杂性,而且没有贪婪的测试可以评估这种复杂性。
回答:
您的矩阵是图形的表示。没有作弊路径,很容易实现良好的BFS。实施欺骗路径并不重要。只需在第一个图层的顶部添加与另一个“图层”相同的矩阵即可。底层是“携带”,顶层是“不携带”。对于给定的成本,您只能在B点移动到另一层。这是具有第三维的相同BFS。
您每层有n ^ 2个节点和(n-1)^ 2个边,并且最多有n ^ 2个连接这些层的节点。那是O(n ^ 2)。
以上是 具有欺骗路径障碍物的矩阵中的最短路径 的全部内容, 来源链接: utcz.com/qa/413979.html