Clojure

A*search [ start goal move-generator :keys [selector filter debug]

Please read the guide to breadth-search before these notes.

A*search provides a simple, partially optimised implementation of an A*, cost sensitive search mechanism.

breadth-search takes 3 arguments...

· start state

· goal state/fn – either a predicate to take a state determine if it is a goal or a state equal to the goal

· legal move generator

...and 3 (optional) key arguments...

· get-state – removes cost & other information from a state returning only the raw state

· get-cost – removes other information from a state returning only the cost

· selector – takes list of states & selects the next one to explore from

· debug – when true, the search prints some information as it runs

– see default operations specified below.

The legal move generator is a function which takes a state representation as its only argument and returns a collection of successor states.

Goal states are (by default) detected using the "=" function. This is often over-simplistic (there may be multiple goal states for example). To deal with cases like this the goal may be specified as a predicate which returns non-false if it is passed a goal state.

default operation

This A*search allows a default state structure as follows...

{:state s, :cost c, ...other keys...}

Where s is a raw state and c is a numeric cost value. If this structure is used get-state and get-cost do not need to be provided nor does the selector function (assuming that costs are to be minimised).

If other structures are to be used then get-state and get-cost should be provided.

If you require an alternative to the default selector function – please check the comments in the source code.

example – using defaults

This example is based on a numbers puzzle where one number can be transformed into another using siimple rules. In this case the rules allow a number to be incremented, have 5 added or be doubled. Each operation incurs a cost.

Number transformations and costs are specified in a legal move generator as follows...

(defn a*lmg [state]

(let [n (:state state)

c (:cost state)

]

(list

{:state (+ n 1), :cost (+ c 2)}

{:state (+ n 5), :cost (+ c 7)}

{:state (* n 2), :cost (+ c 1)}

)))

The A*search will find the "cheapest" route from some start state to a goal and, because the state representation is the default, key arguments are not needed.

user=> (A*search {:state 0, :cost 0} (fn [x] (> x 20)) a*lmg)

( {:state 0, :cost 0} {:state 1, :cost 2} {:state 2, :cost 3}

{:state 4, :cost 4} {:state 8, :cost 5} {:state 16, :cost 6}

{:state 32, :cost 7})

Changing the calculation of costs changes the route which the search finds...