OK - Now I will go through a few Informed Search Methods, with a look at Best-First search, Greedy search, and A* search. For this you will need the GeneralSearch algorithm and associated bits and bobs from [State Space Searching in Tcl]. The searches before were fairly primitive, in that they put nodes onto the queue in a set order, without looking to see which might be the ''best'' way. Informed search methods use some sort of function to determine which is the best node to expand next. In this way they hope to reduce the number of nodes expanded to reach the goal. The GeneralSearch then is improved on to become the BestFirstSearch which is the basis for the other searches. GreedySearch uses an idea of the cost from a given state to the goal in order to judge the best route. Heuristic searches are only useful if you can make judgements based on a knowledge of the domain. Here they are: proc BestFirstSearch {p EvalFunc} { # A heuristic search. upvar 1 $p problem proc EnqueueInOrder {newNodes q} [subst -nocommands { upvar 1 \$q queue set queue [$EvalFunc [concat \$newNodes \$queue]] return }] return [GeneralSearch problem EnqueueInOrder] } proc GreedySearch {p} { global pathCosts upvar 1 $p problem proc h {nodes} { global pathCosts # Sort nodes according to the cost to the goal # Just use a simple bubble sort at the moment. proc compare {e1 e2} { global pathCosts set stateA [${e1}::getState] set stateB [${e2}::getState] return [expr {$pathCosts($stateA) - $pathCosts($stateB)}] } set nodes [lsort -command compare $nodes] return $nodes } return [BestFirstSearch problem h] } We can compare GreedySearch to another (non-heuristic) search called UniformCostSearch. UniformCostSearch is a variation on BreadthFirstSearch, which uses the cost so far to determine which node to expand next = g(n). If we combine Greedy and Uniform Cost searches, so that we are taking into account an idea of the cost so far, and an estimated cost to the goal, we get A* search: proc AStarSearch {p} { global pathCosts upvar 1 $p problem proc gplush {nodes} { global pathCosts proc compare {e1 e2} { global pathCosts set stateA [${e1}::getState] set stateB [${e2}::getState] set gstateA [${e1}::getPathCost] set gstateB [${e2}::getPathCost] return [expr {($pathCosts($stateA) + $gstateA) - ($pathCosts($stateB) + $gstateB)}] } set nodes [lsort -command compare $nodes] return $nodes } return [BestFirstSearch problem gplush] } A* works by combining the two functions to determine the best route. It is complete and optimal if h is an '''admissable heuristic''' - i.e. it never ''overestimates the cost to the goal''. An example: find the quickest route from Arad to Bucharest (see [http://www.turism.ro/map.htm]): # Define the state space: # array contains all possible moves and the distance of that move array set cities { Arad {{Zerind 75} {Timisoara 118} {Sibiu 140}} Bucharest {{Pitesti 101} {Fagaras 211} {Urziceni 85} {Giurgiu 90}} Craiova {{Dobreta 120} {RimnicuVilcea 146} {Pitesti 138}} Dobreta {{Mehadia 75} {Craiova 120}} Eforie {Hirsova 86} Fagaras {{Sibiu 99} {Bucharest 211}} Giurgiu {Bucharest 90} Hirsova {{Urziceni 98} {Eforie 86}} Iasi {{Neamt 87} {Vaslui 92}} Lugoj {{Mehadia 70} {Timisoara 111}} Mehadia {{Lugoj 70} {Dobreta 75}} Neamt {Iasi 87} Oradea {{Zerind 71} {Sibiu 151}} Pitesti {{RimnicuVilcea 97} {Craiova 138} {Bucharest 101}} RimnicuVilcea {{Sibiu 80} {Pitesti 97} {Craiova 146}} Sibiu {{Arad 140} {Oradea 151} {Fagaras 99} {RimnicuVilcea 80}} Timisoara {{Arad 118} {Lugoj 111}} Urziceni {{Bucharest 85} {Vaslui 142} {Hirsova 98}} Vaslui {{Urziceni 142} {Iasi 92}} Zerind {{Arad 75} {Oradea 71}} } # This is our estimation of the cost to the goal - the straight line # distance to the goal (SLD). This is admissible, as it can never over- # estimate the distance. SLD is the shortest possible distance. array set pathCosts { Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 98 RimnicuVilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 } set stateSpace(initState) Arad proc goalTest {state} { if {[string equal $state "Bucharest"]} { return 1 } else { return 0 } } set stateSpace(goalTest) goalTest proc Move {node} { global pathCosts cities set currentState [${node}::getState] set possibleStates $cities($currentState) set currentPathCost [${node}::getPathCost] set result "" # Enumerate the possible moves... foreach state $possibleStates { lappend result [list [lindex $state 0] \ [expr ([lindex $state 1] + $currentPathCost)]] # {state-name cost-of-move cost-so-far} } return $result } set stateSpace(operators) Move catch {GreedySearch stateSpace} result set result [split $result "|"] puts "$result" set route [lindex $result 0] puts -nonewline "[${route}::getState] -> " set result [lrange $result 1 end] foreach item $result { append route "|$item" puts -nonewline "[${route}::getState] -> " } puts "End!" puts "Total cost: [${route}::getPathCost]" catch {AStarSearch stateSpace} result set result [split $result "|"] puts "$result" set route [lindex $result 0] puts -nonewline "[${route}::getState] -> " set result [lrange $result 1 end] foreach item $result { append route "|$item" puts -nonewline "[${route}::getState] -> " } puts "End!" puts "Total cost: [${route}::getPathCost]" That lot should do it. Next installment - ''Game Playing in Tcl''. - '''NEM''' oijuo