1

我正在尝试解决 OCaml 中的谜题 15 游戏。我几乎什么都做了。。除了程序的核心功能，深度优先搜索功能。这就是我的函数现在的样子：

let df_search_path (Graph next) start =
    let rec from_node visited a =
            print(a);
             if List.mem a visited then raise Fail
             else if goal(a) then [a]
                  else a::from_list (a::visited) (next a)
        and from_list visited nextA = match visited with
            [] -> raise Fail
                | nextA::rest -> try from_node visited nextA
                          with Fail -> from_list visited rest
in from_node [] start;;

Graph是一个图，next是一个搜索 2,3 或 4 个下一步移动的函数（我移动空白区域），goal是一个检查当前a状态是否是目标并且Fail是正常异常的函数。

我尝试了很多其他功能，它们运行良好。

这个函数总是在起始状态无限循环，我不明白为什么。 print是一个自定义函数，以友好的形式打印状态a。

我究竟做错了什么？我正在使用远离解决方案的状态“1 move”进行测试，只需“go down”即可解决此问题..但它卡在第一个状态，总是打印开始配置！

4

2 回答 2

4

我怀疑你的错误只是inmatch visited with ..而不是match nextA with ...in from_list。

let df_search_path (Graph next) start =
    let rec from_node visited a =
            print(a);
            if List.mem a visited then raise Fail
            else if goal(a) then [a]
            else a::from_list (a::visited) (next a)
        and from_list visited nextA = match nextA with
            | [] -> raise Fail
            | nextA::rest -> try from_node visited nextA
                             with Fail -> from_list visited rest
in from_node [] start;;

也就是说，还有其他方法可以改进代码：目前，“已访问”仅存储该搜索路径已访问过的节点，而不是迄今为止访问过的所有节点；迁移到全局保存并在任何节点的所有“子搜索”之间共享的数据结构将减少无用搜索的数量（如果您只想要一条通向目标的路径）。

最后，在这里使用列表是一个相当糟糕的主意，因为List.mem时间与列表的大小成线性关系；这给出了一个整体的二次行为。您应该使用专门用于成员资格检查的数据结构，例如Set（或者可能是与您的问题域相对应的数据结构：例如，在类似迷宫的搜索中，布尔矩阵通常更简单且更有效）。

于 2013-02-03T16:50:51.700 回答
2

很难确切地看出这段代码应该如何工作。这是我看到的：

您使用 计算要访问（出现）的节点列表next a。在from_list函数中，您不使用此列表。相反，您将visited列表的第一个元素重命名为nextA并重新访问它。您似乎只是一遍又一遍地重新访问第一个已经访问过的节点。我不明白为什么from_list会关心访问的节点。很可能它只会将列表传递给from_node.

于 2013-02-03T16:35:16.520 回答