首先，这是一项作业，我不是在寻找直接答案，而是在寻找您可能想到的最佳解决方案的复杂性。
这是矩阵中两点（起点和终点）之间有障碍物时的最短路径的已知问题。可接受的移动方式为上、下、左、右。假设在移动时我携带某物，每次移动的成本是 2 。矩阵中有一些点（让它们命名为 B 点），我可以将这个东西留在一个 B 点中，然后从另一个 B 点中拾取它。在 B 点倾倒某物的成本为 1，从 B 点再次拾取某物的成本为 1。每当我在没有这个东西的情况下移动时，我现在的移动成本是 1 。
我认为的解决方案是将矩阵转换为树并应用 BFS。然而，这在没有 B 点的情况下也有效。
每当我考虑 B 点复杂性时，最坏的情况就是 N^2。
这是一个例子：
S - - -
- - - -
B - - B
- - O E
S = 开始，E = 结束，B = B 点掉落某物，O = 障碍物
所以我从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 是很容易的。实施作弊路径并不是什么大问题。只需在第一个“层”之上添加与另一个“层”相同的矩阵即可。底层是“携带”，顶层是“不携带”。您只能在 B 点以给定的成本移动到另一层。这与第三维的 BFS 相同。
每层有 n^2 个节点和 (n-1)^2 条边，此外还有最多 n^2 个连接各层的边。那是 O(n^2)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
