Save the file

pq.py

to your own directory. This contains the definition of a PriorityQueue class. Read through the implementation and see if you understand how it works. You can test it by modifying the test code at the bottom of the file, but you don’t really need to completely understand this file.
Save the file

informedSearch.py

to your own directory. This contains updated definitions of the classes we used in the previous question. The InformedNode class now takes a goal state and has an added method called priority. The InformedSearch class now uses a priority queue and creates instances of the InformedNode class in its execute method. It also keeps track of how many nodes it has expanded during the search process and reports this with the solution. The InformedProblemState now has an added method called heuristic which takes a goal state and returns an estimate of the distance from the current state to the goal state.

Create a file that implements the states, operators, and heuristics needed for the eight puzzle problem. Your EightPuzzle class should inherit from the InformedProblemState class. Remember to make sure that your operators make a copy of the current state before moving the tiles.

Test your solution on the following starting states A-H using the same goal each time. State A should take 2 steps, state B should take 6 steps, and state C should take 8 steps. You’ll need to determine the length of the other solutions.

  
1 2 3  1 3    1 3 4    1 3  7 1 2  8 1 2  2 6 3  7 3 4  7 4 5
8   4  8 2 4  8 6 2  4 2 5  8   3  7   4  4   5  6 1 5  6   3
7 6 5  7 6 5    7 5  8 7 6  6 5 4  6 5 3  1 8 7  8   2  8 1 2
goal     A      B      C      D      E      F      G      H

In order to demonstrate that A* is superior to standard BFS and that the Manhattan distance heuristic is more informed than the tiles out of place heuristic, you will compare the number of nodes that each search expands on the problems given above (A-H). The only change you’ll need to make to do a BFS search rather than an A* search is to replace the priority queue with the standard queue that we used in the previous question. One easy way to do this is to always have a heuristic, but in BFS have the heuristic always return 0. Convince yourself that this is equivalent to BFS. Inside a comment in your eight puzzle file, create and fill in the following table:

            Node Expansions
Problem   BFS  A*(tiles)  A*(dist)
A
B
C
D
E
F
G
H

### File: search.py
### This file includes four class definitions: Queue, Node,
### Search, ProblemState
# from exceptions import *
# This is a global variable that is used to avoid revisiting repeated
# states. It needs to be reset to an empty dictionary each time
# a search is run.
VisitedStates = {}
class Queue:
“””
A Queue class to be used in combination with state space
search. The enqueue method adds new elements to the end. The
dequeue method removes elements from the front.
“””
def __init__(self):
self.queue = []
def __str__(self):
result = “Queue contains ” + str(len(self.queue)) + ” items\n”
for item in self.queue:
result += str(item) + “\n”
return result
def enqueue(self, node):
self.queue.append(node)
def dequeue(self):
if not self.empty():
return self.queue.pop(0)
else:
raise RunTimeError
def empty(self):
return len(self.queue) == 0
class Node:
“””
A Node class to be used in combination with state space search.
A node contains a state, a parent node, the name of the operator
used to reach the current state, and the depth of the node in
the search tree. The root node should be at depth 0. The method
repeatedState can be used to determine if the current state
is the same as the parent’s parent’s state. Eliminating such
repeated states improves search efficiency.
“””
def __init__(self, state, parent, operator, depth):
self.state = state
self.parent = parent
self.operator = operator
self.depth = depth
def __str__(self):
result = “State: ” + str(self.state)
result += ” Depth: ” + str(self.depth)
if self.parent != None:
result += ” Parent: ” + str(self.parent.state)
result += ” Operator: ” + self.operator
return result
def repeatedState(self):
global VisitedStates
if str(self.state) in VisitedStates:
return 1
else:
VisitedStates[str(self.state)] = True
return 0
# if self.parent == None: return 0
# if self.parent.state.equals(self.state): return 1
# if self.parent.parent == None: return 0
# if self.parent.parent.state.equals(self.state): return 1
# return 0
class Search:
“””
A general Search class that can be used for any problem domain.
Given instances of an initial state and a goal state in the
problem domain, this class will print the solution or a failure
message. The problem domain should be based on the ProblemState
class.
“””
def __init__(self, initialState, goalState):
self.clearVisitedStates()
self.q = Queue()
self.q.enqueue(Node(initialState, None, None, 0))
self.goalState = goalState
solution = self.execute()
if solution == None:
print(“Search failed”)
else:
self.showPath(solution)
def clearVisitedStates(self):
global VisitedStates
VisitedStates = {}
def execute(self):
while not self.q.empty():
current = self.q.dequeue()
if self.goalState.equals(current.state):
return current
else:
successors = current.state.applyOperators()
operators = current.state.operatorNames()
for i in range(len(successors)):
if not successors[i].illegal():
n = Node(successors[i],
current,
operators[i],
current.depth+1)
if n.repeatedState():
del(n)
else:
self.q.enqueue(n)
# Uncomment the line below to see the queue.
# print “Enqueuing state: ” + str(n)
return None
def showPath(self, node):
path = self.buildPath(node)
for current in path:
if current.depth != 0:
print(“Operator:”, current.operator)
print( current.state)
print(“Goal reached in”, current.depth, “steps”)
def buildPath(self, node):
“””
Beginning at the goal node, follow the parent links back
to the start state. Create a list of the states traveled
through during the search from start to finish.
“””
result = []
while node != None:
result.insert(0, node)
node = node.parent
return result
class ProblemState:
“””
An interface class for problem domains.
“””
def illegal(self):
“””
Tests the state instance for validity.
Returns true or false.
“””
abstract()
def applyOperators(self):
“””
Returns a list of successors to the current state,
some of which may be illegal.
“””
abstract()
def operatorNames(self):
“””
Returns a list of operator names in the same order
as the successors list is generated.
“””
abstract()
def equals(self, state):
“””
Tests whether the state instance equals the given
state.
“””
abstract()

