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

Question

这是一个我可以通过非功能性方式轻松解决的问题。

但是在 Haskell 中解决它给我带来了很大的问题。我在函数式编程方面经验不足肯定是一个原因。

问题:

我有一个二维字段，分为大小相等的矩形。一个简单的网格。一些矩形是空的空间(可以通过)，而另一些是不可通过的。给定起始矩形 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
• 将已知成本的所有点存储在堆中

仅使用堆中的起始方 block A 进行初始化，成本为零。

然后循环如下:

• 从堆中移除一个最小成本方 block 。
• 如果它不在有限映射中，则添加它和它的成本 c，并将所有非完整邻居添加到堆中，成本为 c+1。

当堆为空时，您将拥有所有可达点的成本，并且可以在有限映射中查找B。 (这个算法可能叫“Dijkstra算法”，忘记了。)

您可以在 Data.Map 中找到有限映射。我假设在庞大的库中某处有一个堆(又名优先级队列)，但我不知道在哪里。

我希望这足以让您入门。