Problem.Search

These search algorithms will solve our Problem, if it's soluble and not too hard. They all have different advantages and drawbacks.

For an introduction to search algorithms, read through this wonderful interactive visualization.

(I plan to add some precise information about their runtime complexity and space complexity.)

Graph Search

Graph search means that the algorithm assumes that the search space looks like a graph. This means that there might be multiple ways to arrive at a state. The algorithm therefore takes care of this and avoids visiting the same state twice.

Uninformed search

breadthFirst : Problem a -> Model a

depthFirst : Problem a -> Model a

uniformCost : Problem a -> Model a

Dijkstra's algorithm.

Informed search

greedy : Problem a -> Model a

bestFirst : Problem a -> Model a

A* search.

Tree Search

Tree search means that the algorithm assumes that the search space looks like a tree. This means that there will always be just a single way to arrive at a state.

Tree search is usually slightly more efficient than graph search (how much exactly?), but:

If we run tree search on a problem where the search space is not a tree, the algorithm might get stuck in cycles. Even if not, it will probably be less efficient than the corresponding graph search algorithm.
Unlike "real" tree search algorithms, the tree search algorithms in this library do also track all the explored states, because we want to have them available for visualization. There is still some performance advantage with tree search, but it is smaller than in "real" tree search, and might be asymptotically negligible. (I need to check this.)

treeBreadthFirst : Problem a -> Model a

treeDepthFirst : Problem a -> Model a

treeUniformCost : Problem a -> Model a

treeGreedy : Problem a -> Model a

treeBestFirst : Problem a -> Model a

Performing the search

The functions above only initialize a search model. We can use one of the functions in here to run the search model.

type alias Model a =

{ strategy : Strategy a

, queue : QueuePopper a

, problem : Problem a

, explored : Dict String (Node a)

, frontier : List a

, result : Result (Node a)

, maxPathCost : Float

}

This record represents the inner state of the search algorithm. You can integrate it into the model of your web application.

The type parameter a refers to the State type of the search problem. For example, if you want to search a sliding puzzle, you can import it with import Problem.Search.SlidingPuzzle exposing (State).

Initialize your model with searchInit (see below).

next : Model a -> Model a

Performs a single step of the search algorithm. Returns a new search model.

nextN : Int -> Model a -> Model a

Performs n steps of the search algorithm. Returns a new search model.

solve : Model a -> ( Maybe (Node a), Model a )

Tries to solve the search. Returns a pair of the result (if it can find one), and the search model.

exhaust : Model a -> Model a

Searches through the complete search space without stopping at solutions. Returns a new search model. Note that the complete search space is usually very large.

exhaustBoundary : (Node a -> Bool) -> Model a -> Model a

Searches through the search space until the boundary condition is no longer fulfilled. Returns a new search model. Could perhaps be used to implement IDA*, but I have not yet attempted that. Experimental.

Inspecting the Result

type Result a

= Pending

| Solution a

| Failure

The current result of any search.

Pending: No solution has been found, but the search has not yet exhausted the state space and more search steps can be performed.
Solution a: A solution has been found
Failure: The complete search space has been searched, but no solution could be found.

mapResult : (a -> b) -> Result a -> Result b

resultWithDefault : a -> Result a -> a

resultHasState : a -> Result (Node a) -> Bool

Internal infrastructure

Use these for building you own visualizations. First, check out the ready-made visualizations in the Problem.Search.Visual submodule.

type alias Node a =

{ state : a

, parent : Maybe a

, pathCost : Float

, children :

Maybe

(List

{ pathCost : Float

, state : a

}

)

}

expand :

Problem a

-> Node a

-> { updatedParent : Node a

, children : List (Node a)

}

path : Model a -> Node a -> List ( Float, a )

reversePathWithPosition : Model a -> Node a -> List ( Float, a, ( Int, Int ) )

unestrangedChildren : Model a -> Node a -> Maybe (List a)

davidpomerenke/elm-problem-solving/1.0.1