def dfs_recursive(problem: SearchProblem, state, direction_stack: util.Stack):
if (problem.isGoalState(state) == 1):
return True
a = problem.getSuccessors(state)
a.reverse()
check = False
for i in a:
#print("burdayız")
#print(i)
if i[0] not in problem._visited:
#print(i)
direction_stack.push(i)
d = dfs_recursive(problem, i[0], direction_stack)
check = check or d
if not d:
direction_stack.pop()
return check
def depthFirstSearch(problem: SearchProblem):
"""
Search the deepest nodes in the search tree first.
Your search algorithm needs to return a list of actions that reaches the
goal. Make sure to implement a graph search algorithm.
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print("Start:", problem.getStartState())
print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
print("Start's successors:", problem.getSuccessors(problem.getStartState()))
"""
"*** YOUR CODE HERE ***"
direction_stack = util.Stack()
start_state = problem.getStartState()
print(start_state)
dfs_recursive(problem, start_state, direction_stack)
direction_list = list()
while (not direction_stack.isEmpty() ):
v = direction_stack.pop()
print(v)
direction_list.append(v[1])
direction_list.reverse()
#print(direction_list)
print(len(direction_list))
return direction_list
"""
print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
a = problem.getSuccessors(problem.getStartState())
for i in a:
b = a[0][0]
c = problem.getSuccessors(b)
print("Start:", problem.getStartState())
print("Start's successors:", problem.getSuccessors(problem.getStartState()))
print("2nd successors:", c)
util.raiseNotDefined()
"""
def breadthFirstSearch(problem: SearchProblem):
"""Search the shallowest nodes in the search tree first."""
"*** YOUR CODE HERE ***"
start_state = problem.getStartState()
Q = util.Queue()
Q.push((start_state, []))
while (not Q.isEmpty()):
v = Q.pop()
if (problem.isGoalState(v[0])):
return v[1]
else:
neigh = problem.getSuccessors(v[0])
for i in neigh:
if i[0] not in problem._visited:
next_list = v[1].copy()
next_list.append(i[1])
Q.push((i[0],next_list))
def uniformCostSearch(problem: SearchProblem):
"""Search the node of least total cost first."""
"*** YOUR CODE HERE ***"
start_state = problem.getStartState()
Q = util.PriorityQueue()
Q.push((start_state, [], 0), 0)
while (not Q.isEmpty()):
v = Q.pop()
if (problem.isGoalState(v[0])):
return v[1]
else:
neigh = problem.getSuccessors(v[0])
for i in neigh:
if i[0] not in problem._visited:
next_list = v[1].copy()
next_list.append(i[1])
next_pr = v[2] + i[2]
Q.push((i[0],next_list, next_pr), next_pr)