Module pacai.student.search

In this file, you will implement generic search algorithms which are called by Pacman agents.

Functions

def aStarSearch(problem, heuristic)

Search the node that has the lowest combined cost and heuristic first.

def breadthFirstSearch(problem)

Search the shallowest nodes in the search tree first. [p 81]

def depthFirstSearch(problem)

Search the deepest nodes in the search tree first [p 85].

Your search algorithm needs to return a list of actions that reaches the goal. Make sure to implement a graph search algorithm [Fig. 3.7].

To get started, you might want to try some of these simple commands to understand the search problem that is being passed in:

print("Start: %s" % (str(problem.startingState())))
print("Is the start a goal?: %s" % (problem.isGoal(problem.startingState())))
print("Start's successors: %s" % (problem.successorStates(problem.startingState())))

def uniformCostSearch(problem)

Search the node of least total cost first.