使用Haskell查找网格上两点之间的最短路径

Question

这是一个我可以很容易地以非功能性方式解决的问题.

但是在Haskell中解决这个问题给了我很大的麻烦.在功能编程方面,我缺乏经验肯定是一个原因.

问题:

我有一个2D字段分为相同大小的矩形.一个简单的网格.一些矩形是空的空间(并且可以通过),而其他矩形是无法通过的.给定起始矩形A和目标矩形B,我如何计算两者之间的最短路径？只能垂直和水平移动,步骤单个矩形大.

我将如何在Haskell中完成此任务？代码片段肯定是受欢迎的,但肯定不是必要的.并且非常欢迎链接到更多资源!

谢谢!

Answer 1

我将网格表示为列表,类型[[Bool]].我定义了一个函数来知道网格元素是否已满:

type Grid = [[Bool]]
isFullAt :: Grid -> (Int, Int) -> Bool  -- returns True for anything off-grid

然后我定义一个函数来查找邻居:

neighbors :: (Int, Int) -> [(Int, Int)]

要查找非完全邻居,point可以过滤filter (not . isFullAt) $ neighbors point.

此时我将定义两个数据结构:

• 将每个点映射到 Maybe Cost
• 将已知成本的所有点存储在堆中

仅使用堆中的起始方A进行初始化,成本为零.

然后循环如下:

• 从堆中删除最小成本的正方形.
• 如果它不在有限映射中,请添加它及其成本c,并将所有非完整邻居添加到堆中并使用成本c+1.

当堆为空时,您将获得所有可到达点的成本,并且可以在有限映射中查找B.(这个算法可能被称为"Dijkstra算法";我已经忘记了.)

你可以找到有限的地图Data.Map.我假设在庞大的库中有一个堆(也就是优先级队列),但我不知道在哪里.

我希望这足以让你开始.