search.py 文件源码

def uniformCostSearch(problem):
  "Search the node of least total cost first. "
  "*** YOUR CODE HERE ***"
  frontier = util.PriorityQueue()
  visited = []
  startNode = ((problem.getStartState(), None, 0), [], 0)
  frontier.push(startNode, None)
  while not frontier.isEmpty():
    curr = frontier.pop()
    currLoc = curr[0][0]
    currDir = curr[0][1]
    currPath = curr[1]
    currCost = curr[2]
    if currLoc not in visited:
      visited.append(currLoc)
      if(problem.isGoalState(currLoc)):
        return currPath
      successors = problem.getSuccessors(currLoc)
      successorsList = list(successors)
      for i in successorsList:
        if i[0] not in visited:
          if(problem.isGoalState(i[0])):
            return currPath + [i[1]]
          newNode = (i, currPath+[i[1]], currCost + i[2])
          frontier.push(newNode, currCost + i[2])
  return []