||The search algorithm is
implemented by the search() method of the Searcher class.
Initialization: Before starting to search, the
following are done:
|Initialize a collection that can be used to collect
nodes as they are "visited". (Later, when we expand a new
node, we need to go back to this collection to check if we have been
there before; else, we might cycle in an infinite loop.)|
|Set the start node as being the "current
node" and set the Cost of coming to that node as zero.|
Loop: Then, we loop until we find a solution
node. Actually, there is a loop within a loop here:
... select a node from the collection
... expand that node in "next" nodes
Loop 2: For each "next"
... Check if it is in our collection
... if not already visited
then calculate the heuristic
& add it to the collection
otherwise, it is already known
... if a solution node is found
then stop and close up
... Of all the nodes in the collection, select
the one that has seems to lie on the best
solution path (i.e. Cost to get there +
Estimated cost to goal, is the lowest)
This will be the next node to use as
the "current node"
Collection: In the implementation, two
collections are used. One is a collection of SearchNode objects that are
always kept in a "best first" order. When a new node is added,
it is done in the correct position. So, getting the next "best node
to explore" simply means taking the first item from the collection.
A second collection is used to make it fast to check is a node has been
visited below. This collection is a Hashtable that is keyed on the
NodeState. The lookup value of the Hashtable is the SearchNode.