AI_search strategies

Start from state A. Goal state is G. The number over each edge indicates the cost to transition from one state to another. What is the order of nodes visited by BFS (including the start and goal state too)? Break any ties using lexicographic ordering and do not perform duplicate detection.

Consider f(n) = g(n) + 5h(n). What is the order of nodes visited by best-first search algorithm? (Start-node is S, no duplicate detection)

Start state is a, and goal state is z. Cost of transitioning from one node to another are mentioned over the corresponding edge. Numbers on the node are the heuristic values. Assume successors are returned in reverse lexicographic order. In case of ties, use lexicographic ordering for breaking ties.For A* search with full duplicate detection, what is the order in which the nodes are visited?

Which of the following is/are false regarding the A* search algorithm ?

• It gives optimal solutions

• A* search algorithm has a better worst-case space time complexity than DFS if the heuristic used is admissible

• It is a systematic search algorithm

• It helps improve the worst-case time complexity of the search

Consider the given adversarial search tree. Assume that the search always chooses children from left to right. The search tree uses alpha-beta pruning.

Which of the following nodes are pruned during the search?

• J

• K

• L

• M

• N

Which of the following is/are true regarding the basic mini-max adversarial search algorithm?

• It is complete if the search tree is finite

• It is optimal for all kinds of adversaries

• The worst-case time complexity and space complexity is similar to that of Depth First Search

• By itself, it cannot play games like Chess and Go due to huge search depths.

Which of the following is/are false regarding the alpha-beta pruning for the mini-max search algorithm?

• It can potentially lead to suboptimal solutions compared to mini-max search without any pruning

• It is guaranteed to improve the running time in-comparison to the mini-max search without any pruning

• The order in which nodes are visited affects the amount of pruning

• If the successors of a node are chosen randomly, the time complexity (on average) is O(b3^m/4)

What will be the value of the node labelled ‘a’ after the run of the min-max search algorithm on the following search tree. Here upwards facing triangles are max nodes, downward facing triangles are min nodes and circles denote game-ends.

Which of the following is/are FALSE for heuristic functions in the context of adversarial search ?

• They can be learnt from data/experience for eg. by playing games with another agent

• They help deal with the problem of extremely large search depths in practice

• They help reduce the worst-case time complexity of minimax search without comprising optimality against optimal adversaries

• They can be hand-engineered by humans/experts

Which of the following is/are true for a search tree with a finite branching factor and all costs greater than one?

• Depth-First Search (DFS) is not complete

• Iterative Deepening Search is systematic

• Uniform Cost Search is optimal

• Breadth-First Search is typically preferred over Depth-First Search in situations where memory is limited