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

Question

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

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

.................................................. ........................................##........ ........................................##........ ........................................##........ ..........######################################.. ........................................##........ ........................................##........ ........................................##........ ....################..........00........##........ ....################....................##........ ....################....................##........ ....################....................##........ ........................................##........ .................................................. ..................................................

作业中需要的是计算每个未知网格的成本（..），以便显示机器人为了到达该位置而必须进行的成本。

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

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

https://i.stack.imgur.com/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。二进制最小堆可以很好地作为优先级队列。（afaik，由于速度的原因，A* + 二进制最小堆在实时游戏中被大量使用）。

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