|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Nilsson N.J. — Problem-Solving Methods in Artificial Intelligence |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
 refutations 227 229
15-puzzle 3
15-puzzle, graph of 4 5
15-puzzle, history of 12
15-puzzle, nondeterministic program for 20—27
15-puzzle, operators 4
15-puzzle, states 4
8-puzzle, evaluation functions for 56 66
8-puzzle, examples of solution, breadth-first search of 45—17
8-puzzle, examples of solution, depth-first search of 50 52
8-puzzle, examples of solution, ordered search of 55—57 66—68
8-puzzle, operators for 20—21
8-puzzle, rewriting rules for 20—21
8-queens problem 41(2—5) 92
Action schedules 112
Admissibility of A* 59—61
Admissibility of ordered—search algorithm for AND/OR trees 131—130
Admissibility of search algorithms 59
Advice taker 11 213—214
Algebra, solving word problems in 212
Algorithm A* 59
Algorithm A* (cont’d), admissibility of 59—61
Algorithm A* (cont’d), efficiency of 62
Algorithm A* (cont’d), optimality of 61—65
Alpha-beta procedure, alpha cutoffs in 145
Alpha-beta procedure, alpha values in 145
Alpha-beta procedure, beta cutoffs in 145 147
Alpha-beta procedure, beta values in 145
Alpha-beta procedure, combined with ordering procedure 148—149
Alpha-beta procedure, efficiency of 147—148
Alpha-beta procedure, example of 146
Alpha-beta procedure, for searching game trees 140—149
Alpha-beta procedure, history of 152
Alphabetic variants 174
Ancestor, in graphs 22—23
Ancestry filter criterion 221—222 229
Ancestry filter criterion, completeness of 220—223
Ancestry-filtered form (AFF) 219—223 229
Ancestry-filtered form (AFF), interpretation as a state-space search problem 231(8—5)
AND nodes in AXD/OR graphs 87
AND/OR graphs, AND nodes in 87
AND/OR graphs, cycles in 123—124
AND/OR graphs, definition of 83 87—88
AND/OR graphs, depth of a node in 124
AND/OR graphs, examples of 88 89
AND/OR graphs, for geometry problem 100
AND/OR graphs, for Grundy’s game 111
AND/OR graphs, for monkey-and-bananas problem 108
AND/OR graphs, for symbolic integration problem 96
AND/OR graphs, OR nodes in 87
AND/OR graphs, representation by nondeterministic programs 90—93
AND/OR graphs, search graph of 118
AND/OR graphs, search methods for 123—120
AND/OR graphs, solved nodes in 88—89
AND/OR graphs, to represent games 110 113
AND/OR graphs, unsolvable nodes in 90 117
AND/OR trees, as game trees 110 113 137
AND/OR trees, breadth-first search of 119—121
AND/OR trees, costs of solutions 120—128
AND/OR trees, definition of 119
AND/OR trees, depth-first search of 121—123 124
AND/OR trees, evaluation functions for searching 128—133
AND/OR trees, generalizing search methods so they apply to AND/OR graphs 123—126
AND/OR trees, merit functions for searching 151
AND/OR trees, node selection in 136
AND/OR trees, optimality of search methods for 136
AND/OR trees, ordered-search algorithm for 130—131 132 133
AND/OR trees, search methods for 119—155
AND/OR trees, tip nodes of 128
Answer extraction in program writing 201—205
Answer extraction, example 189—191
Answer extraction, literature on 213
Answer extraction, process of complete description of 191—201
Answer extraction, process of summary of 199—200
Answer extraction, unification set in 192
Answer statements 190—191
Answer statements containing Skolem functions 197—198
Answer statements derived from wffs containing universally quantified variables 196—198
Answer statements, general form of 195—196
Answer statements, nonuniqueness of 201
Applicability wffs in applications of predicate calculus to state-space problem solving 206—209
Arcs, cost of 46 48 126
Arcs, definition in graphs 22—23
Arcs, irrevocable 40(2—2)
Arrays, rewriting rules for 20—21
Artificial evolution 9
Artificial intelligence, approaches to 9—10
Artificial intelligence, definition of vii—viii 1 114(4—5)
Artificial intelligence, overviews of 9
Artificial intelligence, surveys of 12
Artificial neurons 9
Assignment statement in nondeterministic programs 25
atom 174
Atomic formulas 15S
Attention control in searching AND/OR trees 151
Backtrack programming 75
Backtracking in depth-first search 49 76
Base clause 219
Bidirectional search 76
Blind search 44
Branch and bound methods 11 76
Branch and bound methods, example of 77(3-3)
Branches in nondeterministic programs 25 91—93
Branching factor, effective 73 74
Breadth-first search applied to S-puzzle 45—47
Breadth-first search in resolution theorem proving 217
Breadth-first search of AND/OR trees, algorithm for 119—121
Breadth-first search of AND/OR trees, flow chart for 120
Breadth-first search of state-space graphs 45—47
Breadth-first search of state-space graphs, algorithm for 45
Breadth-first search of state-space graphs, flow chart for 46
Checkers program 151 153
Chess programs 152—153
Choice functions in nondeterministic programs 38
Chromosome matching problems 11
Clause form 165—168
clauses 165—168
Clauses, factors of 178
Clauses, negative 227
Clauses, positive 227
Combined strategies in resolution theorem proving 227
Completeness of resolution 181—183
Completeness of resolution, relative to a model 225—226
Completeness of resolution, relative to ancestry filter 220—223
Completeness of set-of-support 223—224 226—227
Conjunction of wffs 161 162
Conjunctive normal form 167 see
Consistency assumption 63
Construction lines in geometry theorem proving 102—103
Constructive proofs 188
Control problems as examples of state-space problem solving 33—34
Control theory, state spaces in 10 33—34
Correctness of nondeterministic programs 38
Correctness of programs 39 213
Costs of arcs 46 48 126
Costs of solutions in AND/OR trees 126—128
Cycles in searching AND/OR graphs 123—124
Davis — Putnam procedure 1S4
DEDUCOM 212
Delete and add rules 207
Depth of a node 48—49 53 124
Depth of a refutation 180
Depth ratio 77
Depth-first search applied to S-puzzle 50 52
Depth-first search heuristics for 53—54
Depth-first search of AND/OR trees 121—124
Depth-first search of AND/OR trees, algorithm for 123
Depth-first search of AND/OR trees, flow chart for 122
Depth-first search of state-space graphs 4S—50
Depth-first search of state-space graphs, algorithm for 50
| Depth-first search of state-space graphs, flow chart for 51
Descendant in graphs 22—23
Diagram, use in geometry theorem proving 100—102
Differences, history of use 112—113
Differences, in monkey-and-bananas problem 105—109
Differences, in problem reduction 105—109
Disagreement set in unification algorithm 177
Disjunctions of wffs 162
Distribution problems as example of state-space problem solving 30—32
Distribution problems, literature on 39
Domains in predicate calculus 159
Dynamic ordering, use in searching game trees 149
Dynamic programming 75
Effective branching factor 73 74
Efficiency of search algorithms 62 72—75 147—148
Empty clause 175
Equality in predicate calculus 183—184
Evaluation functions as used in game trees 138
Evaluation functions as used in heuristic search 54—55
Evaluation functions as used in searching AND/OR trees 128—133
Evaluation functions in resolution theorem proving 229—230
Evolution, artificial 9
Existential quantifiers 163
Existential quantifiers, elimination of 166—167
Existential quantifiers, realization of, in answer extraction 189—201
Expansion of nodes in graphs 44 117
Explicit graphs 23
Factor of a clause 174
Failure nodes 172
Fewest-components strategy in resolution theorem proving 228
Fixed-ordering search procedure 148—149
Flow charts for breadth-first search 46 120
Flow charts for depth-first search 51 122
Flow charts for nondeterministic programs 24 91
Flow charts for ordered search 132
Flow charts for uniform cost search 49
Flow problems see Distribution problems
Formalization for state-space problem solving 209—212
Frame problem 212
Function letters 158
Functional composition in program writing 201—205
Game trees as AND/OR trees 110 113 137
Game trees, alpha-beta search of 140—149
Game trees, definition of 110
Game trees, minimax search of 137—140
Game trees, search of 137—150
Game trees, search of using dynamic ordering 149
Game trees, search of using fixed ordering 148—149
Game trees, static evaluation functions for 138
Games as example problems 3
Games, books about 12
Games, Grundy’s 110—112 113
Games, Last One Loses 114(4—6)
Games, legal moves in 110
Games, solution by problem-reduction approach 109—112
Games, solution of 137—150
Games, tic—tac—toe 139—143 154(5—6)
General Problem Solver (GPS) 10 113
General problem solver (GPS), method of operation 103—109
Geometry theorem proving 97—103
Geometry theorem proving, adding construction lines in 102—103
Geometry theorem proving, literature on 112
Geometry theorem proving, use of diagram in 100—102
Geometry theorem proving, use of models in 100—102
GO, program for 153
Goal nodes 23
Goal states 22
Goal wff 206
Grammar in syntax analysis 28—30
Graphs, refutation or proof 180—182
Ground instance 168 176
Grundy’s Game 110—112 113
Herbrand base 169—170
Herbrand procedures 184
Herbrand universe 168—169
Herbrand’s theorem 172n
Heuristic function in AND/OR tree-search algorithms 128—131
Heuristic function in state-space search algorithms 58—59
Heuristic function, role in determining heuristic power 65—68
Heuristic information possessed by a search algorithm 62
Heuristic information to focus or reduce search 44 53—54
Heuristic information, uses of 53—54
Heuristic power 54
Heuristic power, role of heuristic functions in determining 65—68
Heuristic search 44 53—54
Heuristics, miscellaneous 71—72 136—137
Implementations of theorem-proving programs 230
Implication signs, elimination of 165
Implicit graphs 23
Inference nodes 174—175
Information retrieval 2 see
Integration, symbolic 11 93—97 112 114(4—5)
Intelligence of computers 8
Intelligence, definition of 2
Intelligence, theory of 2
Interpretations see Models in predicate calculus
Introspection in design of problem solvers 9—10
Irrevocable arcs 40(2—2)
Kalah, programs for 153
Kalah, use for comparing strategies 152
Kalah, use of dynamic ordering in 149
Key operators 104—105
Last One Loses (game) 114(4—6)
Learning by machine viii
Learning strategies 151
Legal moves in games 110
Level bound in unit-preference strategy 228
Level of a refutation 180
Literal 168
Logic in problem solving 6—7 156—157 187—216
Logic, higher-order 154
Logic, second-order 184 see
Logic-theory (LT) machine 13(1—4) 112
Logical connectives in predicate calculus 158
M & N procedure, literature on 152
Mac Hac, chess program 152—153
Mass spectrograph analysis problems 11
Matrix of a wff 167
Max prist of AND/ON solution trees 126—127
Meaning (semantics) of predicate calculus 157 159—161
Means-ends analysis 113
Merges in resolution theorem proving 224 229
Merit functions 151 see
Minimax procedure for searching game trees 137—140
Minimax procedure, example using tic—tac—toe 139—140 141—143
Minimax procedure, improvements on 150 152
Missionanes-and-cannibals problem 39
Model strategies in resolution theorem proving 224—227 229
Model strategies, completeness of 225—226
Models in predicate calculus 159 171—172 224—225
Modus ponens as an instance of resolution 179
Monkey-and-bananas problem, AND/OR graph for 108
Monkey-and-bananas problem, as illustration of applications of predicate calculus 206—212
Monkey-and-bananas problem, as illustration of problem-reduction approach 105—109
Monkey-and-bananas problem, as illustration of state-description schemas 35—37
Monkey-and-bananas problem, as illustration of use of differences 105—109
Monkey-and-bananas problem, graph for 37
Multilated checkerboard problem 41(2—7)
Multiple 150
Narrows in a search space 85 103—109
Natural language, processing of 2 12
Natural language, translation of 188—189 212
Negative clauses 227
Neurons, artificial 9
Nodes, AND 87
Nodes, definition in graphs 22—23
Nodes, depth of 48—40 53 124
Nodes, expansion of 44 117
Nodes, failure 172
Nodes, goal 23
|
|
|
| Ðåêëàìà |
|
|
|
|
|
|
|
|
Î ïðîåêòå