THOMASON@C.CS.CMU.EDU (Rich Thomason) (03/12/87)
COMPUTER SCIENCE COLLOQUIUM PITT/CMU
SPEAKER: David Mutchler (Naval Research Laboratory)
TITLE: What Search Algorithm Gives Optimal Average-Case Performance
When Search Resources Are Highly Limited?
DATE: March 13, 1987
TIME: 1:00 - 2:00 P.M.
PLACE: 228 Alumni Hall, University of Pittsburgh
Searching the state-space for an acceptable solution is a
fundamental activity for many AI programs. Complete search of the
state-space is typically infeasible. Instead, one relies on whatever
heuristic information is available. Here is one interesting question
that then arises: Given n search resources, how can one dynamically
utilize those resources to achieve (on average) as good a solution as
possible?
In this talk, I will:
(1) present a probabilistic model in which to study this
question;
(2) state two theorems that together answer the above
question in the context of that model;
(3) explain how branching processes and branching random
walks are used to prove the theorems.
Here is a brief description of the model I will be using. A
least-cost root-to-leaf path is sought in a random tree. The tree is
known to be binary and complete to depth N. Arc costs are
independently set either to 1 (with probability p) or to 0 (with
probability 1-p). The cost of a leaf is the sum of the arc costs on
the path from the root to that leaf. The searcher (scout) can learn
n arc values; after having done so, a leaf must be selected. It is
easy to see how the leaf should be chosen. The interesting question
is that: how should the scout dynamically allocated the n search
resources to minimize the average cost of the leaf selected?