In one sentence explanation for each class, and each method in each class. Specify the class attributes.
Question:
In one sentence explanation for each class, and each method in each class. Specify the class attributes. Go through the classes in this order:
- TileState
- TileProblem
- GraphTraverser
- class TileState:
#define a new Tile state given the locations of the tiles
def __init__(self, s, i,j):
self.state = s
self.x = i
self.y = j
self.set_state_name()
def set_state_with_name(self, s_name):
self.state=[]
#print("inside set state with name. State = \n****\n", s_name)
#set state
lines = s_name.split('\n')
lines.pop() #remove last line as it is empty.
for line in lines:
lst=[]
ns = line.split(',')
for i in range(3):
lst.append(int(ns[i]))
self.state.append(lst)
#set location of empty tile
for i in range(3):
for j in range(3):
if self.state[i][j]==-1:
self.x=i
self.y=j
break
#the state name shows the tile locations as a string
def set_state_name(self):
if self.state is None:
self.state_name='None'
#print('Can\'t set state name. State is None!')
return
name = ''
s = self.state
for i in range(0,len(s)):
for j in range(0,len(s)):
name = name + str(s[i][j]) + ','
name = name+'\n'
self.state_name = name
#=============================================
#=============================================
#=============================================
#tile problem class to hold all information about the tile problem
class TileProblem:
#istate is an object of tyle TileState
def __init__(self, istate):
self.initial_state = istate
self.n_tiles = 3
#ideal locations of tiles:
self.goal_loc = []
self.goal_loc.append( (0,0) ) #empty tile at 0,0
#1 => 0,1
self.goal_loc.append((0,1))
# 2 => 0,2
self.goal_loc.append((0,2))
# 3 => 1,0
self.goal_loc.append((1,0))
# 4 => 1,1
self.goal_loc.append((1,1))
# 5 => 1,2
self.goal_loc.append((1,2))
# 6 => 2,0
self.goal_loc.append((2,0))
# 7 => 2,1
self.goal_loc.append((2,1))
# 8 => 2,2
self.goal_loc.append((2,2))
#tstate is an object of type TileState
def expand_state(self, tstate):
x = tstate.x
y = tstate.y
nbr_states = []
#move right
if x>0:
rt_mv_s = copy.deepcopy(tstate.state)
rt_mv_s[x][y] = rt_mv_s[x-1][y] # move tile right
rt_mv_s[x-1][y] = -1 # set new empty tile
ts = TileState(rt_mv_s, x-1, y) #create new tilestate
nbr_states.append(ts) #append new tilestate to neighbors
#move left
if x
lt_mv_s[x][y] = lt_mv_s[x+1][y] # move tile left
lt_mv_s[x+1][y] = -1 # set new empty tile
ts = TileState(lt_mv_s, x+1, y) #create new tilestate
nbr_states.append(ts) #append new tilestate to neighbors
#move down
if y>0:
dn_mv_s = copy.deepcopy(tstate.state)
dn_mv_s[x][y] = dn_mv_s[x][y-1] # move tile down
dn_mv_s[x][y-1] = -1 # set new empty tile
ts = TileState(dn_mv_s, x, y-1) #create new tilestate
nbr_states.append(ts) #append new tilestate to neighbors
#move up
if y
up_mv_s[x][y] = up_mv_s[x][y+1] # move tile up
up_mv_s[x][y+1] = -1 # set new empty tile
ts = TileState(up_mv_s, x, y+1) #create new tilestate
nbr_states.append(ts) #append new tilestate to neighbors
return nbr_states
#get the cost of a state by adding distances of tiles to their goal states
def get_state_cost(self,tstate):
locs = tstate.state
sum_dist = 0
for i in range(0,self.n_tiles):
for j in range(0,self.n_tiles):
num = locs[i][j]
if num == -1:
continue
(i_goal, j_goal) = self.goal_loc[num]
sum_dist += abs(i_goal-i) + abs(j_goal-j)
return sum_dist
def is_goal_state(self, tstate):
sum_dist = self.get_state_cost(tstate)
if sum_dist == 0:
return True
else:
return False
class GraphTraverser:
def __init__(self, g):
self.graph = g
self.tree = Tree()
#===========================================
#===========================================
def a_star_traversal(self, tile_problem):
#extract initial state
initial_state = tile_problem.initial_state
#check if initial state is the goal state
if tile_problem.is_goal_state(initial_state):
print("Initial state is goal state!")
return
#set data structures
reached_states_cost_hn = {}
reached_states_cost_gn = {}
reached_states_cost_hn[initial_state.state_name] = tile_problem.get_state_cost(initial_state)
reached_states_cost_gn[initial_state.state_name] = 0
states_to_expand = {initial_state.state_name:1}
self.tree = Tree()
rootNode = TreeNode(initial_state.state_name, None)
self.tree.set_root(rootNode)
#expand initial state and append all states into the data structures
#while loop: keep expanding states until a goal state is reached
while len(states_to_expand)>0:
#compute all state costs
cost_fn={}
for c_state in states_to_expand:
cost_fn[c_state] = reached_states_cost_hn[c_state] + reached_states_cost_gn[c_state]
#find min-cost state
min_cost_state_name = min(cost_fn, key=cost_fn.get)
#pop the min cost state from the states_to_expand list:
states_to_expand.pop(min_cost_state_name)
#a state using the state name:
exp_state = TileState(None, -1,-1)
exp_state.set_state_with_name(min_cost_state_name)
#print("state created for min-cost state:\n")
#print(exp_state.state)
#print(exp_state.x, exp_state.y)
#check if goal state then return solution
if tile_problem.is_goal_state(exp_state):
print("Solution Found!: ", min_cost_state_name)
self.tree.print_path(TreeNode(min_cost_state_name,''))
break
#expand all its neighboring states
expanded_states = tile_problem.expand_state(exp_state)
#find neighbors' costs and add to expansion & reach lists & the traversal tree
for state in expanded_states:
#check if state has been previously reached, in which case, don't re-add as this will lead to infinite loops
if state.state_name not in reached_states_cost_hn:
reached_states_cost_hn[state.state_name] = tile_problem.get_state_cost(state)
reached_states_cost_gn[state.state_name] = reached_states_cost_gn[min_cost_state_name] + 1 # these states are 1 step away from the state being expanded now
states_to_expand[state.state_name]=1
#add node to traversal tree. all edge weights = 1 since each expanded state is one move away from its parent state
n = TreeNode(state.state_name, min_cost_state_name)
self.tree.add_child_node( n, min_cost_state_name, 1)
Expert Answer:
