Base on the function of BFS, rename it to iterative_deepening_search and modify it to perform a iterative deepening search. Test it with the graph below.

graph = { 'A': [('B', 3), ('C', 6), ('K', 5)], 'B': [], 'C': [('D', 4), ('P', 1)], 'D': [('B', 4)], 'G': [('K', 4)], 'H': [('G', 3)], 'K': [('H', 6), ('L', 5)], 'L': [('G', 3)], 'P': [('Q', 1)], 'Q': [('H', 1)] }import queue def breadth_first_search(graph_to_search, initial_state, goal_state, verbose=False): # In frontiers, we store a list because we need to eventually return # the entire PATH from the initial state to the goal state. So, # each element in the queue represents a path from the the initial # state to one frontier node. frontiers = queue.Queue() frontiers.put((0, [initial_state])) # a tuple of the cost and the path visited = set() # a set while not frontiers.empty(): # use while loop to iteratively perform search cost, path = frontiers.get() # Get the next element in the frontier queue node = path[-1] # Get the last node in this path if node in visited: # check if we have expanded this node, if yes then drop it. continue if verbose: print(f'Expanding {node}...') actions = graph_to_search[node] # get the possible actions for next_node, next_cost in actions: if next_node in visited: continue # skip this node if it is already expanded. new_path = path.copy() new_path.append(next_node) new_cost = cost + next_cost # check if we reache the goal state or not if next_node == goal_state: return new_path, new_cost # if yes, we can return this path and its cost else: frontiers.put((new_cost, new_path)) # add to the frontiers # after exploring all actions, we add this node to the visited set visited.add(node) return None, Nonepath, cost = breadth_first_search(graph, 'A', 'G') print('The solution is:', path) print('The cost is:', cost)
 

Transcribed Image Text:

L 3- G 4 3. H 5 6- K 2- C1-P 5 6 4 A 3. B D L 3- G 4 3. H 5 6- K 2- C1-P 5 6 4 A 3. B D

Answer rating: 100% (QA)

import queue def depthlimitedsearchgraphtosearch initialstate goalstate maxdepth frontie... View the full answer