Final Search Flashcards
Q1. State the five elements that characterize a search problem instance/search algorithm.
Answer:
- Initial state
- Set of actions
- Goal state
- Search space
- Path cost
Q2. What is meant by search algorithm completeness?
Answer: This means that if solution to the problem exists, the algorithm is guaranteed to find within a finite amount of time.
Q3. What is meant by search algorithm optimality?
Answer: The algorithm is optimal if when it finds a solution it is the best one (in terms of some measure, e.g. path length).
Q4. Explain the distinction between optimality and optimal efficiency for search algorithms.
Answer: For an algorithm to be optimal means that the solution that it finds is the best one, while being optimally efficient means that no other optimal algorithm finds the solution faster than the one used.
Q5. What are the advantages of breadth-first search (BFS) over depth-first search (DFS)? What is the advantage of DFS over BFS?
Answer: BFS is optimal and complete, while DFS is not optimal and gets stuck in cycles. BFS is better when there are many solution and the goal is to find the best solution possible. Or when solution lies close to the start node. DFS in it’s turn has better space complexity and works better when there is only one solution and it lies far from the start node.
Q6. Explain what the frontier is in a graph-search problem, and what it is used for.
Answer: A frontier in a graph-search problem is the set of paths that the algorithm could explore next. It is used to store the path that algorithm need to explore, the way the frontier is expanded defines the search strategy.
Q7. What node(s) is/are in the frontier of a depth-first search?
Answer: In a DFS, the frontier contains every child of the one single node expanded at each level of the tree.
Q8. Where b is the maximum branching factor and d is the maximum depth of the search, characterize the maximum size of a DFS frontier.
Answer: b*(d-1) is the maximum size of a dfs frontier as it contains all nodes in one current path of length d and all neighbors of those nodes. Each node has at most (d-1) neighbors so the maximum size = b*(d-1)
Q9. Is the worst-case time complexity different for DFS and BFS? Why or why not?
Answer: No, it is the same. The reason for that is that in the worst case, both DFS and BFS have to expand all the nodes in order to find the solution.
Q10. Consider the following generic search algorithm:
1 Input: a graph,
2 a set of start nodes,
3 Boolean procedure goal(n) that tests if n is a goal node.
4 frontier := { : s is a start node};
5 while frontier is not empty:
6 select and remove path from frontier;
7 if goal(nk)
8 return ;
9 for every neighbor n of nk
10 add to frontier;
11 end while
Imagine that this generic algorithm was used as the basis for an implementation of depth first search and of breadth-first search. Which line or lines of the pseudocode above must have different implementations? Briefly, how would those implementations differ?
Answer: None, the algorithm is the same, the difference is in the way you expand frontier and the frontier itself. For example for DFS the frontier is the last-in-first-out stack meaning that the path that was added to the frontier last will be expanded first. For BFS the frontier is first-in-first-out queue - the path added last will be expanded last. (Line 6 does the expand of the frontier).
Q11. What is the distinction between informed and uninformed search?
Answer: Uninformed search strategies do not take into account any information about the state and the goal when making the decision on which path to expand, while informed search strategies do. Often informed strategies use heuristics to guide in the search space.
Q12. What is a heuristic?
Answer: Heuristic is a knowledge that helps guide the search. Often it is an estimate of the cost of the optimal path from node n to the goal node.
Q13. Give the definition of an admissible heuristic.
Answer: Admissible heuristic is such an estimate of the path cost, so that if we denote real cost of the optimal path from node n to any goal node as c(n) and admissible heuristic as h(n), the following is true: h(n) <= c(n) for all nodes n. In other words it is an underestimate of the real cost.
Alternative: A heuristic is admissible if it doesn’t overestimate the distance to the goal.
Q14. Is the max of two admissible heuristics also admissible? Why or why not?
Answer: Yes, if a heuristic is an underestimate of real cost of optimal path, it stays an underestimate even if better heuristic exists.
Q15. Consider two admissible heuristics h1 and h2. Which one of the following options would yield a better heuristic for use with A*? Briefly explain your answer. (a) min(h1, h2) (b) max(h1, h2) (c) (h1+h2)/2 (d) A* will have the same performance in all cases.
Answer: b. Maximum of two admissible heuristics is a better heuristic for use with A* because it is a closer estimate to the real cost of the optimal path.
