CODEWITHSUNDEEP
searchocamlbacktrackingdepth
HypeZ
HypeZ

Reputation: 4127

Can't do backtrack research in OCaml

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!

Upvotes: 1

Views: 1224

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

It's difficult to see exactly how this code is supposed to work. Here's something I see:

You calculate a list of nodes to visit (it appears) with next a. In the from_list function, you don't use this list. Instead you rename the first element of the visited list as nextA and revisit that. It seems you're simply revisiting the first already visited node over and over. I don't see why from_list would care about the visited nodes at all. Most likely it would just pass the list along to from_node.

Upvotes: 2

gasche
gasche

Reputation: 31469

I suspect your error is only the match visited with .. instead of 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;;

That said, there are other ways the code could be improved: currently, "visited" only stores the node that have been visited by this search path, instead of all the nods visited so far; moving to a data structure that is preserved globally and shared between all the "children searches" of any node would reduce the number of useless searches (if you only want a path that leads to the goal).

Finally, using a list here is a rather bad idea as List.mem takes time linear in the size of the list; this gives an overall quadratic behavior. You should rather use a data structure specialized in membership checking, such as Set (or maybe a datastructure that corresponds to your problem domain: in labyrinth-like searches for example, a matrix of booleans is usually simpler and more efficient).

Upvotes: 4

Related Questions