上面的链接包含我编写的使用 BFS 算法解决迷宫的程序。迷宫表示为一个二维数组,最初以数字形式传入,(0 表示可以访问的空块,任何其他数字表示“墙”块),然后转换为我定义的记录类型,它保持跟踪各种数据:
type mazeBlock = {
walkable : bool;
isFinish : bool;
visited : bool;
prevCoordinate : int * int
}
输出是有序对(坐标/索引)的列表,它们跟踪从起点到终点穿过迷宫的最短路径,其坐标都作为参数传入。
它适用于具有低分支因子的较小迷宫,但是当我在较大的迷宫(比如 16 x 16 或更大)上测试它时,尤其是在没有墙壁的迷宫(高分支因子)上,它会占用大量时间和内存。我想知道这是算法固有的还是与我实现它的方式有关。那里有任何 OCaml 黑客可以向我提供他们的专业知识吗?
另外,我对 OCaml 的经验很少,所以任何关于如何从风格上改进代码的建议都将不胜感激。谢谢!
编辑:
这是该程序的清理、编辑版本。我修复了一些风格问题,但没有改变语义。和往常一样,第二次测试仍然占用大量资源,似乎根本无法完成。仍在寻求有关此问题的帮助...
编辑2:
解决了。非常感谢两位回答者。这是最终代码: