小编Daw*_*Shi的帖子

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

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

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

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

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

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

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

谢谢!

编辑2:

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

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

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