Problem Solving by Search Flashcards
What does an agent need to search for a solution?
A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of those actions, a set of goal states, and an action cost function. The environment of the problem is represented by a state space graph.
What are the 5 parts of a search problem?
A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of those actions, a goal test function, and a path cost function. The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution.
How do search algorithms treat states and actions?
Search algorithms treat states and actions as atomic: they do not consider any internal structure they might possess.
How does a tree search work? How does a graph search work?
A general TREE-SEARCH algorithm considers all possible paths to find a solution, whereas a GRAPH-SEARCH algorithm avoids consideration of redundant paths.
How ares each algorithms judged?
Search algorithms are judged on the basis of completeness, optimality, time complex- ity, and space complexity. Complexity depends on b, the branching factor in the state space, and d, the depth of the shallowest solution.
Name 5 uninformed search methods
Breadth first
Uniform cost (Dijkstra’s)
Depth first
Iterative deepending
Bidirectional
Describe breadth first and depth first searches
Breadth-first search expands the shallowest nodes first; it is complete, optimal for unit step costs, but has exponential space complexity.
Depth-first search expands the deepest unexpanded node first. It is neither com- plete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound.
Describe Uniform cost search
Uniform-cost search expands the node with lowest path cost, g(n), and is optimal for general step costs.
Describe iterative deepening search
Iterative deepening search calls depth-first search with increasing depth limits until a goal is found. It is complete, optimal for unit step costs, has time complexity comparable to breadth-first search, and has linear space complexity.
Describe bidirectional search
Bidirectional search can enormously reduce time complexity, but it is not always applicable and may require too much space.
Name the different informed search methods
Best first
Greedy best first
A star
Recursive best first
Describe the best first search, and the greedy best first. How do they differ?
The generic best-first search algorithm selects a node for expansion according to an evaluation function.
Greedy best-first search expands nodes with minimal h(n). It is not optimal but is often efficient.
Describe the A * search algorithm
A∗ search expands nodes with minimal f (n) = g(n) + h(n). A∗ is complete and optimal, provided that h(n) is admissible (for TREE-SEARCH) or consistent (for GRAPH-SEARCH). The space complexity of A∗ is still prohibitive.
Describe the RBFS search algorithm
RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems that A∗ cannot solve because it runs out of memory.
How can one change the performance of a heuristic search algorithm?
The performance of heuristic search algorithms depends on the quality of the heuristic function. One can sometimes construct good heuristics by relaxing the problem defi- nition, by storing precomputed solution costs for subproblems in a pattern database, or by learning from experience with the problem class.
