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