<<Previous

Searcher.search()  

Next>>
Introduction

The puzzle
Overview
The Goal
Playing

The algorithm
Simple
Best solution
Search
Heuristic

Program Design
Search Classes
Extensions
Display

Download

Run

Comments


 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:

Loop 1:
... select a node from the collection
... expand that node in "next" nodes

Loop 2: For each "next" node
... 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
End-Loop-2

... 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"
End-Loop-2

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.