1

I am trying to solve the puzzle 15 game in OCaml. I almost did everything.. except for the core function of the program, the depth first search function. This is what my function looks like now:

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 is a graph, next is a function that searches for the 2,3 or 4 next moves (I move the empty space), goal is a function to check if current a state is the goal and Fail is a normal exception.

I tried a lot all the other functions and they works well.

This function endlessy loops always in the starting state, and I can't understand why. print is a custom function to print the state a in a friendly form.

What am I doing wrong? I'm making my test using a state "1 move" far from the solution, just a "go down" will solve this.. but it is stuck in the first state, always printing the start configuration!

4

2 に答える 2

4

あなたのエラーはinmatch visited with ..ではなくだけだと思います。match nextA with ...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;;

とはいえ、コードを改善する方法は他にもあります。現在、「visited」には、これまでにアクセスしたすべてのノードではなく、この検索パスによってアクセスされたノードのみが格納されます。グローバルに保存され、任意のノードのすべての「子検索」間で共有されるデータ構造に移動すると、無駄な検索の数が減ります (ゴールにつながるパスのみが必要な場合)。

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 に答える