Version 4 of Heuristic Searches

Updated 2005-12-20 03:19:00

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 [L1 ]):

 # 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'''

Category Concept