📄 exhaustive search.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://nobi.ethz.ch/febi/ex_search_paper/paper.html -->
<HTML><HEAD><TITLE>Exhaustive Search</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type><!--
manually translated from LaTeX to HTML 3.0
fm: 4.8.95
last changed: 8.8.95
-->
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY>
<CENTER>
<H2>All the Needles in a Haystack: Can Exhaustive Search Overcome Combinatorial
Chaos? </H2>Jürg Nievergelt, Ralph Gasser, Fabian Mäser, Christoph Wirth
</CENTER><BR><BR>
<H3>Abstract </H3>For half a century since computers came into existence, the
goal of finding elegant and efficient algorithms to solve ``simple''
(well-defined and well-structured) problems has dominated algorithm design. Over
the same time period, both processing and storage capacity of computers have
increased roughly by a factor of 10^6. The next few decades may well give us a
similar rate of growth in raw computing power, due to various factors such as
continuing miniaturization, parallel and distributed computing. If a
quantitative change of orders of magnitude leads to qualitative changes, where
will the latter take place? Many problems exhibit no detectable regular
structure to be exploited, they appear ``chaotic'', and do not yield to
efficient algorithms. Exhaustive search of large state spaces appears to be the
only viable approach. We survey techniques for exhaustive search, typical
combinatorial problems that have been solved, and present one case study in
detail. <BR><BR><BR>
<H3>Table of Contents </H3>
<UL>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#1">1. The
Scope of Search Techniques</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#2">2.
Emerging Achievements of Exhaustive Search</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#3">3. The
Role of Exhaustive Search: Speculation</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#4">4. State
Spaces, their Size and Structure</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#5">5.
Exhaustive Search Techniques</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#6">6. Case
Study: Merrils and its Verification</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#7">7.
Projects and Outlook</A>
<UL>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#7.1">7.1
Using Heuristics to Trade Accuracy for Space and Time: Pawn endings in
chess</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#7.2">7.2
Enumeration of Maximally Elastic Graphs</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#7.3">7.3
Primes in Intervals of Fixed Length</A>
<LI><A href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#7.4">7.4
Quo Vadis Exhaustive Search?</A> </LI></UL>
<LI><A
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#ref">References</A>
</LI></UL><BR><A name=1></A>
<H3>1. The Scope of Search Techniques</H3>
<P>The concept of search plays an ambivalent role in computer science. On one
hand, it is one of the fundamental concepts on which computer science is built,
perhaps as fundamental as computability or complexity: any problem whatsoever
can be seen as a search for ``the right answer''. On the other hand, despite its
conceptually clear algorithmic nature, the problem domain ``search'' has not
developed as rich a theory as, for example, algorithm complexity. When
discussing search, a dozen unrelated techniques come to mind, ranging from
binary search to fashionable trends such as neural nets or genetic algorithms.
<P>The field of artificial intelligence has, at times, placed search at the
center of its conceptual edifice. For example in the dichotomy of ``search''
versus ``knowledge'' as complementary or competing techniques to achieve
``intelligent'' behavior. Although the distinction between ``search'' and
``knowledge'' has an intuitive appeal (``where is it?'' as opposed to ``there it
is!''), it is difficult to pin down. At the implementation level, it is often
reduced to a distinction between a data structure (the ``knowledge'' of how data
is organized, e.g. a binary search tree) and its access algorithms, e.g. the
operation ``find''. The efficiency trade-off between knowledge and search turns
merely into issues of preprocessing time and query time.
<P>A discussion of search in general, independently of any specific problem,
leads to four main concepts:
<OL>
<LI><STRONG>State space, or search space.</STRONG> The given problem is
formalized by defining an appropriate set of ``states'' that represent
possible configurations we may encounter along our way from the initial
problem statement to a solution. In interesting search problems, this set has
a rich structure, and hence is called a ``space''. The structure typically
includes an adjacency relation to express the constraint that in a single
step, we can only go from the current state to an adjacent state. Thus the
state space is often modeled as a graph with directed or undirected edges.
Various functions may be defined on the state space or on the set of edges,
such as exact or approximate values to be optimized, and exact or estimated
costs of going from one state to another.
<LI><STRONG>Goal, or search criterion.</STRONG> This can vary widely with
respect to both quantity and quality: from a single desired state to an
exhaustive enumeration of all the states in the space; and from accepting only
exact matches, or globally optimum states, to approximate matches, local
optima, or heuristic values with unknown error bounds.
<LI><STRONG>Search algorithm</STRONG>, a framework for specifying a class of
possible traversals of the state space. Examples: greedy, gradient, or
hill-climbing techniques, where each step is taken with the sole criterion of
an immediate gain, regardless of past history or future consequences; or
backtrack, a systematic enumeration of all states that meet given constraints.
The direction of search can vary: from a given initial state to goal states,
or, if the latter are known but paths leading to them are unknown, from the
goal states back towards the initial state. Bidirectional search <A
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Pohl71">[Pohl
71]</A> and other combinations are of interest.
<LI><STRONG>Data structures</STRONG> used to organize the chosen search, such
as: remember what part of the state space has been visited, find one's way to
yet unexplored regions, store the collected information. A stack for
depth-first search (DFS) and a queue for breadth-first search (BFS) are the
most prominent examples, but combinations of these two and other structures,
such as union-find, frequently occur. </LI></OL>
<P>The first two concepts, state space and goal, lend themselves to a rough but
meaningful characterization of most search algorithms into the four categories
described below, depending on whether:
<UL>
<LI>the state space has a regular structure to be exploited, such as a total
order, or not, i.e. its only known structures are irregular, ``random'',
<LI>the search goal is exact or approximate. </LI></UL>
<P><STRONG>Regular structure, exact goal.</STRONG> Typical table-look-up
techniques in a totally ordered space, such as binary search or interpolation
search. Iterative techniques for finding zeros or minima of functions with
special properties, such as Newton iteration or Fibonacci search for the minimum
of a unimodal function. When the state space is a Cartesian product of totally
ordered domains, such as d-dimensional Euclidean space, fast search techniques
still apply in many cases.
<P><STRONG>Regular structure, approximate goal.</STRONG> Includes approximate
pattern-matching algorithms, typically in 1 dimension (strings) or 2 (pictures).
<P><STRONG>Irregular structure, exact goal.</STRONG> The domain of exhaustive
search techniques, such as sieves, backtrack, DFS, BFS, or reverse search for
systematic enumeration of a state space, or retrograde analysis of of
combinatorial puzzles and games.
<P><STRONG>Irregular structure, approximate goal.</STRONG> The domain of
heuristic search. Includes greedy, gradient or hill-climbing techniques to find
a local optimum. Along with enhancements to escape local minima to continue the
search for better ones, without ever knowing whether a global optimum has been
found. Includes simulated annealing, genetic algorithms, neural nets, tabu
search.
<P>This paper is about the class of search problems we call ``state space of
irregular structure, exact goal''. Almost by definition, these problems can only
be approached by techniques called ``exhaustive search''. Exhaustive search
algorithms visit the entire state space in the worst case, and a significant
fraction on the average. For any state not visited (``pruned''), a rigorous
argument guarantees that visiting it would not change the result. This class
includes dynamic programming, branch-and-bound, and alpha-beta evaluation of
game trees - search algorithms that make extensive use of bounds to prune the
search space.
<P>At the risk of oversimplification we venture some comments about the relative
importance of each of the four aspects mentioned above from a programmer's point
of view.
<OL>
<LI>Designing an effective state space is the first and foremost step! The
main point to remember is that, in constructing a state space, the designer
has the greatest opportunity to bring problem-specific knowledge to bear on
the efficiency of the search techniques. This is the domain of conceptual
clarity, common sense, and mathematics. Representations that exploit symmetry
to avoid redundancy; heuristics that detect good candidates early without
wasting time analysing poor candidates; theorems that preclude solutions from
lying in certain subspaces, or assert lower or upper bounds on the value or
cost of solutions, can turn a search problem from infeasible to trivial.
<LI>The goal is rarely under control of the programmer - it is given by the
problem statement. It may be useful, however, to gather experience by first
relaxing the goal, so as to reach a partial objective soon.
<LI>The choice of search algorithm, i.e. the class of traversals of the space
that are considered, is often predetermined by characteristics of the problem.
Available choices have clear consequences. Among forward searches, for
example, DFS requires less temporary storage for its stack than BFS does for
its queue, hence BFS may be impractical for a large problem. As another
example, a backward search such as retrograde analysis is feasible only if all
the goal states can be listed efficiently, i.e., an enumeration problem is
solved first. Thus, it cannot be argued that one exhaustive search technique
dominates others across the board. This situation is in contrast to heuristic
search, where each of several fashionable paradigms (simulated annealing,
neural nets, genetic algorithms, etc.) can often be used interchangeably, and
each has its proponents who proclaim it a superior general-purpose search
technique.
<LI>Data structures are the key to program optimization in the small. A good
implementation often saves a constant factor but is hardly decisive.
</LI></OL><BR><A name=2></A>
<H3>2. Emerging Achievements of Exhaustive Search</H3>
<P>Exhaustive search is truly a creation of the computer era. Although the
history of mathematics records amazing feats of paper-and-pencil computation, as
a human activity, exhaustive search is boring, error-prone, exhausting, and
never gets very far anyway. As a cautionary note, if any is needed, Ludolph van
Ceulen died of exhaustion in 1610 after using regular polygons of 2^62 sides to
obtain 35 decimal digits of Pi - they are engraved on his tombstone.
<P>With the advent of computers, ``experimental mathematics'' became practical:
the systematic search for specific instances of mathematical objects with
desired properties, perhaps to disprove a conjecture or to formulate new
conjectures based on empirical observation. Number theory provides a fertile
ground for the team ``computation + conjecture'', and Derrick Lehmer was a
pioneer in using search algorithms such as sieves or backtrack in pursuit of
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -