1

http://ideone.com/QXyVzR

上面的链接包含我编写的使用 BFS 算法解决迷宫的程序。迷宫表示为一个二维数组，最初以数字形式传入，（0 表示可以访问的空块，任何其他数字表示“墙”块），然后转换为我定义的记录类型，它保持跟踪各种数据：

type mazeBlock = {
    walkable   : bool;
    isFinish   : bool;
    visited    : bool;
    prevCoordinate : int * int
}

输出是有序对（坐标/索引）的列表，它们跟踪从起点到终点穿过迷宫的最短路径，其坐标都作为参数传入。

它适用于具有低分支因子的较小迷宫，但是当我在较大的迷宫（比如 16 x 16 或更大）上测试它时，尤其是在没有墙壁的迷宫（高分支因子）上，它会占用大量时间和内存。我想知道这是算法固有的还是与我实现它的方式有关。那里有任何 OCaml 黑客可以向我提供他们的专业知识吗？

另外，我对 OCaml 的经验很少，所以任何关于如何从风格上改进代码的建议都将不胜感激。谢谢！

编辑：

http://ideone.com/W0leMv

这是该程序的清理、编辑版本。我修复了一些风格问题，但没有改变语义。和往常一样，第二次测试仍然占用大量资源，似乎根本无法完成。仍在寻求有关此问题的帮助...

编辑2：

解决了。非常感谢两位回答者。这是最终代码：

http://ideone.com/3qAWnx

4

2 回答 2

2

在你的临界区，也就是说mazeSolverLoop，你应该只访问以前没有访问过的元素。当您从队列中取出元素时，您应该首先检查该元素是否已被访问，在这种情况下，除了递归获取下一个元素之外什么都不做。这正是算法具有良好时间复杂度的原因（您永远不会访问一个地方两次）。

否则，是的，您的 OCaml 样式可以得到改进。一些备注：

  • OCaml-land 中的约定是 towrite_like_this而不是writeLikeThis. 我建议您遵循它，但不可否认，这是一个品味问题，而不是一个客观标准。

  • 如果数据结构是已更新的可变结构，则返回数据结构毫无意义；(grid, pair)当队列与输入完全相同时，为什么要始终返回队列？您可以让这些函数返回unit并拥有更简单、更易于阅读的代码。

  • 对允许的抽象级别很好，您应该保留它；你目前没有。例如，写作没有意义let (foo, bar) = dimension grid in if in_bounds pos (foo, bar)。只需命名维度dim而不是(foo, bar)，如果您不需要单独使用它们，将其拆分为两个组件是没有意义的。请注意，对于邻居，您现在确实使用neighborXandneighborY进行数组访问，但这是一个风格错误：您应该有辅助函数来获取和设置数组中的值，将一对作为输入，这样您就没有破坏主函数中的对。尝试将单个函数中的所有代码保持在同一抽象级别：所有代码都在单独的坐标上工作，或者所有代码都在对上工作（这样命名而不是一直被构造/解构）。

于 2013-05-31T17:43:26.970 回答
0

如果我理解正确，对于没有墙壁的 N x N 网格，您有一个包含 N^2 节点和大约 4*N^2 边的图。对于 N = 16，这些似乎不是很大的数字。

我想说唯一的技巧是确保您正确跟踪访问过的节点。我浏览了您的代码，并没有发现您的操作方式有任何明显错误。

这是一个很好的 OCaml 习惯用法。你的代码说：

let isFinish1 = mazeGrid.(currentX).(currentY).isFinish in
let prevCoordinate1 = mazeGrid.(currentX).(currentY).prevCoordinate in
mazeGrid.(currentX).(currentY) <-
    { walkable = true;
     isFinish = isFinish1;
     visited = true;
     prevCoordinate = prevCoordinate1}

你可以这样说更经济一点：

mazeGrid.(currentX).(currentY) <-
    { mazeGrid.(currentX).(currentY) with visited = true }
于 2013-05-31T17:39:03.900 回答