At the forefront of Artificial Intelligence

Home » Articles » General » Miscellaneous

Open Node Reduction Through Intermediary States in State-Space Trees

By Forrest Briggs

In the map from object P in state ‘a’ to state ‘c’ (written in this document as ) where f(a,b) is the distance in levels of node expansion from arbitrary object-state O_a to O_b, q is the number of operators that can be applied to P that change its state, and n is the number of nodes that would need to be expanded in a non-heuristic search of all possibilities from P_a to P_b:

A hypothetical node P_b can be conceived such that

. In this case, n is both the number of nodes needing to be opened in

, and

and where:

Then, the total number of nodes needing to be opened in

is r less than in

, where P_b is the node directly in between P_a and P_b:

This figure assumes that the same operator sequences are being found by both an exhaustive search and a search using transversal division, although it is possible that a shorter path could be found by an exhaustive search. Given the above definition for r, it is more efficient to divide a transversal into two separate parts and transverse them separately if r > 1. If 0 < r < 1, then the transversal can be accomplished through the application of a single operator. Please note that where

is the upper bound for sigma, it must be an integer.

A pressing issue then becomes finding a suitable intermediary node. The closer to equidistant a node is from the two nodes from which it is derived, the more efficient bridging the gap between those two nodes will become. Also, it is necessary to ensure that through the use of the given operators, that state can be obtained. For example, in , where the only available operator adds 3 to P, although an optimal P_b = 22.5, such a value is unobtainable through addition of 3 beginning at 0. One way to determine the validity of a state when dealing with only numerical values as states might be to apply prime factorization, but in general, an individual method will be required for each situation. One final point of consideration might be a situation in which it was impossible (or impractical,) to find an intermediary node. Under such a circumstance, or any other where any node that is a part of a transversal being calculated is known and is not directly in between two other nodes, as long as r > 1, it is more efficient to use that node as an intermediate node for the transversal. In such a case, it is necessary to calculate r differently in order to reflect the fact that the transversal is not being directly divided in half, but such a calculation is not substantially more difficult than binary division to warrant any great detail.

Download Word Format (53Kb)

Submitted: 31/05/2000

Article Toolbar

BibTeX entry