Search (Midterm) Flashcards
State the main elements that characterize a search algorithm
Definition of a search problem
- State space
- Initial states
- Sets of actions
- Goal state
- path cost
or
1) State
2) Successor function
3) Goal state
4) solution
5) heuristic if there is one
Main properties of search
1) time complexity
2) space complexity
3) completeness
4) Optimality
Explain what the frontier is in a graph-search problem. and what it is used for.
Frontier is some data structure used in search which maintains paths from the start node that have been explored.
As search proceeds, the frontier expands into unexplored nodes until a goal node is encountered.
The way in which the frontier is expanded defines the search strategy.
Where b is the maximum branching factor and d is the maximum depth of the search, characterize the maximum size of a DFS frontier.
The maximum size of a DFS frontier is when it is at its worst case, the size is b*d.
Is the worst-case time complexity difference for DFS and BFS? Why or why not
Yes they are different, BFS has worst time complexity of b^m, and DFS has b*d.
Give the definition of an admissible heuristic
A search heuristic is admissible if it never overestimates the actual cost of the cheapest path from a node to a goal
In what sense is BFS better than DFS? In what sense is DFS better than BFS?
BFS is better if:
- When space is not a problem
- It is necessary to find solution with fewest arcs
- There are cycles
- We care about optimality
DFS is better if:
- Space is limited
- All solutions tend to be located deep in the tree
- The branching factor is very large
In what sense is branch and bound better than A? In what sense is A better than branch and bound?
Branch and bound has better space complexity: O(bm) vs. O(b^m)
Uses less memory
Time complexity is the same: O(b^m)
A: complete, optimal (if heuristic is admissible)
Branch and bound: complete (only if UB is initialized to finite value) and optimal (if heuristic is admissible)
A expands the minimal number of nodes→ more efficient (optimal efficiency)
Is the sum of two admissible heuristics also admissible?
No, not necessarily, the sum of 2 heuristics can be larger than the cost of the actual path
Is the max of two admissible heuristics also admissible?
Yes, because if a heuristic is admissible an underestimate still remains an underestimate even if a better heuristic exists
Is the min of two admissible heuristics also admissible?
Yes, because if a heuristic is admissible an underestimate still remains an underestimate especially for the min of two heuristics.
Explain the distinction between optimality and optimal efficiency of search algorithm
An algorithm is optimally efficient if there is no algorithm that finds an optimal solution better (less number of nodes expanded for example) that it does. Algorithms is optimal if the solution found is the best one.
Assume you run uniformed iterative deepening to find solution no more than k steps from the start node (k>2). In worst case, how many times the nodes two steps from the start node will be generated? Why?
k-2 times
Assume uniformed iterative deepening is running. If the algorithm has reached the stage in which DFS is running with bound depth 6: must it be true that the start state is not the goal? Why? must it be true that there are no solution at level 3? Why?
Yes because iterative deepening runs DFS with a set bound if IDS has already reached bound depth 6 which means in the previous depth IDS was not able to find the goal node. If the start state is the solution or solution at are located at depth 3, IDS would already found it.
