breadth-search provides a simple, partially optimised implementation of a breadth-first search mechanism.
breadth-search takes 3 arguments...
· start state
· goal state/fn
· legal move generator
(breadth-search start goal legal-move-generator)
The legal move generator is a function which takes a state representation as its only argument and returns a collection of successor states – see example 1. Note that breadth-search also allows maps to be used as legal move generators – see example 2. The use of maps works because of Clojure's partial abstraction of maps as functional forms – it is not directly a feature of breadth-search.
Goal states are (by default) detected using the "=" function. This is sometimes 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 – see example 3.
Similarly, by default, states are compared using the "=" function. It is often necessary to use more complex (faceted) state descriptions which require less trivial approaches to comparison – see example 4.
This example considers finding a route between numbers using a simple transformation function where a number can be...
· multiplied by 3
· have 7 subtracted from it
· have 2 added to it
The transformation function (a legal move generator) can be written as follows...
(defn lmg [n]
(list (* n 3) (- n 7) (+ n 2)))
To find a path between (for example) 5 and 1357 using this legal move generator we would call bread-search like this...
user=>
(breadth-search 5 1357 lmg)
(5 15 17 51 153 459 452 454 1362 1355 1357)
NB: legal move generators should return something seq-able: a list, vector or set.
Since Clojure can treat maps as functions, maps can be used as legal move generators as long as they are structured correctly, ie: any key lookup should return a list, vector or set. This example shows a map used for a simple word transformation puzzle. In this case words can be transformed to other words where only one letter has changed. All possible transformations are held in the map.
The example shown is a little trivial but the technique can be used in other cases where the problem space is finite (and small-ish) and all transformations can be specified in advance.
(def words
'{ coat #{boat moat cost}
cost #{most lost coat cast}
boat #{moat coat boot}
moat #{moot most boat}
moot #{soot boot loot}
})
user=> (breadth-search 'coat 'loot words)
(coat moat moot loot)
If a simple equality comparison is too limited for determining goal states, predicates maybe used. In which case any state satisfying the predicate will be considered a valid goal.
(defn is-goal? [n]
; n is greater than 0 and divisible by 35
(and (> n 0) (zero? (mod n 35))))
user=>
(breadth-search 1 is-goal? lmg)
; see example-1 for defn of lmg
(1 3 9 11 33 35)
Inline function definitions (long and short forms) are also permitted...
user=> (breadth-search 1 #(> % 20) lmg)
(1 3 9 27)
In some cases it is convenient to combine additional information with state data. There are many different ways to do this, the following example presents a simple case for the sake of example.
States in the following example are 2 element vectors where the first element is a state and the second is some randomly generated (and accumulated) number.
(defn facet-lmg [[state other]]
(map (fn[x] [x (+ other (rand-int 100))]) (lmg state)))
user=> (breadth-search [5 0] (fn [[x _]] (= x 237)) facet-lmg) ; see example-1 for defn of lmg
([5 0] [15 63] [45 160] [38 214] [31 257] [93 312] [86 359] [79 442] [237 522])
; note that using random numbers means that different calls to facet-lmg
; generate some different additional data
user=> (breadth-search [5 0] (fn [[x _]] (= x 237)) facet-lmg)
([5 0] [15 37] [45 124] [38 220] [31 269] [93 279] [86 325] [79 333] [237 383])