from pq import *
from search import *
class InformedNode(Node):
“””
Added the goal state as a parameter to the constructor. Also
added a new method to be used in conjunction with a priority
queue.
“””
def __init__(self, goal, state, parent, operator, depth):
Node.__init__(self, state, parent, operator, depth)
self.goal = goal
def priority(self):
“””
Needed to determine where the node should be placed in the
priority queue. Depends on the current depth of the node as
well as the estimate of the distance from the current state to
the goal state.
“””
return self.depth + self.state.heuristic(self.goal)
class InformedSearch(Search):
“””
A general informed search class that uses a priority queue and
traverses a search tree containing instances of the InformedNode
class. The problem domain should be based on the
InformedProblemState class.
“””
def __init__(self, initialState, goalState):
self.expansions = 0
self.clearVisitedStates()
self.q = PriorityQueue()
self.goalState = goalState
self.q.enqueue(InformedNode(goalState, initialState, None, None, 0))
solution = self.execute()
if solution == None:
print(“Search failed”)
else:
self.showPath(solution)
print(“Expanded”, self.expansions, “nodes during search”)
def execute(self):
while not self.q.empty():
current = self.q.dequeue()
self.expansions += 1
if self.goalState.equals(current.state):
return current
else:
successors = current.state.applyOperators()
operators = current.state.operatorNames()
for i in range(len(successors)):
if not successors[i].illegal():
n = InformedNode(self.goalState,
successors[i],
current,
operators[i],
current.depth+1)
if n.repeatedState():
del(n)
else:
self.q.enqueue(n)
return None

class InformedProblemState(ProblemState):
“””
An interface class for problem domains used with informed search.
“””
def heuristic(self, goal):
“””
For use with informed search. Returns the estimated
cost of reaching the goal from this state.
“””
abstract()

class PriorityQueue:
“””
Implements a heap-style priority queue with O(lg n) enqueue and
dequeue methods. The priority queue is stored as a list where
position 0 always contains None. The first actual item is stored
in position 1. This is necessary so that the list can be treated
as a binary tree and simple calculations can be done to find the
parent, and left and right sub-trees. The items being stored are
expected to be instances of a class which has a priority() method.
“””
def __init__(self):
self.q = [None]
def __str__(self):
result = “Queue contains ” + str(len(self.q)-1) + ” items”
if not self.empty():
result += “-Minimum item has priority: ” + \
str(self.min().priority())
return result
def parent(self, i):
return i//2
def right(self, i):
return (i * 2) + 1
def left(self, i):
return i * 2
def hasLeft(self, i):
return self.left(i) <= len(self.q)-1 def hasRight(self, i): return self.right(i) <= len(self.q)-1 def empty(self): return len(self.q) == 1 def swap(self, p1, p2): self.q[p1], self.q[p2], = self.q[p2], self.q[p1] def bubbleUp(self,i): p = self.parent(i) if i==1 or self.q[i].priority() >= self.q[p].priority():
return
else:
self.swap(i, p)
self.bubbleUp(p)
def bubbleDown(self, i):
if (not self.hasLeft(i)) and (not self.hasRight(i)):
return
elif self.hasLeft(i) and (not self.hasRight(i)):
l = self.left(i)
if self.q[i].priority() > self.q[l].priority():
self.swap(i, l)
self.bubbleDown(l)
else:
l = self.left(i)
r = self.right(i)
key = self.q[i].priority()
if self.q[l].priority() >= key and self.q[r].priority() >= key:
return
elif self.q[l].priority() <= self.q[r].priority(): self.swap(i, l) self.bubbleDown(l) else: self.swap(i, r) self.bubbleDown(r) def min(self): if self.empty(): raise RunTimeError return self.q[1] def dequeue(self): if self.empty(): raise RunTimeError result = self.q.pop(1) self.q.insert(1, self.q.pop(len(self.q)-1)) self.bubbleDown(1) return result def enqueue(self, item): self.q.append(item) self.bubbleUp(len(self.q)-1) if __name__ == '__main__': class Test: """ A simple class created to test the priority queue. The PriorityQueue class expects to store instances of a class that has a method called priority(). """ def __init__(self, v): self.value = v def __str__(self): return str(self.value) def priority(self): return self.value print("Creating a PriorityQueue") pq = PriorityQueue() print("Check that an empty queue is printable") print(pq) print("Inserting 10, 5, 2, 12, 25") pq.enqueue(Test(10)) pq.enqueue(Test(5)) pq.enqueue(Test(2)) pq.enqueue(Test(12)) pq.enqueue(Test(25)) print(pq) print("Removing the minimum until empty") while (not pq.empty()): print(pq.dequeue())