.png)
Consider the Vacuum World Illustration as covered in the videos. Assume that now there are 3 rooms and 2 Roombas (autonomous robotic vacuum cleaners). Each room can be either dirty/clean and each Roomba is present in one of the 3 rooms.
What are the number of states in propositional/factored knowledge representation?
72
Which of the following is/are part of a node?
State
Path cost from initial state
Path cost to the goal
Parent node
Full duplicate detection can reduce the number of nodes to be visited from exponential to linear (in problem size).
True
False
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.
ACBEDFG
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 cost of the path given by BFS? Break any ties using lexicographic ordering and do not perform duplicate detection.
32
Consider the given graph.
What is the order of nodes visited by IDDFS (Iterative-deepening depth-first search)? Start from A, Goal State is E, break any ties using lexicographic ordering, and no duplicate detection.
ACBDFE
Which of the following problems is typically not modelled as a search problem?
Puzzle Solving eg. solving the 8-Puzzle
Path finding eg. finding the shortest path to a hospital in your city starting from your home
Stock Market Prediction i.e. predicting the stock prices using historical data / trends
Path Planning eg. finding the minimum cost path that visits all nodes in a graph and returns to the source node
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
Suppose there is only one goal state and each step cost is k (k>0, k is constant). Which of the following search algorithm(s) will return the optimal path?
Breadth-First Search
Depth First Search
Uniform Cost Search
Iterative Deepening Search
Which of the following is/are false regarding search? The maximum branching factor of the search tree is finite and is represented by b, d is the depth of the least cost solution and m is the maximum depth of the search-space
If m >> d, DFS (depth-first search) has a better worst-case time complexity than BFS (breadth-first search)
Unlike Iterative Deepening Search, BFS visits each world state exactly once and has a better worst-case time complexity than iterative deepening search
Bidirectional search, if applicable, has a better worst-case space complexity than BFS
BFS is optimal even if all step costs are not identical