why the following code doesn't work to find A*/uniform cost algorithm in java of a 3x3: the
Question:
why the following code doesn't work to find A*/uniform cost algorithm in java of a 3x3:
the code is supposed to output the v,d,b of each algorithm along with the path
please put full corrected code
import copy
import sys
import heapq
class PriorityQueue():
def __init__(self):
self.thisQueue = []
def push(self, thisNode):
heapq.heappush(self.thisQueue, (thisNode.val, -thisNode.id, thisNode))
def pop(self):
return heapq.heappop(self.thisQueue)[2]
def isEmpty(self):
return len(self.thisQueue) == 0
def length(self):
return len(self.thisQueue)
class Set():
def __init__(self):
self.thisSet = set()
def add(self,entry):
if entry is not None:
self.thisSet.add(entry.__hash__(self))
def length(self):
return len(self.thisSet)
def isMember(self,query):
return query.__hash__() in self.thisSet
nodeid=0
class Node():
def __init__(self,val,startstate,endstate,depth):
global nodeid
self.id = nodeid
nodeid += 1
self.val = val
self.start= startstate
self.end=endstate
self.depth=depth
def __str__(self):
return 'Node: id=%d val=%d'%(self.id,self.val,self.state)
class state():
def __init__(self):
self.xpos = 0
self.ypos = 0
self.tiles = [[0,1,2],[3,4,5],[6,7,8]]
def left(self):
if (self.ypos == 0):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos-1]
s.ypos -= 1
s.tiles[s.xpos][s.ypos] = 0
return s
def right(self):
if (self.ypos == 2):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos+1]
s.ypos += 1
s.tiles[s.xpos][s.ypos] = 0
return s
def up(self):
if (self.xpos == 0):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos-1][s.ypos]
s.xpos -= 1
s.tiles[s.xpos][s.ypos] = 0
return s
def down(self):
if (self.xpos == 2):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos+1][s.ypos]
s.xpos += 1
s.tiles[s.xpos][s.ypos] = 0
return s
# def __hash__(self):
# return (tuple(self.tiles[0]),tuple(self.tiles[1]),tuple(self.tiles[2]))
def __str__(self):
return '%d %d %d\n%d %d %d\n%d %d %d\n'%(
self.tiles[0][0],self.tiles[0][1],self.tiles[0][2],
self.tiles[1][0],self.tiles[1][1],self.tiles[1][2],
self.tiles[2][0],self.tiles[2][1],self.tiles[2][2])
def copy(self):
s = copy.deepcopy(self)
return s
def h0(currenttiles,stiles):
misplaced=0
for i in range(len(stiles)):
for j in range(len(currenttiles)):
if (stiles[i][j] != currenttiles[i][j]):
misplaced+=1
return misplaced
def manhattan(currenttiles,stiles):
total=0
for i in range(len(stiles)):
for j in range(len(currenttiles)):
if (stiles[i][j] != currenttiles[i][j]):
y=stiles[i][j]
a=i
b=j
for k in range(len(stiles)):
for l in range(len(stiles)):
if (currenttiles[k][l] == y):
d=k
e=l
count=(abs(d-a)+abs(e-b))
total+=count
return total
class state():
def __init__(self):
self.xpos = 0
self.ypos = 0
self.tiles = [[0,1,2],[3,4,5],[6,7,8]]
def left(self):
if (self.ypos == 0):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos-1]
s.ypos -= 1
s.tiles[s.xpos][s.ypos] = 0
return s
def right(self):
if (self.ypos == 2):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos+1]
s.ypos += 1
s.tiles[s.xpos][s.ypos] = 0
return s
def up(self):
if (self.xpos == 0):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos-1][s.ypos]
s.xpos -= 1
s.tiles[s.xpos][s.ypos] = 0
return s
def down(self):
if (self.xpos == 2):
return None
s = self.copy()
s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos+1][s.ypos]
s.xpos += 1
s.tiles[s.xpos][s.ypos] = 0
return s
def __hash__(self):
return (tuple(self.tiles[0]),tuple(self.tiles[1]),tuple(self.tiles[2]))
def __str__(self):
return '%d %d %d\n%d %d %d\n%d %d %d\n'%(
self.tiles[0][0],self.tiles[0][1],self.tiles[0][2],
self.tiles[1][0],self.tiles[1][1],self.tiles[1][2],
self.tiles[2][0],self.tiles[2][1],self.tiles[2][2])
def copy(self):
s = copy.deepcopy(self)
return s
frontier = PriorityQueue()
closedlist = Set()
def astar(initial_state, goal_state, closedlist):
initial_node = Node(0, initial_state, goal_state, 0)
frontier.push(initial_node)
V=0
N=0
d=0
while not frontier.isEmpty():
if (frontier.length()> N):
N=frontier.length()
current_node = frontier.pop()
V+=1
if current_node.state == goal_state:
d = current_node.depth # Found the solution
return d, N, V
expanded = expand(current_node, closedlist, goal_state)
for node in expanded:
frontier.push(node)
return None, V, N, d
def expand(current_node,closedlist,goal_state):
closedlist.add(current_node.state)
successors= []
current_state = Node.state()
up_child = current_state.up()
down_child = current_state.down()
right_child = current_state.right()
left_child = current_state.left()
children = [left_child,right_child,up_child,down_child]
for child in children:
if child is not None and not closedlist.isMember(child):
s = Node(0, child, None, current_node.depth + 1)
s.parent_node = current_node
if child == left_child:
s.action = "left"
elif child == right_child:
s.action = "right"
elif child == up_child:
s.action = "up"
elif child == down_child:
s.action = "down"
successors.append(s)
return successors
def main():
inputs = []
for line in sys.stdin:
inputs += line.split()
array = [
[int(inputs[0]), int(inputs[1]), int(inputs[2])],
[int(inputs[3]), int(inputs[4]), int(inputs[5])],
[int(inputs[6]), int(inputs[7]), int(inputs[8])]
]
s = state()
current = state()
current.tiles = array
s.tiles =[[0,1,2],[3,4,5],[6,7,8]]
array2=s.tiles
printMan=manhattan(array,array2)
array3=Set()
print()
for i in range(3):
for j in range(3):
print(array[i][j], end= " ")
print()
print()
for i in range(3):
for j in range(3):
print(array2[i][j], end= " ")
print()
print("Manhattan:",printMan)
h0p=h0(array,array2)
print("misplaced",h0p)
h1p=astar(current,s,closedlist)
print(h1p)
main()
International Marketing And Export Management
ISBN: 9781292016924
8th Edition
Authors: Gerald Albaum , Alexander Josiassen , Edwin Duerr