1. For each of the following tasks, list two suitable performance measures:
Driving in a car racing event.
Filtering spam mails.
Online product recommendation system
2. Using the Romanian map in the textbook, search for the path to Bucharest from Lugoj using graph-search BFS. For equally preferred nodes, generate and expand them in alphabetical order. Show the frontier after each step, the order of expanded nodes, and the solution found.
3. Same as problem #2, but use A* search with the straight-line distance heuristic. When showing the frontier, include the f, g, and h score for each node.
In chess, a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. The problem is to move a rook from square A to square B in the smallest number of moves. For example, in the figure below, the red line is a 3-step solution
(the x's mark other pieces).
What is the maximum branching factor from any square? Assume an 8x8 board, as the example below.
Design an admissible heuristic for this problem. You need to provide your rationale (what constraint is removed) and also explain why it is admissible. Is it consistent?
Assume that graph-search is used, count the number of squares reachable from A at each different step count using BFS. How many nodes have to be generated at step counts below 3, the solution depth?
Repeat (c) using IDS instead of BFS.
Assume that graph-search is used, run A* using your heuristic. How many nodes are expanded (A and B included) during the search from A and B?
x
x B
x x
x
x x
Notes:
Late submission penalty: 10% per day for up to 3 days.
Please submit the assignment through the E3 system.
