Tree-Search algorithms Flashcards
What characterizes Best-first search (greedy search)
It first expands the node with minimum value of some evaluation function, f(n)
What characterizes breadth-first search (BFS).
Uses FIFO. Expands one layer at a time.
Optimal: Yes
Time: O(b^d)
Space: O(b^d)
What characterizes Depth-first search (DFS)?
Uses LIFO. Goes as far down it can, and backtracks to expand rest of the nodes.
Optimal: No (returns first solution it finds.)
Time: O(b^d)
Space: O(bm), where m is branching factor and m is maximum depth.
What characterizes iterative deepening search?
Uses depth-first search on a limited depth. Increases depth with each iteration until it finds solution.
Optimal: Yes.
Time: O(b^d)
Space: O(bm)
What is the idea with bidirectional search?
Saving time, since b^{d/2} + b^{n/2} «_space;b^{d}
What does bidirectional search do?
Searches both forward from initial state and backwards from goal state, hoping they meet.
What is meant by a heuristic function?
A function that estimates the cost of the cheapest path from the state at node n to a goal state.
What characterizes greedy best-first search?
Expands node with lowest h(n) value. (The value that appears to be closest to goal.)
Optimal: No
Complete: Yes (but no in infinite state-spaces)
What characterizes A* search?
Uses the evaluation function: f(n) = g(n) + h(n)
Where g(n) is the cost from initial state to n, and h(n) is the estimated cost of shortest path from n to goal state.
Complete: Yes
Cost optimal: Yes (depends on quality of heuristic)
What is the requirement for the heuristic function in informed search algorithms?
The heuristic must not overestimate.
What makes satisficing search different from informed search?
Satisficing search explores fewer nodes at the cost of possibly finding a sub-optimal but “good enough” solution.
What makes weighted A* different from normal A* search?
The heuristic is valued more heavily:
f(n) = g(n) + W * h(n) for W > 1
List ways memory-bounded search saves memory.
By storing a given state once in either the frontier or reached-lists.
Removing states from reached when we know they are not needed.
Having a reference counter, for the number of times a state has occurred. (For only storing a given state once.)
What characterizes the Beam search-group?
It limits the size of the frontier. Keeps on the k best nodes with the best f(x)-scores, and removes the rest.
What makes recursive best-first search different from best-first search.
Recursive best-first search uses a variable to keep track of the f(x) value of the best alternative path available from any ancestor of the current node.
Goes back if the node exceeds the value of the variable.
