Homework 4: Short Answer and Programming Homework 2

For this homework you will be programming using student_code_hw4.py and you will answer questions about the code in this document that will be named as HW4_YourName.pdf.  You will turn in the document                           HW4_YourName.pdf in along with the student_code_hw4.py file on GradeScope.

Checklist

1)    Are your written answers in a document called HW4_YourName.pdf?

2)    Is all of your code in the student_code_hw4.py file?

3)    Have you uploaded both files to GradeScope by Monday, October 10 at 11:59 p.m.?

8 Puzzle Problem

The 8 Puzzle Problem consists of a 3x3 tray in which the goal is to get the initial configuration to the goal state by shifting the numbered tiles into the blank space.

We have a total of 9 blank tiles giving us a total of 9! initial configuration but not all of these are solvable. The solvability of a configuration can be checked by calculating the Inversion Permutation. If the total      Inversion Permutation is even then the initial configuration is solvable else the initial configuration is not  solvable which means that only 9!/2 initial states lead to a solution.

Let's define our goal state and solve the puzzle using A* and the default heuristic.  The following code shows you how to run an EightPuzzle with A* search.  The other searches are similar in nature.  Instead of printing out the     result of a function call as done by the code below, your code could return the solutions and print them in the main function.

#EightPuzzle

#Default goal is goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)

puzzle = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))

# checks whether the initialized configuration is solvable or not

puzzle.check_solvability((2, 4, 3, 1, 5, 6, 7, 8, 0))

print(astar_search(puzzle).solution()))

Problem 1:  (a, b: 5 points each; Each question worth 3 points; 25 points total) Solve the instances of the EightPuzzle problem in student_code_hw4.py where:

a)    the initial state is (1, 0, 3, 4, 6, 8, 2, 7, 5) and the goal state is (1, 2, 3, 4, 5, 6, 7, 8, 0) using                astar_search. The default heuristic used in the software is the number of misplaced tiles.  Return the solution found by astar_search to the function call in main and print it.

b)    the initial state is (2, 1, 3, 4, 0, 6, 5, 7, 8) and the goal state is (1, 2, 3, 4, 0, 5, 6, 7, 8) using                astar_search. The default heuristic used in the software is the number of misplaced tiles.  Return the solution found by astar_search to the function call in main and print it.

To find out how to pass in a different goal, you will need to look at the EightPuzzle class in search.py and review the constructor’s input parameters. You can also look in the directory /tests/test_search.py for an   example on how to call the EightPuzzle with a goal state.

Answer the following questions for problem a in your HW4_YourName.pdf document

1)    Show what the possible next states would look like after THE START STATE.  You can draw them or list them using the format (x, x, x, x, x, x, x, x, x) where the x’s are the number of the tile at locations (0,0),     (0,1), (0,2), (1,0), (1,1), (1,2),(2,0), (2,1),(2,2).

2)    For each state, what is the value of g() and what is the value of h()?  Be specific.

3)    What would be the next state chosen immediately after the start state?

4)    Is the first state selected after the start state the one that is shown in the solution as being on the optimal path?   Yes or No

5)    How is the actual cost of the path to a node determined for each node state?  Be specific.

Problem 2 (15 points):  Now that you have A* search running, run problem 1a and 1b using a different heuristic. Currently the default is the number of tiles that are not in their proper place.  We can pass in a new heuristic to the A* algorithm - the Manhattan distance heuristic.  We will use the code below to create the Manhattan distance      heuristic for your use – and note,  the code below has been added to the file: student_code_hw4.py

# Added to student_code_hw4.py file

import math

def manhattan(node):

state = node.state

index_goal = {0:[2,2], 1:[0,0], 2:[0,1], 3:[0,2], 4:[1,0], 5:[1,1], 6:[1,2],

7:[2,0], 8:[2,1]}

index_state = {}

index = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]

x, y = 0, 0

for i in range(len(state)):

index_state[state[i]] = index[i]

mhd = 0

for i in range(8):

for j in range(2):

mhd = abs(index_goal[i][j] - index_state[i][j]) + mhd

return mhd

#=======Your Turn to run it===========

# A* with 8-Puzzle and different heuristic

# An example for you to follow to get you started on heuristics

puzzle = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))

# Checks whether the initialized configuration is solvable or not

puzzle.check_solvability((2, 4, 3, 1, 5, 6, 7, 8, 0))

print ("Default")

print (hw4.example_problem_1 (puzzle, astar_search))

puzzle = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))

print ("Manhattan")

print (hw4.problem_2a: (puzzle, astar_search, hw4.manhattan))

a) (5 points)  Run the example code from above in student_code_hw4.py and answer the following question: Are the paths the same?  Yes or No   -- Explain why you got the answer you did.

b) (10 points – 5 points code, 5 points answer)  Run your own code with the start path of (1, 0, 3, 4, 6, 8, 2, 7,

5) and the default goal.  Use the default heuristic and the manhattan heurstic.  Put your code in Problem 2_b and call the method in main.

Are the paths the same?  Yes or No   Explain why you got the answer you did.

Problem 3 (30 points): Use the following algorithms:

depth_first_graph_search

iterative_deepening_search,

breadth_first_graph_search,

uniform_cost_search,

astar_search

a)    (10 points for each problem below (2 points per algorithm); total 20 points)

On the Romanian map, you will solve the following problems for each algorithm.  You will return  the solution found and print the solution in the main function.

1)    find a path from Arad to Bucharest

2)    find a path from Iasi to Sibiu

b)     (5 points)

Compare the performance of the search algorithms and problem instances from 3a) for the path from Iasi to Sibiu using the function compare_searchers and return the results.  Print the results.

c)    (5 points)

What did you learn from comparing the search algorithms?  You only need to discuss the most significant thing you learned.

Problem 4 (15 points – 5 points each):

A drawback of A* is its memory requirement since the frontier might get very large.  Suppose you modify A* as      follows:  you keep in the frontier only the best N nodes (with N > 1). When the frontier is full and a new node has to be stored, the worst node is deleted from it and forever removed from consideration.

a)    If the heuristic used is admissible, is the modified algorithm guaranteed to find an optimal solution? Explain your reasoning precisely.

b)    Does the value of N make any difference in the ability of the algorithm to find an optimal solution? Why or why not?

c)    If a perfect heuristic is used (i.e. for all nodes n, h(n) = h*(n), where h*(n) is the cost of the optimal path  from n to a goal node), is the modified algorithm guaranteed to find an optimal solution? does the answer depend on the value of N

Problem 5 (15 points – 5 points each):

Read the paper, Genetic Algorithms:  Principles of Natural Selection Applied to Computation, pages 872 -873 (only read up to section Genetic Algorithms for Solving Problems).  Answer the following questions using the paper to     guide your answers:

a)    What does the fitness function do?