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

Question

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

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

我们应该将它减少到右侧,而不是使用左侧的例程.

3. 喜欢向右然后向下,除非下降比正确短.

在下面的例子中,我们不应该选择左侧解决方案,而是选择右侧的一个,因为它从(2,0)向下移动(向下移动,向下移动(2),而不是向右移动2) 0,1).

其他示例如下所示,这些都是最好的例程.

我正在研究这个问题一段时间.我已经研究了一些算法,如传递减少和Dijkstra,但没有弄明白.如果你想给我一些关于算法的提示,我可以调查一下这会很棒.

谢谢!

---

编辑2:

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

对于动态编程,我考虑了节点应该如何加入路径.优先级应如下:

但问题是它没有考虑动态视图的问题,这会输出错误的结果.

Answer 1

我认为您的示例都适合以下通用算法：同时向左和向上遍历 \xe2\x80\x94 从第一行和列的末尾开始，然后是第二行和列的末尾，依此类推。 \xe2 \x80\x94 将每个D遇到的路线延伸到最近的路线，D或者S（当然，N-NW-W 弧线中的曼哈顿距离）。

\n\n

实施例7：

\n\n

  1 2 3 4\n1 S     D\n\n2     D\n\n3   D\n\n4 D     D\n\n  1 2 3 4\n1 S-----D<\n  |\n2 |   D\n  |\n3 | D\n  |\n4 D     D\n  ^\n\n  1 2 3 4\n1 S-----D\n  |   |\n2 |   D  <\n  |\n3 |-D\n  |\n4 D     D\n    ^\n\n  1 2 3 4\n1 S-----D\n  |   |\n2 |   D\n  |\n3 |-D\n  |\n4 D-----D<\n        ^\n

\n\n

实施例5：

\n\n

  1 2 3 4\n1 S\n\n2       D\n\n3     D\n\n4 D     D\n\n  1 2 3 4\n1 S      <\n  |\n2 |     D\n  |\n3 |   D\n  |\n4 D     D\n  ^\n\n  1 2 3 4\n1 S\n  |\n2 |-----D<\n  |\n3 |   D\n  |\n4 D     D\n    ^\n\n  1 2 3 4\n1 S\n  |\n2 |-----D\n  |   |\n3 |   D  <\n  |\n4 D     D\n      ^\n\n  1 2 3 4\n1 S\n  |\n2 |-----D\n  |   |\n3 |   D--\n  |     |\n4 D     D<\n        ^\n

\n\n

示例1：

\n\n

  1 2 3 4\n1 S\n\n2     D\n\n3   D   D\n\n4     D\n\n  1 2 3 4\n1 S--\n    |\n2   --D  <\n    |\n3   D   D\n\n4     D\n    ^\n\n  1 2 3 4\n1 S--\n    |\n2   --D\n    |\n3   D---D<\n      |\n4     D\n      ^\n

\n