created python.py

syamkumar · web-flow · commit 9671ed272a6b · 2017-10-25T23:35:39.000+05:30
performed breadth first search using python
diff --git a/BestFirstSearch/python.py b/BestFirstSearch/python.py
@@ -0,0 +1,39 @@
+class SearchNode:
+    def __init__(self, action, state, parent):
+        self.state = state
+        self.action = action
+        self.parent = parent
+    def path(self):
+        if self.parent == None:
+            return [(self.action, self.state)]
+        else:
+            return self.parent.path() + [(self.action, self.state)]
+    def inPath(self, s):
+        if s == self.state:
+            return True
+        elif self.parent == None:
+            return False
+        else:
+            return self.parent.inPath(s)
+ 
+def breadthFirstSearch(initialState, goalTest, actions, successor):
+    agenda = Queue()
+    if goalTest(initialState):
+        return [(None, initialState)]
+    agenda.push(SearchNode(None, initialState, None))
+    while not agenda.isEmpty():
+        parent = agenda.pop()
+        newChildStates = []
+        for a in actions(parent.state):
+            newS = successor(parent.state, a)
+            newN = SearchNode(a, newS, parent)
+            if goalTest(newS):
+                return newN.path()
+            elif newS in newChildStates:
+                pass
+            elif parent.inPath(newS):
+                pass
+            else:
+                newChildStates.append(newS)
+                agenda.push(newN)
+    return None
