started work on uniform cost search

1 files changed, 30 insertions, 1 deletions

diff --git a/search.py b/search.py
index b360091..583e419 100644
--- a/search.py
+++ b/search.py
@@ -169,7 +169,36 @@ def breadthFirstSearch(problem):
 def uniformCostSearch(problem):
     """Search the node of least total cost first."""
     "*** YOUR CODE HERE ***"
-    util.raiseNotDefined()
+
+    # lambda to get the total cost of a node
+    cost = lambda node: problem.getCostOfActions(node[3])
+    pq = util.PriorityQueueWithFunction(cost)
+    pq.push((problem.getStartState(), None, 0, []))
+    visited = {}
+
+    while not pq.isEmpty():
+        node = pq.pop()
+
+        # Add nextNode to visited list
+        visited[node[0]] = cost(node)
+
+        # base case
+        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
+            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)
+
 
 def nullHeuristic(state, problem=None):
     """