Search

Input types for searches:

type alias Step state =

state -> List ( state, Bool )

Defines the type of the step function that produces new states from existing ones. This is how the graph over the search space is defined.

type alias Uninformed state =

{ step : Step state

, cost : state -> Float

}

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search.

type alias Informed state =

{ step : Step state

, cost : state -> Float

, heuristic : state -> Float

}

Defines the type of a bundle of operators that need to be supplied to conduct an informed (heuristic) search.

type alias WithBasicSearch a state =

{ a | step : Step state, cost : state -> Float }

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search. This is an extensible record so that heuristic searches can also take this type, making it easy to apply switch between heuristic and non-heuristic searches.

The search output type:

type SearchResult state

= Complete

| Goal state (() -> SearchResult state)

| Ongoing state (() -> SearchResult state)

Defines the possible outcomes of a search.

Helper functions for iterating searches to produce results:

next : SearchResult state -> SearchResult state

Steps a search result, to produce the next result. * The result of this function may be an Ongoing search. This will provide the current head search node and a continuation to run the remainder of the search.

nextN : Int -> SearchResult state -> SearchResult state

Continues a search result, to produce the next search goal up to a limited number of iterations. * This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete, or the iteration count is exhausted in which case an Ongoing search may be returned.

nextGoal : SearchResult state -> SearchResult state

Continues a search result, to produce the next search goal. * The result of this function will never be an Ongoing search. This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete. * If the search is bad and no goal can ever be found, this function may infnite loop.

Uninformed search strategies:

breadthFirst : WithBasicSearch a state -> List state -> SearchResult state

Performs an unbounded breadth first search. Breadth first searches store a lot of pending nodes in the buffer, so quickly run out of space.

depthFirst : WithBasicSearch a state -> List state -> SearchResult state

Performs an unbounded depth first search. Depth first searches can easily fall into infinite loops.

depthBounded : WithBasicSearch a state -> Int -> List state -> SearchResult state

Implements an uninformed search that is bounded to a specified maximum depth.

costBounded : WithBasicSearch a state -> Float -> List state -> SearchResult state

Implements a cost bounded search. This search will proceed depth first.

uniformCost : WithBasicSearch a state -> List state -> SearchResult state

Performs a uniform-cost search. This always follows the search node that has the lowest path cost. It is called a uniform cost search because the boundary of the search will have a roughly uniform cost as the search space is searched by increasing cost.

iterativeDeepening : Int -> WithBasicSearch a state -> List state -> SearchResult state

Implements an iterative deepening search. This search proceed depth first but repeats at progressively larger depth limits. The iteration number is multiplied by a specified multiple to calculate the maximum depth allowed at a given iteration.

iterativeCostIncreasing : Float -> WithBasicSearch a state -> List state -> SearchResult state

Implements an iterative cost increasing. This search proceed depth first but repeats at progressively larger cost limits. The iteration number is multiplied by a specified multiple to calculate the maximum cost allowed at a given iteration.

Informed search strategies:

aStar : Informed state -> List state -> SearchResult state

Performs an A* search. This is one that always follows the search node that has the highest f value (f = heuristic + cost). The seach will only be optimal if the heuristic function is monotonic.

greedy : Informed state -> List state -> SearchResult state

Performs a greedy heuristic search. This is one that always follows the search node that has the highest h value (h = heuristic).

fBounded : Informed state -> Float -> List state -> SearchResult state

Implements a cost bounded search. This search will proceed depth first and does not use the heuristic to order search nodes at all.

the-sett/ai-search/3.1.0