1

首先，这是一个评估，我不是在寻找直接的答案，而是在寻找最佳解决方案的复杂性，正如您所想的那样。

这是矩阵中两个点（起点和终点）之间的最短路径的已知问题，同时有障碍物。移动可接受的是上、下、左和右。假设移动时 i 携带某物，每次移动的成本为 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 = 障碍 所以我从 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，在最近的 B 在 E 和最近的 B 上有 BFS 然后看看在最接近 S 的 B 和最接近 E 的 B 之间是否有路径。如果有，那么我会看看路径是否小于有障碍物的常规最短路径。如果它更大，那么就没有最短路径（没有贪心测试）。如果 2 个 B 点之间没有路径，请尝试第二个最接近 S 的点，然后重试。如果再没有路径，第二个最接近E，最接近S。但是，在最坏的情况下，我无法计算这一复杂性，而且没有贪婪的测试来评估它。

4

2 回答 2

0

您的矩阵是图形的表示。没有作弊路径，很容易实现一个好的 BFS。实施作弊路径并不是什么大问题。只需在第一个顶部添加与另一个“层”相同的矩阵。底层是'carry'，顶层是'no carry'。对于给定的成本，您只能在 B 点移动到另一层。这是具有第三维的相同 BFS。

每层有 n^2 个节点和 (n-1)^2 个边，另外最多有 n^2 个连接层的边。那是 O(n^2)。

于 2017-04-11T21:49:02.623 回答
0

您可以使用 (N, w) 标记的节点构建一个新图，其中 N 是原始图中的一个节点（因此是矩阵中的一个位置），而 w=0 或 1 是您是否携带重量。然后很容易在这个图中添加所有可能的边

这个新图的大小为 2*V，而不是 V^2（边数约为 4*V+number(B)）。

然后您可以使用最短路径算法，例如 Dijkstra 算法：复杂度 O(E + V log(V)) 在您的情况下为 O(V log(V))。

于 2017-04-12T07:25:40.500 回答