diff options
Diffstat (limited to 'search.py')
| -rw-r--r-- | search.py | 41 |
1 files changed, 22 insertions, 19 deletions
@@ -169,35 +169,38 @@ def breadthFirstSearch(problem): def uniformCostSearch(problem): """Search the node of least total cost first.""" "*** YOUR CODE HERE ***" - - # lambda to get the total cost of a node + # 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: problem.getCostOfActions(node[3]) - pq = util.PriorityQueueWithFunction(cost) - pq.push((problem.getStartState(), None, 0, [])) + nodes = util.PriorityQueueWithFunction(cost) + + # 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 pq.isEmpty(): - node = pq.pop() + while not nodes.isEmpty(): + node = nodes.pop() - # Add nextNode to visited list + # 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) - # base case + # Chech if the current node is the goal state and if it is, return the path if problem.isGoalState(node[0]): return node[3] - # Get all successors and push them into a priority queue based on cost - nextNodes = problem.getSuccessors(node[0]) - for nextNode in nextNodes: - # Append the node's path + nextNode's direction + # 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]],) - - # Check that nextNode has not been visited - if visited.has_key(nextNode[0]) and visited[nextNode[0]] < cost(nextNode): - continue - - # Push the child if it was not visited - pq.push(nextNode) + nodes.push(nextNode) def nullHeuristic(state, problem=None): |