search.py 文件源码

def uniformCostSearch(problem):
  "Search the node of least total cost first. "
  frontier = PriorityQueue()
  startNode = Node((problem.getStartState(), None, None))

  #Check if start node is goal
  if problem.isGoalState(startNode.state):
      return []

  for successors in problem.getSuccessors(problem.getStartState()):
      newNode = Node(successors, startNode)
      frontier.push(newNode, 0)

  explored = list()
  explored.append(startNode.state)

  while not frontier.isEmpty():
      leafNode = frontier.pop()
      if problem.isGoalState(leafNode.state):
          return leafNode.getPath()
      explored.append(leafNode.state)
      for successor in problem.getSuccessors(leafNode.state):
          newNode = Node(successor, leafNode)
          if newNode.state not in frontier.stateList and newNode.state not in explored:
              frontier.push(newNode, newNode.pathCost)
  return []