Merge branch 'bfs' into develop

1 files changed, 32 insertions, 34 deletions

diff --git a/search.py b/search.py
index 863c863..9003b00 100644
--- a/search.py
+++ b/search.py
@@ -130,40 +130,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):