Proof Set Search
Proof-set search (PSS) is a best-first
search method for and/or graphs which is closely related
to Allis' proof-number search. PSS addresses a problem
that has plagued search algorithms on and/or graphs for a long time:
overestimating the solution cost of those subgraphs that can be reached through
many different paths.
PSS computes proof and disproof sets
instead of proof numbers, which are upper bounds of the size of such sets.
This method eliminates the problem of counting the same node
more than once.
The sets computed by proof-set search provide a provably better approximation
to the hard-to-compute minimal proof sets than is possible with proof numbers.
Publication
M. Müller.
Proof-set search.
In J. Schaeffer, M. Müller, and Y. Björnsson, editors,
Computers and Games 2002, number 2883 in Lecture Notes in Computer Science,
pages 88-107. Springer Verlag, 2003.
Created: Sep 26, 2000 Last modified: Jun 19, 2009
Martin Müller