Homework 1 Six-Puzzle

Question 1: * You will probably find it easier to write a program to solve this problem.
Consider a variant of the eight-puzzle, which we saw in class, where we reduce the size of the puzzle to 3x2, in order to keep the number of states manageable. Now, consider the following initial and goal states:
Initial state: Goal state: 1 4 2 5 3
a) Show the solution path (i.e., the sequence of puzzle states from the initial to the goal state) found by each of the following algorithms, assuming transitions have unit cost. You must ensure that puzzle states that have been explored are not added to the search queue. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer the state that involves moving a lower-numbered piece. i. Breadth first search ii. Uniform cost search iii. Depth first search iv. Iterative deepening
b) Suppose now that transitions have differing costs. In particular, the cost of a transition is equal to the number of the piece that is moved (e.g., moving the “4” costs 4). If we employ the Manhattan distance heuristic for the original unit cost version of the eight-puzzle presented in class (Lecture 3, slide 13, ℎ2), would this heuristic still be an admissible heuristic for A* search in the new variant? Justify your answer.
c) Design an admissible heuristic that dominates the heuristic from part b, under the same transition cost scheme as part b.
d) Now consider another variant of the problem in which moving pieces to the left or right costs 2, whereas moving pieces up or down costs 0.5. Would the Manhattan distance heuristic from part b still be admissible? Justify your answer.
1 2 5 4 3
Question 2: Search algorithms * You will probably find it easier to solve this problem by hand. (From Russell & Norvig)
a) Describe a state space in which iterative deepening search performs much worse than depth-first search (for example, 𝑂(𝑛2) vs 𝑂(𝑛)).
Prove each of the following statements, or give a counterexample: b) Breadth-first search is a special case of uniform-cost search. c) Depth-first search is a special case of best-first tree search. d) Uniform-cost search is a special case of A* search.
Question 3: Optimization * You will probably find it easier to write a program to solve this problem.
Consider the following function: Y= sin(X2/2)/log2(X+4), in the range X=[0, 10]. a) Apply hill-climbing, starting from each of the following starting points: X0={0, 1, 2, …, 10} and step sizes ∆𝑋 = {0.01, 0.02, …, 0.1}. b) Repeat using simulated annealing with a range of different temperatures and annealing schedules (of your choosing). Consider each of the different starting points in (a). Consider only those step sizes from part (a) that produced a good result (use your own judgment in defining this; briefly explain your reasoning and method.) For each part report the number of steps to convergence and final result (X*,Y*) for each case. Use plots and/or tables to report your results in an organized manner. Don’t forget to include labels & captions.
Question 4: Constraint satisfaction * You will probably find it easier to solve this problem by hand. (Adapted from Russell & Norvig)
Consider the problem of placing k rooks on an n x n chessboard such that no two rooks are attacking each other, where k is given and 𝑘 ≤ 𝑛2.
a) Formulate this problem as a Constraint Satisfaction problem. Describe the set of variables, and their domain. List the set of constraints.
b) Show the search tree generated with applying backtracking search, without forward checking for the problem with k = 3 and n = 3. Show clearly the domain for each variable at every point in the search.
c) Show the search tree generated with applying backtracking search, this time using forward checking for the problem with k = 3 and n = 3.