IAI Chapter 3 Problem Solving as Search
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 3 Problem Solving as Search
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 3 Problem Solving as Search
Kartei Details
| Karten | 59 |
|---|---|
| Sprache | English |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 04.02.2017 / 11.02.2017 |
| Weblink |
https://card2brain.ch/box/20170204_iai_chapter_3_problem_solving_as_search
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170204_iai_chapter_3_problem_solving_as_search/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
What is the definition of search?
Find the action sequence or solution path from a initial to goal states
What are characteristics of search? [3]
1. Completeness and optimality
2. Time-, memory complexity
3. Informed, heuristic or uninformed, blind
What is the definition of completeness?
If a solution exists, is it found?
What is the definition of optimality?
If a solution exists, is the best found?
What is the definition of time and memory complexity?
Time and memory used in a worst case
What is the definition of an informed, heuristic search? [2]
1. Additional information enhances the search
2. Assign nodes with evaluation function f
What are examples for informed, heuristic search strategies? [4]
1. Greedy search
2. A*
3. Hill-climbing
4. Simulated annealing
What is the definition of a uninformed, blind search?
No additional information
What are examples for uninformed, blind search strategies? [6]
1. Breadth-first
2. Uniform cost
3. Depth-first
4. Depth-limited
5. Iterative deepening
6. Bidirectional
What is the definition of a search tree?
The tree induced by expansion with maximal branching factor b and depth of solution d
What represents a node of a search tree?
A state
What represents a edge of a search tree?
An action
What are the characteristics of a node? [5]
1. Parent-node
2. Action
3. Depth
4. Cost
5. State
What is the definition of state space?
Set of possible states or state sets
Which kind of problems have state sets?
Multiple-state problems
What is a problem of state spaces?
Abstraction of details
What is the definition of the initial state?
State which the agent believes to be in initially
What is the definition of Operator(x)?
A state y is reached by action a
What is the definition of States(x)?
All reachable states y
What is the definition of Goal(x)?
Test if x is a goal state
What is the definition of path cost g(P)?
Cost of the path P, usually the sum of costs of actions
What is the definition of search cost?
Time and memory consumption of search
What is the definition of total cost?
Sum of solution and search cost
What is the general function structure of a search?
search(problem, strategy) → solution/failure
What is the function structure of a general search function? [1 + 2]
1. static search tree with initial state of problem
loop
2. If no expansion possible then failure else expand a leaf according to strategy
3. If new node is goal state then solution else add new node to search tree
What is the definition of Breadth-first (BFS)?
Expand nodes in the order they are generated
What are the characteristics of Breadth-first (BFS)? [3+2]
1. Completeness (if b is finite)
2. Optimality (if actions have non-negative identical cost)
3. Memory and time cost in O(b^d+1)
b=10 with d=2 → t=0.11s and m=1MB
b=10 with d=14 → t=3600y and m=1EB
What is the definition of Uniform cost (UCS, modified BFS)?
Expand node with least path cost next
What are the characteristics of Uniform cost (UCS, modified BFS)? [3]
1. Completeness (if b is finite and actions have cost greq eps) with eps cheapest action
2. Optimality
3. Memory and time cost in O(b^(1+round_down[C*/eps])) with C* optimal path cost
What is the definition of Depth-first (DFS)?
Expand nodes at the deepest level m
What are the characteristics of Depth-first (DFS)? [3]
1. No completeness and optimality
2. Memory cost in O(b*m)
3. Time cost in O(b^m)
What is the definition of Depth-limited (DLS, modified DFS)?
Expand nodes at the deepest level till maximal depth l (diameter)
What are the characteristics of Depth-limited (DLS, modified DFS)? [3]
1. No completeness and optimality
2. Memory cost in O(b*l)
3. Time cost in O(b^l)
What is the definition of Iterative deepening (IDS, modified DLS)?
Expand as DLS for current depth 0 to d
What are the characteristics of Iterative deepening (IDS, modified DLS)? [6]
1. Completeness (if b is finite)
2. Optimality (if actions have non-negative identical cost)
3. Memory cost is O(b*d)
4. Time cost is O(b^d)
5. First level has to be expanded d times, second level d-1 times
6. Preferred if d unknown
What is the definition of Bidirectional?
Expand nodes from initial and goal state with a specified strategy
What are the characteristics of Bidirectional? [3+3]
1. Completeness (if b is finite with BFS)
2. Optimality (if actions have non-negative identical cost with BFS)
3. Time cost is O(b^[d/2])
4. Operator has to be reversible
5. Many incomplete described goal states
6. Meeting pattern and strategies for forward and backward search
What is the definition of the single-state problem?
Complete knowledge about world and actions
What is the definition of the multiple-state problem?
1. Incomplete knowledge about world
2. Complete knowledge about actions
What is the definition of the contingency problem?
1. Complete knowledge about world
2. Incomplete knowledge about actions
