使用 Haskell 查找网格上两点之间的最短路径
这是一个我可以很容易地以非功能性方式解决的问题。
但用 Haskell 解决它给我带来了大问题。我在函数式编程方面缺乏经验肯定是一个原因。
问题：
我有一个二维字段，分为大小相等的矩形。一个简单的网格。有些矩形是空的（并且可以通过），而另一些则无法通过。给定一个起始矩形 A 和一个目标矩形 B，我如何计算两者之间的最短路径？只能垂直和水平移动，步长为单个矩形。
我将如何在 Haskell 中完成这个任务？代码片段当然受欢迎，但也肯定不是必需的。也非常欢迎链接到更多资源！
谢谢！
This is a problem that I can easily enough solve in a non-functional manner.
But solving it in Haskell is giving me big problems. Me being inexperienced when it comes to functional programming is surely a reason.
The problem:
I have a 2D field divided into rectangles of equal size. A simple grid. Some rectangles are empty space (and can be passed through) while others are impassable. Given a starting rectangle A and a destination rectangle B, how would I calculate the shortest path between the two? Movement is possible only vertically and horizontally, in steps a single rectangle large.
How would I go about accomplishing this in Haskell? Code snippets certainly welcome, but also certainly not neccessary. And links to further resources also very welcome!
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我将网格表示为列表的列表，输入
[[Bool]]。我会定义一个函数来了解网格元素是否已满：然后我会定义一个函数来查找邻居：
要查找
point的非完整邻居，您可以使用filter 进行过滤（不是 .isFullAt）$ 邻居点。此时，我将定义两个数据结构：
Maybe Cost仅使用堆中的起始方A进行初始化，成本为零。
然后按如下方式循环：
c添加到堆中，并使用成本c+1将所有非完整邻居添加到堆中。当堆为空时，您将获得所有可到达点的成本，并且可以在有限映射中查找B。 （这个算法可能被称为“Dijkstra 算法”；我忘了。）
您可以在
Data.Map中找到有限映射。我假设在巨大的库中的某个地方有一个堆（也称为优先级队列），但我不知道在哪里。我希望这足以让您开始。
I'd represent the grid as a list of lists, type
[[Bool]]. And I'd define a function to know if a grid element is full:Then I'd define a function to find neighbors:
To find non-full neighbors of
pointyou can filter withfilter (not . isFullAt) $ neighbors point.At this point I'd define two data structures:
Maybe CostInitialize with only the start square A in the heap, with cost zero.
Then loop as follows:
c, and add all the non-full neighbors to the heap with costc+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.
嗯，你的类型将决定你的算法。
您想使用什么数据类型来表示网格？二维数组？列表的列表？一棵树？图表？
如果您只想有向图中的最短路径，那么使用 FGL（函数图包）中的内容将是最好的。
Well, your types will determine your algorithms.
What data type do you want to use to represent the grid? A two-dimensional array? A list of lists? A tree? A graph?
If you just want shortest path in a directed graph, using something from the FGL (functional graph package) would be best.