zhibo's notebook

Tesing

def aStarSearch(problem, heuristic=nullHeuristic):
  "Search the node that has the lowest combined cost and heuristic first."
  "*** YOUR CODE HERE ***"
  
  closedset = []
  start = problem.getStartState()
  openset = util.PriorityQueue()
  g_score = {}
  h_score = {}
  f_score = {}
  g_score[start] = 0
  h_score[start] = heuristic(start, problem)
  f_score[start] = h_score[start]
  openset.push( start, f_score[start])
  action = []
  came_from = {}
  came_from_action = {}
  while not openset.isEmpty():
	x = openset.pop()
	print x
	if problem.isGoalState(x):
		break
	closedset.append(x)
	for y in problem.getSuccessors(x):
		if y[0] in closedset:
			continue
		tentative_g_score = g_score[x] + 1
		g_score[y[0]] = g_score[x] + 1
		h_score[y[0]] = heuristic(y[0], problem)
		f_score[y[0]] = g_score[y[0]] + h_score[y[0]]
		
		if not openset.isHas(y[0]):
			openset.push(y[0], f_score[y[0]])
			tentative_is_better = True
		elif (tentative_g_score < g_score[y[0]]):
			tentative_is_better = True
		else:
			tentative_is_better = False
		
		if tentative_is_better == True:
			came_from[y[0]] = x
			came_from_action[y[0]] = y[1]
			g_score[y[0]] = tentative_g_score
			h_score[y[0]] = heuristic(y[0],problem)
			f_score[y[0]] = g_score[y[0]] + h_score[y[0]]
	
  v = x
  while v != start:
	action.append(came_from_action[v])
	v = came_from[v]
  
  action.reverse()
  return action
  
  util.raiseNotDefined()