计算/显示机器人（位置）在2D网格（阵列）上移动的最小成本

Question

我目前正在研究一个计算机器人移动成本（位置 x，y）的作业问题。

我们给出了带有多个障碍物（符号 ##）的 2D 网格（2 维数组）的尺寸。下面是一个示例网格。我们还给出了机器人的起始位置。在当前位置，它的“成本”为00（静止）。

<代码>...................................................... ... …………………………………… …………………………………… …………………………………… ..########################################.. …………………………………… …………………………………… …………………………………… ....################..........00......................................... ......################......................................................... ......################......................................................... ......################......................................................... …………………………………… ...................................................... ......................................................

作业中需要计算每个未知网格的成本 (..)，以便显示机器人移动到该位置所需的成本。

水平移动+2 前一个网格的成本。
对角线移动前一个网格的成本+3。
机器人不能越过障碍物，必须绕过它。
每个值必须具有最小成本（例如：对角线移动的成本比水平和垂直移动的成本少）。

下面是我们应该得到的结果（仅显示成本的最后两位数字，省略了一些值，因此更具可读性）：

https://i.sstatic.net/JiDl1.png

现在我无法想象/解决这个问题。我们被告知，它“在道德上就像冒泡排序算法”，每次找到新的最小成本时，所有内容都会重新计算。

抱歉，如果这非常令人困惑，任何建议（代码或伪代码将非常受欢迎）

Answer 1

恕我直言，可视化路径问题的最简单方法是作为一个连接的节点网络（图），其中邻居节点（机器人可以从当前位置移动到的方块）通过加权边相互连接（权重是移动成本）节点之间）。

N     @     N -2- N -2- N
|\         /|\   /|    /
2  3     3  2  3  2  3
|    \ /    |/   \|/
N -2- N -2- N -2- N     @

N = 节点，数字和线是带有权重的边，@ 是障碍

Djikstra 算法 是已经建议，有关更多选项，请参阅例如 http://en.wikipedia.org/wiki/Shortest_path_problem。 二进制最小堆可以很好地用作优先级队列。 （据我所知，由于速度的原因，A* + 二进制最小堆在实时游戏中被大量使用）。

编辑：我之前建议使用 A*，但仔细想想，它不适用于单源最短路径 - 问题那么好。