具有作弊路径障碍的矩阵中的最短路径
Shortest path in matrix with obstacles with cheat paths
首先，这是一个评估，我不是在寻找直接的答案，而是在寻找您可能认为的最佳解决方案的复杂性。
这是已知的矩阵中两点（起点和终点）之间有障碍物的最短路径问题。可接受的移动是上、下、左、右。可以说当我搬家时我携带某物并且每次移动的成本是 2 。矩阵中有一些点（让我们将它们命名为 B 点），我可以将它留在一个 B 点并从另一个 B 点拾取它。在 B 点倾倒某物的成本为 1，从 B 点再次捡起某物的成本为 1。每当我在没有这个的情况下搬家时，我现在搬家的成本是 1 。
我想到的解决方案是将矩阵转换为树并应用 BFS。然而，没有 B 点也是可行的。
每当我考虑到 B 点的复杂性时，最坏的情况就是 N^2。
这是一个例子：
S - - -
- - - -
B - - B
- - O E
S = Start , E = End , B = B point to drop sth, O = obstacle
所以我从 S 开始向下移动到 B 点（2*2=4 点）在 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 和最近的 B 上有 bfs
在 E 和最近的 B 上有 BFS
然后查看最接近 S 的 B 和最接近 E 的 B 之间是否有路径。
如果有那么我会看看路径是否小于有障碍物的常规最短路径。
如果它更大，那么就没有最短路径（没有贪心测试）。
如果 2 个 B 点之间没有路径，请尝试第二个最靠近 S 的点，然后重试。
如果没有再次路径，第二个最接近 E 和最接近 S。
但是，在最坏的情况下，我无法计算这一个的复杂性，而且没有评估它的贪婪测试。
任何有关计算复杂性甚至指出最佳复杂性解决方案（不是解决方案而只是复杂性）的帮助都将不胜感激
您的矩阵是图形的表示。没有作弊路径，很容易实现一个不错的 BFS。实施作弊路径没什么大不了的。只需在第一个矩阵之上添加与另一个 'layer' 相同的矩阵。底层是 'carry'，顶层是 'no carry'。您只能在 B 点以给定的成本移动到另一层。这是具有第三维的相同 BFS。
每层有 n^2 个节点和 (n-1)^2 条边，另外还有最多 n^2 个节点连接层。那是 O(n^2).
您可以构建一个新图，其中的节点标记为 (N, w)，其中 N 是原始图中的一个节点（因此是矩阵中的一个位置），w=0 或 1 表示您是负重。然后很容易在此图中添加所有可能的边
这个新图的大小是 2*V，而不是 V^2（边数约为 4*V+number(B)）。
然后你可以使用最短路径算法，例如Dijkstra的算法：复杂度O(E + V log(V)) 在你的情况下是O(V log(V))。
首先，这是一个评估，我不是在寻找直接的答案，而是在寻找您可能认为的最佳解决方案的复杂性。
这是已知的矩阵中两点（起点和终点）之间有障碍物的最短路径问题。可接受的移动是上、下、左、右。可以说当我搬家时我携带某物并且每次移动的成本是 2 。矩阵中有一些点（让我们将它们命名为 B 点），我可以将它留在一个 B 点并从另一个 B 点拾取它。在 B 点倾倒某物的成本为 1，从 B 点再次捡起某物的成本为 1。每当我在没有这个的情况下搬家时，我现在搬家的成本是 1 。 我想到的解决方案是将矩阵转换为树并应用 BFS。然而，没有 B 点也是可行的。
每当我考虑到 B 点的复杂性时，最坏的情况就是 N^2。 这是一个例子：
S - - -
- - - -
B - - B
- - O E
S = Start , E = End , B = B point to drop sth, O = obstacle 所以我从 S 开始向下移动到 B 点（2*2=4 点）在 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 和最近的 B 上有 bfs 在 E 和最近的 B 上有 BFS 然后查看最接近 S 的 B 和最接近 E 的 B 之间是否有路径。 如果有那么我会看看路径是否小于有障碍物的常规最短路径。 如果它更大，那么就没有最短路径（没有贪心测试）。 如果 2 个 B 点之间没有路径，请尝试第二个最靠近 S 的点，然后重试。 如果没有再次路径，第二个最接近 E 和最接近 S。 但是，在最坏的情况下，我无法计算这一个的复杂性，而且没有评估它的贪婪测试。 任何有关计算复杂性甚至指出最佳复杂性解决方案（不是解决方案而只是复杂性）的帮助都将不胜感激
您的矩阵是图形的表示。没有作弊路径，很容易实现一个不错的 BFS。实施作弊路径没什么大不了的。只需在第一个矩阵之上添加与另一个 'layer' 相同的矩阵。底层是 'carry'，顶层是 'no carry'。您只能在 B 点以给定的成本移动到另一层。这是具有第三维的相同 BFS。
每层有 n^2 个节点和 (n-1)^2 条边，另外还有最多 n^2 个节点连接层。那是 O(n^2).
您可以构建一个新图，其中的节点标记为 (N, w)，其中 N 是原始图中的一个节点（因此是矩阵中的一个位置），w=0 或 1 表示您是负重。然后很容易在此图中添加所有可能的边
这个新图的大小是 2*V，而不是 V^2（边数约为 4*V+number(B)）。
然后你可以使用最短路径算法，例如Dijkstra的算法：复杂度O(E + V log(V)) 在你的情况下是O(V log(V))。