diff options
Diffstat (limited to 'search.py')
-rw-r--r-- | search.py | 66 |
1 files changed, 30 insertions, 36 deletions
@@ -86,45 +86,39 @@ def depthFirstSearch(problem): print "Is the start a goal?", problem.isGoalState(problem.getStartState()) print "Start's successors:", problem.getSuccessors(problem.getStartState()) """ - "*** YOUR CODE HERE ***" - - def traverse(problem, node, visited): - - # Add nextNode to visited list - visited.append(node[0]) - # Recursive base case + # The only differences between the search functions: + # 1. Cost: Lambda function to get the total cost of a node + # 2. Nodes: Data structure to store the nodes + cost = lambda node: 1 + nodes = util.Stack() + + # Initialize start node and push onto nodes, + nodes.push((problem.getStartState(), None, 0, [])) + + # Dictionary of visited nodes; key: node's (x,y); value: current cost of + # actions to get to the node + visited = {} + + while not nodes.isEmpty(): + node = nodes.pop() + + # If the node has been traversed by a cheaper path, skip it + if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + continue + + # Add set the value at the nodes index to the cost + visited[node[0]] = cost(node) + + # Chech if the current node is the goal state and if it is, return the path if problem.isGoalState(node[0]): - return [node[1]] - - pq = util.PriorityQueueWithFunction(lambda child: child[2]) - - # Get all successors and push them into a priority queue based on cost - children = problem.getSuccessors(node[0]) - for nextNode in children: - # Check that nextNode has not been visited - if nextNode[0] in visited: - continue - - # Push the child if it was not visited - pq.push(nextNode) - - while not pq.isEmpty(): - # Pop lowest cost child from the queue - nextNode = pq.pop() - - # Recursive call to nextNode - path = traverse(problem, nextNode, visited) - - # Check if recursive call returned values - if path != None: - # Check to not add the initial node - if node[1] != None: - # Add the node the start of the list (reverse it) - path.insert(0, node[1]) - return path + return node[3] - return traverse(problem, (problem.getStartState(), None, 0), []) + # Get all successors, and set each nodes's path to previous node's + # path + nextNode's direction and push it onto stack + for nextNode in problem.getSuccessors(node[0]): + nextNode = nextNode + (node[3] + [nextNode[1]],) + nodes.push(nextNode) def breadthFirstSearch(problem): |