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

Question

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

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

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

作业中需要计算每个未知网格的成本..（

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

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

http://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*，但想想看，它不适用于单源最短路径 - 问题很好。