Browse Prior Art Database

Space-Optimizing Best-First Search

IP.com Disclosure Number: IPCOM000101153D
Original Publication Date: 1990-Jul-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 3 page(s) / 150K

Publishing Venue

IBM

Related People

De Gennaro, S: AUTHOR [+2]

Abstract

Disclosed is an algorithm for implementing a best-first search (1) that uses a fraction of the storage used by the standard priority-queue implementation (2). Upon applying the move generator to get a list of successor nodes, only the most promising ones are stored in the priority-queue, yielding a space savings in one use of this algorithm of over 95%. The algorithm maintains the number of unexpanded children for a node in the priority-queue, and when this reaches 0, backtracks to regenerate more successors.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Space-Optimizing Best-First Search

       Disclosed is an algorithm for implementing a best-first
search (1) that uses a fraction of the storage used by the standard
priority-queue implementation (2).  Upon applying the move generator
to get a list of successor nodes, only the most promising ones are
stored in the priority-queue, yielding a space savings in one use of
this algorithm of over 95%.  The algorithm maintains the number of
unexpanded children for a node in the priority-queue, and when this
reaches 0, backtracks to regenerate more successors.

      A best-first search is a search strategy that captures the
advantages of depth and breadth first search, by using a heuristics
and priority-queue.  At each iteration, the most promising node from
the priority-queue is removed, its successors generated, the
heuristic applied, and the new nodes inserted back into the
priority-queue.  If the number of successor states is high, then
memory space could easily become exhausted before a solution is
found.

      This algorithm works by only placing "promising" successors for
a node in the priority queue.  When all these successors have been
expanded, the next most promising successors are generated and placed
in the priority queue. This reduces the memory needed to search, but
at the expense of backtracking.  Only one value is needed for each
node in the search tree beyond that required for a standard
best-first search, the number of unexplored children.  In the
implementation described below, the heuristic is a probability that
decreases monotonically as one descends in the search tree, the
search tree is stored using parent pointers, and all solution nodes
within delta of the optimal are required:
1.   Initialize the search tree and priority queue as a root with
probability 1.
2.   Examine the best node in the priority queue.  If empty, or the
best node is delta less than the best solution, then exit.
3.   Remove the best node, and all nodes within delta of both the
best solution and best node from the priority-queue and place in a
list.
4.   Expand each node on the list (see below), and decrement the
number value of the node's parent.
5.   If the number value becomes 0 for the parent, then re-expand the
parent (see below).
6.   Go to step 2.

      The expansion (and re-expansion) algorithm is:
1.   Apply the move generator to get the successors, and apply the
heuristic to each node.
2.   If this is an expansion, find the best child.  If a
re-expansion, find the best child less than the last expanded child
of this node.
3.   If no best child, or if the best child is delta less than the
best solution, then return from the expansion algorithm.
4.   Add the best child to the tree and priority-queue, using the
probability to determine its location. Initialize the parent pointer
to the node being expanded, and the number to 0.
5.   Increment the number of the node being expanded, since a child
was...