algorithm - 使用 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
• 将具有已知成本的所有点存储在堆中

Initialize with only the start square A in the heap, with cost zero.

Then loop as follows:

• Remove a min-cost square from the heap.
• If it's not already in the finite map, add it and its cost c, and add all the non-full neighbors to the heap with cost c+1.

When the heap is empty, you will have the costs of all reachable points and can look up B in the finite map. (This algorithm may be called "Dijkstra's algorithm"; I've forgotten.)

You can find finite maps in Data.Map. I assume there's a heap (aka priority queue) somewhere in the vast library, but I don't know where.

I hope this is enough to get you started.

Answer 2

好吧，您的类型将决定您的算法。

您想使用什么数据类型来表示网格？二维数组？列表列表？一颗树？图表？

如果您只想要有向图中的最短路径，最好使用 FGL（功能图包）中的一些东西。