矩阵中最短的路径以及带欺骗路径的障碍物 [英] Shortest path in matrix with obstacles with cheat paths
问题描述
首先，这是一个保证，我不是在寻找直接的答案，而是您可能会想到的最佳解决方案的复杂性.
First of all this is an assingment and I am not looking for direct answers but instead the complexity of the best solution as you might be thinking it .
这是已知的矩阵中两个点(起点和终点)之间最短路径同时有障碍物的问题.向上，向下，向左和向右移动可接受的范围.可以说，移动时我携带某物，每次移动的成本为2.矩阵中有一些点(我将它们命名为B点)，我可以在某一个B点中保留此点，然后从另一个B点中提取该点.在B点卸货的成本为1，从B点卸货的成本再为1.每当我搬家时，现在搬家的成本是1. 我认为该解决方案是将矩阵转换为树并应用BFS.但是，没有B点也可以.
This is the known problem of shortest path between 2 points in a matrix (Start and End) while having obstacles in the way. Moves acceptables is up,down,left and right . Lets say when moving i carry sth and the cost of each movement is 2 . There are points in the matrix (lets name them B points) where I can leave this sth in one B point and pick it up from another B point . Cost of dumping sth in B point is 1 and cost of picking sth up from a B point is 1 again . Whenever I move without this sth , my cost of moving now is 1 . What I think of the solution is transform the matrix into a tree and have a BFS applied . However that works without the B points .
每当我考虑到B点的复杂性时，最坏的情况就是N ^ 2. 这是一个示例:
Whenever i take into account the B points complexity comes to a worst case scenario N^2. Here is an example :
S - - -
- - - -
B - - B
- - O E
S =开始，E =结束，B = B指向下降点，O =障碍物 所以我先从S向下移动到B点(2 * 2 = 4点)在sth的B点(1点)上右移(2 * 1 = 2点)，将其拾起(1点)，下移2分=总共10分.
S = Start , E = End , B = B point to drop sth, O = obstacle So i start with S move down down to the B point (2*2=4 points) leave sth in the B point (1 point ) move right right (2*1= 2 points ) , pick it up (1 point ) , move down 2 points = total of 10 points .
我认为是用每B个点构建带有节点的树，但是这会创建一个非常密集的，几乎(V-1)*(V-1)边的循环图，这会使N ^ 2边界的算法达到创建图. 这是上述最坏的情况:
What i thought was build the tree with nodes every B point , however this would create a very dense cyclic graph of almost (V-1)*(V-1) edges which takes the algortithm in N^2 boundaries just to create the graph . That is the worst case scenario as above :
S b b b
b b b b
b b b b
b b b E
我认为的另一种选择是首先计算没有B点的最短路径. 然后进行迭代，每次迭代: 首先在S和最接近的B上有bfs E上有BFS，B最接近 然后查看最接近S的B和最接近E的B之间是否存在路径. 如果有的话，我会看看路径是否小于带障碍物的常规最短路径. 如果那更大，那么就没有最短的路径(没有贪婪测试). 如果2个B点之间没有路径，请尝试最靠近S的第二个点，然后重试. 如果再次没有路径，则第二个最接近E且最接近S. 但是，在最坏的情况下，我无法计算这种复杂性，而且没有贪婪的测试可以评估这种复杂性.
Another option I thought was that of first calculating shortest paths withouth B points . Then have iterations where at each iteration : First have bfs on S and closest B have BFS on E and closest B Then see if there is a path between B of closest to S and B closest to E . If there is then I would see if the path is smaller than that of regular shortest path with obstacles . If that is bigger then there is no shortest path (no greedy test). If there is no path between the 2 B points , try second closest to S and try again . If no path again , the second closest to E and closest to S . However I am not able to calculate the complexity in this one in the worst case scenario plus there is no greedy test that evaluates that. Any help on calculating the complexity or even pointing out the best complexity solution (not the solution but just the complexity ) would be greatly appreciated
推荐答案
您的矩阵是图形的表示形式.没有作弊路径，很容易实现良好的BFS.实施欺骗路径并不重要.只需在第一个图层的顶部添加与另一个图层"相同的矩阵即可.底层是携带"，顶层是不携带".对于给定的成本，您只能在B点移动到另一层.这是具有第三维的相同BFS.
Your matrix is a representation of a graph. Without the cheat paths it is quite easy to implement a nice BFS. Implementing the cheat paths is not a big deal. Just add the same matrix as another 'layer' on top of the first one. bottom layer is 'carry', top layer is 'no carry'. You can move to the other layer only at B-points for the given cost. This is the same BFS with a third dimension.
您有n ^ 2个节点，每层有(n-1)^ 2个边缘，另外最多有n ^ 2个连接这些层的节点.那是O(n ^ 2).
You have n^2 nodes and (n-1)^2 edges per layer and additionally a maximum of n^2 eges connecting the layers. That's O(n^2).
这篇关于矩阵中最短的路径以及带欺骗路径的障碍物的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
