# Untitled

unknown
plain_text
2 years ago
3.6 kB
1
Indexable
Never
```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()))
"""

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()
"""

"""Search the shallowest nodes in the search tree first."""

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."""
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)```