diff options
Diffstat (limited to 'search.py')
| -rw-r--r-- | search.py | 103 |
1 files changed, 57 insertions, 46 deletions
@@ -96,28 +96,31 @@ def depthFirstSearch(problem): # 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 = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(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] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # 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]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -133,28 +136,31 @@ def breadthFirstSearch(problem): # 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 = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(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] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # 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]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -170,28 +176,31 @@ def uniformCostSearch(problem): # 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 = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(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] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # 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]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -210,35 +219,37 @@ def aStarSearch(problem, heuristic=nullHeuristic): # 2. Nodes: Data structure to store the nodes cost = lambda node: problem.getCostOfActions(node[3]) + heuristic(node[0], problem) 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 = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(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] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # 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]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) - # Abbreviations bfs = breadthFirstSearch dfs = depthFirstSearch |