时间戳

首页 > 解决方案 > 给定有限的移动集，最小成本路径（遍历网格），以及不同位置的移动成本可能不同？

algorithm - 给定有限的移动集，最小成本路径（遍历网格），以及不同位置的移动成本可能不同？

问题描述

这对您的普通最短/最低成本路径问题有点旋转，虽然我确实有一些解决它的一般想法，但它让我有点难过。我认为居住在 Stack Overflow 这个神圣地方的 STEM 众神可能知道他们认为适合授予我的解决方案，或者如果没有，他们可能仍然喜欢尝试解决这个问题。

问题陈述：

存在一个与 X 和 Y 轴对齐的方形网格，其尺寸为n x m （其中 (0,0) 表示最左边和最底角， (n-1, m-1) 表示最右边和最顶角） . 从任何给定的位置，您都可以在某个方向上移动一定数量的步数，如给定的移动集所定义的那样。在这个问题中，我们考虑一个移动集，它允许从网格上的任何点选择以下四个移动中的任何一个：

从任何给定的位置 (Xi, Yj)，这些移动中的每一个都有由r1 (Xi, Yj)、r2 (Xi, Yj)、u1 (Xi, Yj)、u2 (Xi, Yj) 给出的相关成本。（请注意，移动的成本可能会因移动的位置而异）。

您的目标是以最小的总成本从 (0,0) 移动到 (n-1, m-1)。
设计一个有效的算法来做到这一点。推导出时间复杂度。

（问题说明附图）

到目前为止我所考虑的：

Naïve 方法：计算从 (0, 0) 到 (n-1, m-1) 的每条可能路径的总权重，并选择成本最低的路径。
这种方法的问题：随着n和m的增加，几乎立即变得不可行。
有趣的是，似乎通过 r1 和 r2 移动的某个序列（没有任何向上移动）从 X=0 到 X = n-1 的可能方式总数是Fibonacci( n-1 )，= n-斐波那契数列的第1项（其中Fibonacci( 0 ) =0, Fibonacci( 1 ) =1, Fibonacci( 2 )=1 等）。u1 和 u2 的情况相同，从 Y=0 变为 Y = m-1。虽然，我不确定考虑这个是否真的相关？...
无论如何，很明显需要一种更有效的技术。

贪婪方法：在每一步做出局部最优选择（例如，只选择每回合在当前位置具有最佳 (move_weight)/(spaces_moved) 比率的移动，只要它不超过 n-1 或 m-1 ）。
这种方法的问题：具有良好的时间复杂度，但我认为简单地在每个位置选择局部最优选择并不能保证全局最优路径。例如，当前位置的局部最佳移动可能是权重为 5 的 r1，其次是权重为 8 的 u2 下一步移动；但可能是这样的情况，在这一回合移动权重为 7 的 u2 允许我们移动权重为 3 的 r1 以进行下一步。然后，很明显，这种贪心方法不是全局最优的，因为当存在通往同一目的地的不同路径且成本=10 时，它产生了成本=13 的路径。

...这就是我现在所处的位置。我正在考虑尝试某种涉及树的解决方案（比如游戏树？），或者接下来可能对 Dijkstra 的最短路径算法进行某种修改？任何解决方案或见解将不胜感激:)

标签： algorithmpathgridtraversalweighted

解决方案

这正是最短路径问题。您可以使用 Dijkstra 算法。该算法包括存储从每​​个节点到目标节点（n-1，m-1）的“迄今为止已知的最短距离”。或者，存储从每个节点到起始节点 (0, 0) 的“迄今为止已知的最短距离”。

因此，您创建了一个 n*m 数组来存储所有这些距离。

最初您只知道节点 (n-1, m-1) 与自身的距离为 0；并且您不知道从任何其他节点到 (n-1, m-1) 的任何路径；因此，对于（n-1，m-1）将每个节点的距离初始化为 0，对于每个其他节点将距离初始化为 +Infinity。

然后迭代地选择一个节点，并通过查看其邻居并选择最有用的邻居来更新其最短的已知节点：

dist[x, y] = min(
                 dist[x, y],
                 dist[x+1, y] + cost_r1[x,y],  // being careful if x+1 is out of bounds
                 dist[x+2, y] + cost_r2[x,y],  // being careful if x+2 is out of bounds
                 dist[x, y+1] + cost_u1[x,y],  // being careful if y+1 is out of bounds
                 dist[x, y+2] + cost_u2[x,y],  // being careful if y+2 is out of bounds
                )

Dijkstra 的算法停止条件基本上是“继续更新，直到没有可更新的内容”。这可以以多种方式实现。

在我们的例子中，我们知道图形是一个网格，并且我们知道我们只会向右或向上移动，所以我们可以聪明地直接以正确的顺序更新距离；我们唯一需要确定的是，在计算到 (x,y) 的距离时，我们必须已经计算出到 (x+1,y)、(x+2,y)、(x, y+1) 和 (x,y+1)。

因为我们必须格外小心那些 +1 和 +2 不会让我们离开数组，所以您可以在处理其余部分之前处理列 n-1 和 n-2 以及行 m-1 和 m-2数组，或者您可以编写一个包装函数，如果它存在则dist(x,y)返回dist[x,y]，或者如果 x 或 y 超出范围则返回 +Infinity。

下面，我选择不使用包装函数，而是为单元格制作了单独的循环，其中并非所有四个选项 u1、u2、r1、r2 都可用。

dist[n-1, m-1] = 0

dist[n-2, m-1] = cost_r1[n-2, m-1]
for (x = n-3; x >= 0; x--)
    dist[x, m-1] = min(dist[x+1,m-1] + cost_r1[x,m-1], dist[x+2,m-1] + cost_r2[x,m-1])

dist[n-1, m-2] = cost_u1[n-1, m-2]
for (y = m-3; y >= 0; y--)
    dist[n-1, y] = min(dist[n-1,y+1] + cost_u1[n-1,y], dist[n-1,y+2] + cost_u2[n-1,y])

dist[n-2, m-2] = min(...r1, ...u1)
for (x = n-3; x >= 0; --x)
    dist[x, m-2] = min(...r1, ...r2, ...u1)
for (y = m-3; y >= 0; --y)
    dist[n-2, y] = min(...r1, ...u1, ...u2)

for (x = n-3; x >= 0; x--)
    for (y = m-3; y >= 0; y--)
        dist[x,y] = min(...r1, ...r2, ...u1, ...u2)

一旦你这样做了，你在我们数组dist的每个单元格中都有从 (x,y) 到 (n-1, m-1) 的距离。特别是，单元格 (0,0) 包含从 (0, 0) 到 (n-1, m-1) 的距离。

然后，如果您不仅对距离感兴趣，而且对要遵循的实际路径感兴趣，您可以使用此数组在线性时间内检索它，方法是从 (0, 0) 开始并导航到最小化成本的相邻单元格（即将由min(..., ..., ..., ...)操作选择的那个）。

推荐阅读