具有欺骗路径障碍物的矩阵中的最短路径

  • Z时代
  • 2024-01-10
  • 分类：问答

首先，这是一个保证，我不是在寻找直接的答案，而是您可能会想到的最佳解决方案的复杂性。

这是一个已知的问题，即矩阵中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 b
b 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

回到顶部