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
Set of flashcards Details
| Flashcards | 59 |
|---|---|
| Language | English |
| Category | Computer Science |
| Level | University |
| Created / Updated | 04.02.2017 / 11.02.2017 |
| Weblink |
https://card2brain.ch/box/20170204_iai_chapter_3_problem_solving_as_search
|
| Embed |
<iframe src="https://card2brain.ch/box/20170204_iai_chapter_3_problem_solving_as_search/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Create or copy sets of flashcards
With an upgrade you can create or copy an unlimited number of sets and use many more additional features.
Log in to see all the cards.
What are the characteristics of the missionaries and cannibals? [4+3]
1. States are the triple x the number of cannibals, y the number of missionaries and z the boat on the left side of the river // Initial state (3,3,1) and not all states are reachable
2. Operators are two humans change river sides with the boat
3. Goal is reaching state (0,0,0)
4. Path cost is 1 unit per river crossing
Are all relevant information available? // Non-intended solutions
What can happen normally? // Sabotaging the correct solution
Solved by Saul Amarel (1968)
What is the definition of best-first (BeFS)?
Expand node with best node value
What is the definition of greedy (GS)? [4]
1. Estimate cost h(n) from current node n to goal state
2. Expand cost minimizing node
3. Completeness (if h unequal 0)
4. Memory and time cost in O(b^h)
What is the definition of A*? [2]
1. Combine UCS and GS
2. Estimate cost f(n) the sum from initial node to current node g(n) and from current node n to goal state h(n)
What is the definition of admissible?
h is called admissible if h(n) \leq h*(n) with h* the cost of the optimal path from current node to goal state
What holds for monotone and nondecreasing functions? [2]
1. Path-max equation can be guaranteed
2. f(n’) = max(f(n) or g(n’)+h(n’)) with n parent of n’
What are the characteristics of the effective branching factor b*? [3]
1. Number of successors generated by a "typical" node
2. N+1 = 1+b*+b*²+...+b*^d // No closed form solution for b*
3. Smaller b* is better for h
What is the definition of IDA*? (2)
1. Perform IDS with respect to the heuristic of A*
2. Do not consider an increasing depth (1...d) but the increasing value to the goal node (f(root),...,f(goal))
What is the definition of simplified memory-bounded A* (SMA*)? [3]
1. Apply A* on deepest node in Queue with smallest f
2. Assign max(f(parent), g(node)+h(node)) to node or inf if at max depth
3. Update ancestors of node if necessary and add/remove nodes from Queue
What is the definition of hill-climbing? [2]
1. Find successor node with higher value as current node
2. Current node is solution if no successor has a higher value
What is the definition of simulated annealing (SAS)? [4]
1. Choose successor randomly after scheduling index to T
2. If T!=0 AND successor value is greater than current value update current node // Difference deltaE
3. Else update current node only with probability e^(deltaE/T)
4. Theorem “For every search space a schedule exists such that SAS converges to global maximum.”
What are examples of heuristics for the 8-Puzzle? [2]
1. Number of tiles in wrong position // Simplified to placing tiles arbitrary
2. Sum of (Manhattan) distance of tiles to goal location
What are examples of heuristics for chess? [2]
1. Material value
2. Safety of king, pawn structure
What are the characteristics of heuristics? [2]
1. Easy to compute
2. Weighted linear functions // Criteria independent from each other
How can a heuristic be found? [2]
1. Cost of exact solution for simplified problem
2. Pattern databases with maximizing pattern // Sum of pattern is not admissible due to shared moves
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
-
- 1 / 59
-
