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> 
    (isGoal:'n->bool)
    (expand:'n->seq<'n*int>) 
    (merge:seq<Path<'n>>->seq<Path<'n>>->seq<Path<'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 -> 
          search
            isGoal 
            expand
            merge
            (merge 
              (Seq.skip 1 paths) 
              (Seq.map 
                (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 = {
  id:string
  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) = g.id=n.id
  
  // Expand a path.  
  let expandNode (n:Node) = 
    match hashLoop.Add n.id with 
    | false -> Seq.empty
    | true -> (List.toSeq n.links)

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


// 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 " h.id
        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