diff options
Diffstat (limited to 'search.py')
| -rw-r--r-- | search.py | 88 |
1 files changed, 46 insertions, 42 deletions
@@ -93,8 +93,12 @@ def depthFirstSearch(problem): cost = lambda node: 1 nodes = util.Stack() + # create a Node structure + from collections import namedtuple + Node = namedtuple('Node', ['state', 'stepCost', 'actions']) + # Initialize start node and push onto nodes, - nodes.push((problem.getStartState(), None, 0, [])) + nodes.push(Node(problem.getStartState(), 0, [])) # Lists used to keep track of visited nodes and their costs visitedList = [] @@ -102,26 +106,23 @@ def depthFirstSearch(problem): 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 state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): + if node.state in visitedList and visitedCost[visitedList.index(node.state)] <= cost(node): continue # Add the node to the visited lists - visitedList.append(state) + visitedList.append(node.state) visitedCost.append(cost(node)) # Check if the current node is the goal state and if it is, return the path - if problem.isGoalState(state): - return actions + if problem.isGoalState(node.state): + return node.actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for state, action, stepCost in problem.getSuccessors(state): - nextNode = (state, action, stepCost, actions + [action]) - nodes.push(nextNode) + for state, action, stepCost in problem.getSuccessors(node.state): + nodes.push(Node(state, stepCost, node.actions + [action])) def breadthFirstSearch(problem): @@ -133,8 +134,12 @@ def breadthFirstSearch(problem): cost = lambda node: 1 nodes = util.Queue() + # create a Node structure + from collections import namedtuple + Node = namedtuple('Node', ['state', 'stepCost', 'actions']) + # Initialize start node and push onto nodes, - nodes.push((problem.getStartState(), None, 0, [])) + nodes.push(Node(problem.getStartState(), 0, [])) # Lists used to keep track of visited nodes and their costs visitedList = [] @@ -142,26 +147,23 @@ def breadthFirstSearch(problem): 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 state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): + if node.state in visitedList and visitedCost[visitedList.index(node.state)] <= cost(node): continue # Add the node to the visited lists - visitedList.append(state) + visitedList.append(node.state) visitedCost.append(cost(node)) # Check if the current node is the goal state and if it is, return the path - if problem.isGoalState(state): - return actions + if problem.isGoalState(node.state): + return node.actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for state, action, stepCost in problem.getSuccessors(state): - nextNode = (state, action, stepCost, actions + [action]) - nodes.push(nextNode) + for state, action, stepCost in problem.getSuccessors(node.state): + nodes.push(Node(state, stepCost, node.actions + [action])) def uniformCostSearch(problem): @@ -170,11 +172,15 @@ def uniformCostSearch(problem): # 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]) + cost = lambda node: problem.getCostOfActions(node.actions) nodes = util.PriorityQueueWithFunction(cost) + # create a Node structure + from collections import namedtuple + Node = namedtuple('Node', ['state', 'stepCost', 'actions']) + # Initialize start node and push onto nodes, - nodes.push((problem.getStartState(), None, 0, [])) + nodes.push(Node(problem.getStartState(), 0, [])) # Lists used to keep track of visited nodes and their costs visitedList = [] @@ -182,26 +188,23 @@ def uniformCostSearch(problem): 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 state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): + if node.state in visitedList and visitedCost[visitedList.index(node.state)] <= cost(node): continue # Add the node to the visited lists - visitedList.append(state) + visitedList.append(node.state) visitedCost.append(cost(node)) # Check if the current node is the goal state and if it is, return the path - if problem.isGoalState(state): - return actions + if problem.isGoalState(node.state): + return node.actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for state, action, stepCost in problem.getSuccessors(state): - nextNode = (state, action, stepCost, actions + [action]) - nodes.push(nextNode) + for state, action, stepCost in problem.getSuccessors(node.state): + nodes.push(Node(state, stepCost, node.actions + [action])) def nullHeuristic(state, problem=None): @@ -217,11 +220,15 @@ def aStarSearch(problem, heuristic=nullHeuristic): # The only differences between the search functions: # 1. Cost: Lambda function to get the total cost of a node + heuristic # 2. Nodes: Data structure to store the nodes - cost = lambda node: problem.getCostOfActions(node[3]) + heuristic(node[0], problem) + cost = lambda node: problem.getCostOfActions(node.actions) + heuristic(node.state, problem) nodes = util.PriorityQueueWithFunction(cost) + # create a Node structure + from collections import namedtuple + Node = namedtuple('Node', ['state', 'stepCost', 'actions']) + # Initialize start node and push onto nodes, - nodes.push((problem.getStartState(), None, 0, [])) + nodes.push(Node(problem.getStartState(), 0, [])) # Lists used to keep track of visited nodes and their costs visitedList = [] @@ -229,26 +236,23 @@ def aStarSearch(problem, heuristic=nullHeuristic): 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 state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): + if node.state in visitedList and visitedCost[visitedList.index(node.state)] <= cost(node): continue # Add the node to the visited lists - visitedList.append(state) + visitedList.append(node.state) visitedCost.append(cost(node)) # Check if the current node is the goal state and if it is, return the path - if problem.isGoalState(state): - return actions + if problem.isGoalState(node.state): + return node.actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for state, action, stepCost in problem.getSuccessors(state): - nextNode = (state, action, stepCost, actions + [action]) - nodes.push(nextNode) + for state, action, stepCost in problem.getSuccessors(node.state): + nodes.push(Node(state, stepCost, node.actions + [action])) # Abbreviations bfs = breadthFirstSearch |