diff options
author | Neil Kollack <nkollac@siue.edu> | 2021-08-31 22:48:52 -0500 |
---|---|---|
committer | Neil Kollack <nkollac@siue.edu> | 2021-08-31 22:48:52 -0500 |
commit | 66a88a1cd8242218327551226338aeb865b60fab (patch) | |
tree | 19614fd25732e8d10f67661d6c6c3d408b49d814 /search.py | |
parent | af648f856bb1517449e4bae86b7e7f4e326c2268 (diff) |
implemented Breadth-First Search
Diffstat (limited to 'search.py')
-rw-r--r-- | search.py | 38 |
1 files changed, 36 insertions, 2 deletions
@@ -91,8 +91,42 @@ def depthFirstSearch(problem): def breadthFirstSearch(problem): """Search the shallowest nodes in the search tree first.""" - "*** YOUR CODE HERE ***" - util.raiseNotDefined() + + # 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) + def uniformCostSearch(problem): """Search the node of least total cost first.""" |