Search in Artificial IntelligenceSearch is an important component of problem solving in artificial intelligence (AI) and, more generally, in computer science, engineering and operations research. Combinatorial optimization, decision analysis, game playing, learning, planning, pattern recognition, robotics and theorem proving are some of the areas in which search algbrithms playa key role. Less than a decade ago the conventional wisdom in artificial intelligence was that the best search algorithms had already been invented and the likelihood of finding new results in this area was very small. Since then many new insights and results have been obtained. For example, new algorithms for state space, AND/OR graph, and game tree search were discovered. Articles on new theoretical developments and experimental results on backtracking, heuristic search and constraint propaga tion were published. The relationships among various search and combinatorial algorithms in AI, Operations Research, and other fields were clarified. This volume brings together some of this recent work in a manner designed to be accessible to students and professionals interested in these new insights and developments. |
Contents
Preface | 1 |
An Algebra for Search Problems and Their Solutions | 28 |
A General BranchandBound Formulation | 89 |
Copyright | |
10 other sections not shown
Other editions - View all
Common terms and phrases
a₁ admissible AND/OR graph arc consistency Artificial Intelligence B&B procedure backtrack-free best-first binary branch and bound branching factor breadth-first search CFDR checks complexity components conjuncts constraint satisfaction problems corresponding cost function Dechter defined definition depth-first search domain dynamic programming Eight Puzzle empty_domain evaluation function example expanded exponential Figure formulation Freuder game tree given goal node heuristic estimate heuristic search implicit enumeration algorithms instantiation lateral combination Lemma lookahead lower bound macro network minimax monotone network of constraints node expansions number of nodes optimal solution ordered constraint graph pair parse tree partial tree performance problem instance problem type Proof q-queens represented RFL1 rooted Rubik's Cube search algorithms search problem Section selection sequence serializable solution path solution space solution tree strategy subgoals subgraph subset subtree terminal Theorem tree search vertex vertical combinations vertical search width