如何在这种情况下实现最短路径算法？

Question

我的任务中有一个MxN的网格

例如：

M = 5，N = 8

KKKK....
.###...X
.XX#...X
...#....
........

K - 起点，X - 终点，# - 障碍物

我需要找到从起点到终点搬运包裹所需的最少步数。我们一次只能搬运1个包裹，且不能斜着走。

这个例子的答案是20。

我的建议是实现A*算法，并针对每种可能性启动它（计算从每个起点到每个终点的最小步数），然后选择最小值，考虑到一个包裹覆盖一个终点的事实。

有更好的实现方法吗？

- MarJan

---

@Dementic 这是与语言无关的，OP建议使用A*算法并从每个可能性启动它，这是一个具体的解决方案建议。 - ggorlen

你能只使用每个起点和终点一次吗？ - Richard

@Dementic 不，跨语言的算法问题在 Stack Overflow 上是非常相关的话题。 - ggorlen

@ggorlen 在这个特定的例子中，这些包互相阻挡。我们不能斜着走，而且在这种情况下我们没有任何自由邻居。 - MarJan

@Richard，我的猜测是它将被测试在100x100的范围内，最多有10-20个起始点。 - MarJan

Answer 1

虽然我对此的实际了解有限，但我将尝试将问题表述为一种最小费用流问题。将每个起点视为源，每个终点视为汇。通过特定边缓冲流量f的成本为f*a，其中a是该边的成本。处理多个源和汇的惯用方法是将每个组连接到另一个单一实例。

初步制定：

称n为起点或终点的数量。

1. 将所有起点连接到具有流n的单个源，其中每条边都具有容量和流量1和成本0。 2. 将所有终点连接到具有每条边容量1和成本0的汇。 3. 所有其他边都具有无限容量（至少n似乎足够）和成本1。 4. 查找通过网络实现流n的最小费用。

图示：

imaginary source
 with edge to each
  S with capacity 1
 / /|\
S1S-S1S2.2.2.2.
2       | | | 2   imaginary sink
. # # # .-.-.-T -- with edge to
2       | | | 1     each T with
.2T1T # .-.-.-T --  capacity 1
                      |   |
. . . # . . . .

. . . . . . . .

（图中数字表示每条边的最优流量，它们加起来为20。）

- גלעד ברקן

---

你能给我一个实际的例子吗？因为我无法正确理解你的图表。管道连接起点和汇点，但是“2”代表什么？ - MarJan

@MarJan 图表中的数字是每条边的最优流量（它们加起来为20）。问题中的边是任何单个允许的移动。（我将没有预期流量的地方绘制为线条。）这有意义吗？ - גלעד ברקן

有道理，感谢澄清。我会尝试以这种方式实现，而不是使用A*算法。我会比较它们，然后选择更好的方法。谢谢 :) - MarJan

那么我的最大流应该等于n，其中n是起点/终点的数量？ - MarJan

@MarJan 我认为在网络中实现流量 n 的最小成本（如步骤4所建议的）并不是一个“最大流”问题，而是一个最小费用流问题。 - גלעד ברקן

在示例中，我觉得实现的流程是“n = 4”（起点或终点的数量），因为4个从源到汇点。 - גלעד ברקן