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

Question

我目前正在做一道作业题，计算机器人(位置 x，y)的移动成本。

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

................................................ ……
...................................##.......
...................................##.......
...................................##.......
.........########################################..
...................................##.......
...................................##.......
...................................##.......
....################.......00.......##.......
....################.......................##......
....################.......................##......
....################.......................##......
...................................##.......
.....................................................
.....................................................

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

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

下面是我们应该得到的结果(只显示成本的最后两位数字，省略了一些值，以便更易读):

http://i.stack.imgur.com/JiDl1.png

现在我无法想象/解决问题。我们被告知，它“在道德上类似于冒泡排序算法”，每次找到新的最小成本时，一切都会重新计算。

如果这非常令人困惑，我们深表歉意，任何建议(代码或伪代码将非常受欢迎)

Answer 1

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

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

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

Djikstra's algorithm已经建议，更多选项参见例如http://en.wikipedia.org/wiki/Shortest_path_problem . Binary min heap作为优先队列工作得很好。 (afaik，A* + 二进制最小堆由于速度原因在实时游戏中使用很多)。

编辑:我之前建议使用 A*，但后来想起来，它不适用于单源最短路径 - 这么好的问题。