Thursday, April 8, 2010

Search Routines, Continued

Yay! I finished my taxes. I hope to post some more F# stuff over the coming weekend.

In the meantime, here is a first try at general purpose depth/breadth-first search routine. It's not really generic yet, being based on a specific data structure. However, my goal is, over the next few days, to turn it into a nice generic search routine that I can use in a number of applications. The final version will implement the A* search rather than depth/breadth-first search. THAT is what I will finally marry with the semantic network.

Also, the code below is very, very rough; rather grim and awfull, actually. I wrote it quickly last night in between various chores and while worrying about a half-dozen other things. I mainly post it as a way of forcing myself to stay active on the blog here.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)
// Rough-draft code, hammered-in between eating dinner, 
// playing with my pet rabbit to keep him from becoming feral,
// worrying about taxes, etc.
// Take it with a grain of salt
// and an eye towards what it may become.

open System.Collections.Generic

type Node = {
mutable links:(Node*int) list }

let defaultNode = { id=""; links=[] }

type Path = int*Node*(Node list)

let search =

let hashLoop = new HashSet<string>()

let rec search0 (g:string)
(pl:Path list) =

let rec expand (c:int)
(l:(Node*int) list)
(nl:Node list)
(pl:Path list) =
match l with
| [] -> pl
| (ln,lc)::t ->
match hashLoop.Add with
// Breadth-first.
//| true -> expand c t nl (List.append pl [(c+lc,ln,nl)])
// Depth-first.
| true -> expand c t nl ((c+lc,ln,nl)::pl)
| false -> expand c t nl pl

match pl with
| [] -> None
| (c,n,nl)::pt ->
match with
| true -> Some(c,n::nl)
| false ->
search0 g (expand c n.links nl pt)

let search1 (s:Node) gid =
search0 gid [(0,s,[])]


// This is the same network used for
// search examples in Patrick Henry Winston's
// Artificial Intelligence, 3rd Edition, p.64ff

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

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)]

let x0 = search s "c"

System.Console.ReadLine() |> ignore

No comments: