Friday, April 9, 2010

Improved Canonical Search

Here is an improved search. This the simplest version of the “canonical” graph search given in many A.I. textbooks.

I decided to code it using mostly sequences. There was no overriding technical reason for this, I simply wanted some practice using sequences in F#.

The code is split into three sections: a generic search function, a specific implementation and adapter using a simple node type, and a test.

The test graph is the same as that used in Patrick Henry Winston’s Artificial Intelligence (3rd edition, p.64ff). I added a disconnected node, H, so that I could test search failures. For convenience, here is a copy of it:

This test shows depth- and breadth-first searches. A* will come next, but will require some modification to the canonical search.

The code is below. There may be a bug or two, or a bad practice. I did test it using Winston’s examples, and it passed.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)
open System.Collections.Generic

//// Generic search.

// A path: (cost,head,tail).
type Path<'n> = int*'n*('n list)

// Search for a path.
let rec search<'n>
(paths:seq<Path<'n>>) =
match Seq.isEmpty paths with
| true -> Seq.empty
| false ->
let (c,n,nl) = Seq.head paths
match isGoal n with
| true -> paths
| false ->
(Seq.skip 1 paths)
(fun (n0,c0)->(c+c0,n0,n::nl))
(expand n)))

// Merge functions determine search behavior.
let breadthFirst s0 s1 = Seq.append s0 s1
let depthFirst s0 s1 = Seq.append s1 s0

//// Non-generic parts.

// A simple node.
type Node = {
mutable links:(Node*int) list }

// Base node for initialization.
let node = { id=""; links=[] }

// Search adapter.
let searchNodes =

// Prevents looping.
let hashLoop = new HashSet<string>()

// Goal test.
let testNode (g:Node) (n:Node) =

// Expand a path.
let expandNode (n:Node) =
match hashLoop.Add with
| false -> Seq.empty
| true -> (List.toSeq n.links)

// Search adapter internal function.
let searchAdapter
(goal:Node) =
let sr =
(testNode goal)
(seq { yield (0,start,[]) })
match Seq.isEmpty sr with
| true -> None
| _ -> Some(Seq.head sr)


// Define a graph.

let s = { node with id="s" }
let a = { node with id="a" }
let b = { node with id="b" }
let c = { node with id="c" }
let d = { node with id="d" }
let e = { node with id="e" }
let f = { node with id="f" }
let g = { node with id="g" }
let h = { node with id="h" }

s.links <- [(a,3);(d,4)]
a.links <- [(s,3);(b,4);(d,5)]
b.links <- [(a,4);(c,4);(e,5)]
c.links <- [(b,4)]
d.links <- [(s,4);(a,5);(e,2)]
e.links <- [(b,5);(d,2);(f,4)]
f.links <- [(e,4);(g,3)]
g.links <- [(f,3)]

// Print a path.
let printo (po:Path<Node> option) =
let rec printo0 (l:Node list) =
match l with
| [] -> printfn ""
| h::t ->
printf "%s "
printo0 t
match po with
| None -> printfn "Search Failed"
| Some((c,n,nl)) -> printo0 (n::nl)

// Test some searches.

printo (searchNodes depthFirst s d)
printo (searchNodes depthFirst s g)
printo (searchNodes depthFirst s h)
printo (searchNodes breadthFirst s d)
printo (searchNodes breadthFirst s g)
printo (searchNodes breadthFirst s h)

System.Console.ReadLine() |> ignore

No comments: