module Uninf_search: sig .. end
Methods for uninformed search.
Note: Some of these Algorithms might not terminate, depending on the search space
val dfsearch : start:'a ->
childgen:('a -> 'a list) ->
goaltest:('a -> bool) ->
combinator:('a -> bool -> 'b option -> 'b option) -> 'b option
Simple Depth First Search.
Works in Space Complexity O(b*d) where d is the depth of the Search space and b
is the maximum branching factor. Might not terminate when the search space is infinit.
Also the solution might not always be optimal. Use with caution.
val boundeddfsearch : start:'a ->
childgen:('a -> 'a list) ->
goaltest:('a -> bool) ->
combinator:('a -> bool -> 'b option -> 'b option) -> depth:int -> 'b option
Bounded Depth First Search.
Similar to dfsearch, but will only search to a given maximum depth. Might not find a
solution if it is below that depth. Also the solution might not be optimal.
Returns the result of the combinator at the final node
start : the start node
childgen : function to generate a list of childs for a given node
goaltest : a test to see if a given node is a goal
combinator : a combinator to build a solution from the path. This function is passed the combined history to the current node, the current node and a bool indicating the result of the goaltest. Have a look at the supplied combinators, to see how this works.
depth : the depth to which the search space is searched
val iterativedfs : start:'a ->
childgen:('a -> 'a list) ->
goaltest:('a -> bool) ->
combinator:('a -> bool -> 'b option -> 'b option) -> 'b option
Iterated Depth First Search.
An iterated Version of the Bounded Depth First Search. Keeps increasing the depth
every iteration. Will find a optimal solution if there is one.
Returns the result of the combinator at the final node
start : the start node
childgen : function to generate a list of childs for a given node
goaltest : a test to see if a given node is a goal
combinator : a combinator to build a solution from the path. This function is passed the combined history to the current node, the current node and a bool indicating the result of the goaltest. Have a look at the supplied combinators, to see how this works.
val bfsearch : start:'a ->
childgen:('a -> 'a list) ->
goaltest:('a -> bool) ->
combinator:('a -> bool -> 'b option -> 'b option) -> 'b option
Breadth first search.
Simple BFS that works in time space and time O(b^d) where d is the depth of the solution and b the maximum branching factor of the search space.
Will find a optimal solution if there is one.
Returns the result of the combinator at the final node
start : the start node
childgen : function to generate a list of childs for a given node
goaltest : a test to see if a given node is a goal
combinator : a combinator to build a solution from the path. This function is passed the combined history to the current node, the current node and a bool indicating the result of the goaltest. Have a look at the supplied combinators, to see how this works.
val exhaustive_search : start:'a ->
childgen:('a -> 'a list) ->
goaltest:('a -> bool) ->
combinator:('a -> bool -> 'b option -> 'b option) -> 'b list
Exhaustive search of the search space. Wont terminate if the search space is infinite or contains loops, since then there are infinitely many solutions possible.
Returns a list of all solutions and the combined paths up to them.
start : the start node
childgen : function to generate a list of childs for a given node
goaltest : a test to see if a given node is a goal
combinator : a combinator to build a solution from the path. This function is passed the combined history to the current node, the current node and a bool indicating the result of the goaltest. Have a look at the supplied combinators, to see how this works.
val res_comb : 'a -> bool -> 'a option -> 'a option
very simple combinator.
Use this one if you are just interested in the node that satisfies the goaltest, but not
the path leading up to that node.
val path_comb : 'a -> bool -> 'a list option -> 'a list option
another very simple cobinator. Use this one to get the path leading up to the
result in the form of a simple list.