用于在矩阵中找到从单个源到多个目的地的最佳路径的算法

Question

问题陈述:我们有一个 m * n 矩阵。起点是左上角的单元格。我们只能在矩阵中往下或者往右走。目的地是在矩阵中随机选择的。现在我们需要找到具有以下约束的最佳例程:

1. 路径上的每个节点只能有一个父节点，但最多有两个子节点。
2. 尽量减少重复路线。例如，如果我们的目的地如下所示:

与其使用左侧的例程，不如将其简化为右侧的例程。

1. 最好向右走然后向下走，除非向下走比向右走短。

在下面的示例中，我们不应该选择左侧的解决方案，而应该选择右侧的解决方案，因为它通过从 (2, 0) 向下移动 1 而不是向右移动到 (2, 1) 向下分支2 来自 (0, 1)。

其他例子如下，都是最好的套路。

我正在为此工作一段时间。我研究了一些算法，如传递归约和 Dijkstra，但没有弄明白。如果你想给我一些我可以研究的算法提示，那就太好了。

谢谢!

---

编辑 2:

我收到了一些关于 Dijkstra 算法和使用动态规划的想法。我认为对于 Dijkstra 算法，如果您能提供将此问题转换为图形问题的提示，那就太好了。我正在研究该算法并认为它的主要问题是不必访问单元格。在下面的示例中，如果我们删除其中一个目的地，则与左侧 map 相比，整个例程将发生重大变化。

对于动态规划，我有一个节点应该如何加入路径的想法。优先级应如下所示:

但问题是没有考虑动态 View 的问题，会输出错误的结果。

Answer 1

我认为您的示例都适合以下通用算法:同时向左和向上遍历 - 从第一行和第一列的末端开始，然后是第二行和第二列的末端，等等 - 扩展路线从每个 D 遇到最近的路线，D 或 S(当然是 N​​-NW-W 弧中的曼哈顿距离)。

示例 7:

  1 2 3 4
1 S     D

2     D

3   D

4 D     D

  1 2 3 4
1 S-----D<
  |
2 |   D
  |
3 | D
  |
4 D     D
  ^

  1 2 3 4
1 S-----D
  |   |
2 |   D  <
  |
3 |-D
  |
4 D     D
    ^

  1 2 3 4
1 S-----D
  |   |
2 |   D
  |
3 |-D
  |
4 D-----D<
        ^

示例 5:

  1 2 3 4
1 S

2       D

3     D

4 D     D

  1 2 3 4
1 S      <
  |
2 |     D
  |
3 |   D
  |
4 D     D
  ^

  1 2 3 4
1 S
  |
2 |-----D<
  |
3 |   D
  |
4 D     D
    ^

  1 2 3 4
1 S
  |
2 |-----D
  |   |
3 |   D  <
  |
4 D     D
      ^

  1 2 3 4
1 S
  |
2 |-----D
  |   |
3 |   D--
  |     |
4 D     D<
        ^

示例 1:

  1 2 3 4
1 S

2     D

3   D   D

4     D

  1 2 3 4
1 S--
    |
2   --D  <
    |
3   D   D

4     D
    ^

  1 2 3 4
1 S--
    |
2   --D
    |
3   D---D<
      |
4     D
      ^