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

Question

这与您的普通 shortest/least-cost 路径问题有点不同，虽然我确实有一些解决它的一般想法，但它让我有点难过。我认为居住在 Stack Overflow 这个神圣之地的 STEM 大神们可能知道他们认为适合给我的解决方案，或者如果不知道，他们可能仍然喜欢尝试这个。

问题陈述：

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

r1 : 向右移动一个位置（与X轴平行+1个单位）。
r2 : 向右移动两个位置（+2 个平行于 X 轴的单位）。
u1 : 向上移动一个位置（+1 平行于 Y 轴的单位）。
u2 : 向上移动两个位置（+2 个平行于 Y 轴的单位）。

从任何给定的位置 (Xi, Yj)，这些移动中的每一个都有一个相关的成本，由 r1(Xi, Yj), r2(Xi, Yj), u1(Xi, Yj), u2(Xi, Yj)。（请注意，移动的成本可能会有所不同，具体取决于移动的位置）。

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

(problem statement attached image)

到目前为止我考虑的内容：

朴素的方法：计算从 (0, 0) 到 (n-1, m-1) 的每条可能路径的总权重，select成本最低的一个。
这种方法的问题：随着 n 和 m 的增加几乎立即变得不可行。
有趣的是，似乎通过一些 r1 和 r2 移动序列（没有任何向上移动）从 X=0 到 X = n-1 的总可能方式数是 Fibonacci(n-1), = 斐波那契数列的第 n-1th 项（其中 Fibonacci(0)=0, 斐波那契(1)=1, 斐波那契( 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 的最短路径算法进行某种修改？任何解决方案或见解将不胜感激:)

Answer 1

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

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

最初你只知道节点(n-1, m-1)与它自己的距离为0；并且您不知道从任何其他节点到 (n-1, m-1) 的任何路径；所以你将每个节点的距离初始化为 0 (n-1, m-1)，并为每个其他节点初始化 +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) 其中 returns 如果它存在 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(..., ..., ..., ...)操作选择的成本）。

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

Least cost path (traverse a grid), given a limited move-set, and in which moves' costs may differ at different positions?

algorithm

path

grid

traversal

weighted

问题陈述：

到目前为止我考虑的内容：