Problem Solving Methods in Artificial Intelligence

Cover......Page __sk_0000.djvu Copyright......Page __sk_0002.djvu Contents......Page __sk_0009.djvu Preface......Page __sk_0005.djvu 1-1 Bibliographical and historical remarks......Page __sk_0015.djvu 1-2 Problem-solving and artificial intelligence......Page __sk_0016.djvu 1-3 Puzzles and games as example problems......Page __sk_0018.djvu 1-4 Problem states and operators......Page __sk_0019.djvu 1-5 Reducing problems to subproblems......Page __sk_0020.djvu 1-7 Two elements of problem solving: representation and search......Page __sk_0022.djvu Problems......Page __sk_0026.djvu References......Page __sk_0027.djvu 2-1 State descriptions......Page __sk_0031.djvu 2-2 Operators......Page __sk_0033.djvu 2-4 Graph notation......Page __sk_0036.djvu 2-5 Representation of state spaces by nondeterministic programs......Page __sk_0038.djvu 2-6 Some example problem representations......Page __sk_0041.djvu 2-7 Selecting "good" representations......Page __sk_0049.djvu 2-8 Bibliographical and historical remarks......Page __sk_0052.djvu Problems......Page __sk_0053.djvu References......Page __sk_0055.djvu 3-1 Graph-searching processes......Page __sk_0057.djvu 3-2 Breadth-first methods......Page __sk_0059.djvu 3-3 A depth-first method......Page __sk_0062.djvu 3-4 Modifications needed when searching graphs......Page __sk_0064.djvu 3-5 Discussion of heuristic information......Page __sk_0067.djvu 3-6 Use of evaluation functions......Page __sk_0068.djvu 3-7 An optimal search algorithm......Page __sk_0071.djvu 3-8 The admissibility of A*......Page __sk_0073.djvu 3-9 The optimality of A*......Page __sk_0075.djvu 3-10 The heuristic power of h-hat......Page __sk_0079.djvu 3-11 The importance of g-hat......Page __sk_0082.djvu 3-12 Use of other heuristics......Page __sk_0085.djvu 3-13 Measures of performance......Page __sk_0086.djvu 3-14 Bibliographical and historical remarks......Page __sk_0089.djvu Problems......Page __sk_0091.djvu References......Page __sk_0092.djvu 4-1 An example of a problem-reduction representation......Page __sk_0094.djvu 4-2 Problem descriptions......Page __sk_0097.djvu 4-3 Problem-reduction operators......Page __sk_0099.djvu 4-4 Primitive problem descriptions......Page __sk_0100.djvu 4-5 AND/OR graphs......Page __sk_0101.djvu 4-6 Representation of AND/OR graphs by nondeterministic programs......Page __sk_0104.djvu 4-7 Examples of problem-reduction representations......Page __sk_0107.djvu 4-8 Planning mechanisms in problem reduction......Page __sk_0117.djvu 4-9 Key operators......Page __sk_0118.djvu 4-10 Differences......Page __sk_0119.djvu 4-12 Games......Page __sk_0123.djvu 4-13 Bibliographical and historical remarks......Page __sk_0126.djvu Problems......Page __sk_0127.djvu References......Page __sk_0128.djvu 5-1 AND/OR graph-searching processes......Page __sk_0130.djvu 5-2 Breadth-first search......Page __sk_0133.djvu 5-3 Depth-first search......Page __sk_0135.djvu 5-4 Searching AND/OR graphs......Page __sk_0137.djvu 5-5 Costs of solution trees......Page __sk_0140.djvu 5-6 Using cost estimates to direct search......Page __sk_0142.djvu 5-7 An ordered search algorithm for AND/OR trees......Page __sk_0144.djvu 5-8 Admissibility of the ordered-search algorithm......Page __sk_0145.djvu 5-10 Modifications......Page __sk_0150.djvu 5-11 The minimax procedure for searching game trees......Page __sk_0151.djvu 5-12 The alpha-beta procedure......Page __sk_0154.djvu 5-13 The search efficiency of the alpha-beta procedure......Page __sk_0161.djvu 5-14 Combined alpha-beta and ordering procedures......Page __sk_0162.djvu 5-16 Bibliographical and historical remarks......Page __sk_0164.djvu Problems......Page __sk_0167.djvu References......Page __sk_0168.djvu 6-1 Predicate calculus as a language for problem solving......Page __sk_0170.djvu 6-2 Syntax......Page __sk_0171.djvu 6-3 Semantics......Page __sk_0173.djvu 6-4 Variables and quantifiers......Page __sk_0175.djvu 6-5 Validity and satisfiability......Page __sk_0177.djvu 6-6 Clause form......Page __sk_0179.djvu 6-7 The Herbrand universe......Page __sk_0182.djvu 6-8 The Herbrand base......Page __sk_0183.djvu 6-9 Constructing a semantic tree......Page __sk_0184.djvu 6-10 Failure nodes......Page __sk_0186.djvu 6-11 Inference nodes......Page __sk_0188.djvu 6-12 Unification......Page __sk_0189.djvu 6-13 Resolvents......Page __sk_0192.djvu 6-14 The resolution principle......Page __sk_0194.djvu 6-15 Soundness and completeness of resolution......Page __sk_0195.djvu 6-16 Bibliographical and historical remarks......Page __sk_0197.djvu Problems......Page __sk_0198.djvu References......Page __sk_0200.djvu 7-1 The predicate calculus in problem solving......Page __sk_0201.djvu 7-2 An example......Page __sk_0203.djvu 7-3 The answer-extraction process......Page __sk_0205.djvu 7-4 Conjectures containing universally quantified variables......Page __sk_0210.djvu 7-5 An automatic program-writing example......Page __sk_0215.djvu 7-6 The use of the predicate calculus in state-space problem solving......Page __sk_0220.djvu 7-7 A formalization for state-space problem solving......Page __sk_0223.djvu 7-8 Bibliographical and historical remarks......Page __sk_0226.djvu Problems......Page __sk_0228.djvu References......Page __sk_0229.djvu 8-1 Search Strategies......Page __sk_0231.djvu 8-2 Simplification strategies......Page __sk_0232.djvu 8-4 Ancestry-filtered form proofs......Page __sk_0233.djvu 8-5 Set-of-support strategy......Page __sk_0237.djvu 8-7 Model strategies......Page __sk_0238.djvu 8-10 Ordering strategies......Page __sk_0241.djvu 8-11 Bibliographical and historical remarks......Page __sk_0242.djvu Problems......Page __sk_0244.djvu References......Page __sk_0246.djvu Combined References and Author Index......Page __sk_0248.djvu Subject Index......Page __sk_0259.djvu Solving problems by heuristically guide, trial-and-error search in a space of possible solutions is a dominant theme in artificial-intelligence research, yet there is no single textbook devoted to explaining the underlying theoretical ideas of these search processes. This book has been written in an attempt to fill that need. It covers throughly the major heuristic search methods used to automatic problem solving, theorem proving, and game playing