diff options
-rw-r--r-- | search.py | 66 |
1 files changed, 32 insertions, 34 deletions
@@ -92,40 +92,38 @@ def depthFirstSearch(problem): def breadthFirstSearch(problem): """Search the shallowest nodes in the search tree first.""" - # main search function - - # initialize - queue = util.Queue() - visited = [] - path = [] - start = (problem.getStartState(), None, 0) - - queue.push(start) - path.append(start) - visited.append(problem.getStartState()) - - def getActions(list, goal): - start = problem.getStartState() - path = [] - list = list[1:] - list = list[::-1] - state = next((node for node in list if node[0][0] == goal), None) - while state[0][1] is not start: - path.insert(0, state[0][1]) - state = next((node for node in list if node[0] == state[1]), None) - if state is None: - return path - return path - - while not queue.isEmpty(): - state = queue.pop() - if problem.isGoalState(state[0]): - return getActions(path, state[0]) - for successor in problem.getSuccessors(state[0]): - if successor[0] not in visited: - visited.append(successor[0]) - path.append((successor, state)) - queue.push(successor) + # 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.Queue() + + # 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[3] + + # 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 uniformCostSearch(problem): |