1. What is the space complexity of Greedy search?
a) O(b)
b) O(bl)
c) O(m)
d) O(bm)
Explanation: O(bm) is the space complexity where b is the branching factor and m is the maximum depth of the search tree. Since this algorithm resembles the DFS.
2. What is the evaluation function in A* approach?
a) Heuristic function
b) Path cost from start node to current node
c) Path cost from start node to current node + Heuristic cost
d) Average of Path cost from start node to current node and Heuristic cost
Explanation: The most widely-known form of best-first search is called A* search. It evaluates nodes by combining g(n), the cost to reach the node, and h(n.), the cost to get from the node to the goal: f(n) = g(n) + h(n). Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal.
3. A* is optimal if h(n) is an admissible heuristic-that is, provided that h(n) never underestimates the cost to reach the goal.
a) true
b) false
Explanation: A* is optimal if h(n) is an admissible heuristic-that is, provided that h(n) never overestimates the cost to reach the goal. Refer both the example from the book for better understanding of the algorithms.
4. _________________ are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations.
a) Constraints Satisfaction Problems
b) Uninformed Search Problems
c) Local Search Problems
d) All of the mentioned
Explanation: Constraints Satisfaction Problems
5. Which of the Following problems can be modeled as CSP?
a) 8-Puzzle problem
b) 8-Queen problem
c) Map coloring problem
d) All of the mentioned
Explanation: All of above problems involves constraints to be satisfied.
6. What among the following constitutes to the incremental formulation of CSP?
a) Path cost
b) Goal cost
c) Successor function
d) All of the mentioned
Explanation:
Initial state: The empty assignment ( ), in which all variables are unassigned.
Successor function: A value can be assigned to any unassigned variable, provided it does not conflict with previously assigned variables.
Goal test: The current assignment is complete.
Path cost: A constant cost (e.g., 1) for every step.
7. The term ___________ is used for a depth-first search that chooses values for one variable at a time and returns when a variable has no legal values left to assign.
a) Forward search
b) Backtrack search
c) Hill algorithm
d) Reverse-Down-Hill search
Explanation: Refer definition of backtracking algorithm.
8. To overcome the need to backtrack in constraint satisfaction problem can be eliminated by ____________
a) Forward Searching
b) Constraint Propagation
c) Backtrack after a forward search
d) Omitting the constraints and focusing only on goals
Explanation: Forward Searching is technique in which a forward check till k steps is made to analyze that the goal can be achieved satiating all constraints. With constraint propagation, constraints on a variable can be propagated to next level/hierarchy and satisfied at that level, eliminating need to backtrack.
9. Consider a problem of preparing a schedule for a class of student. What type of problem is this?
a) Search Problem
b) Backtrack Problem
c) CSP
d) Planning Problem
Explanation: Schedule developer needs to consider all constraints on teacher as well as students.
10. Constraint satisfaction problems on finite domains are typically solved using a form of ___________
a) Search Algorithms
b) Heuristic Search Algorithms
c) Greedy Search Algorithms
d) All of the mentioned
Explanation: Any Search techniques can be used