''' ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ''' ''' For Search Algorithms ''' ''' ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ''' ''' BFS add to queue ''' def add_to_queue_BFS(node_id, parent_node_id, cost, initialize=False): # Your code here return ''' BFS add to queue ''' def is_queue_empty_BFS(): # Your code here return False ''' BFS pop from queue ''' def pop_front_BFS(): (node_id, parent_node_id) = (0, 0) # Your code here return (node_id, parent_node_id) ''' DFS add to queue ''' def add_to_queue_DFS(node_id, parent_node_id, cost, initialize=False): # Your code here return ''' DFS add to queue ''' def is_queue_empty_DFS(): # Your code here return False 

code in python needed

Problem 2 [70 points]. Search algorithms. In this problem you are to implement the queue management functionality for DFS. BFS. Uniform-cost, and A* best-first search. Only graph search is required. In main.py, there is an illustration of the data structure used to encode a graph, which is a dictionary indexed by numerical node index numbers from 1 to n for an n-vertex graph. For each node, a multi-type list is used to store (i) the node index (node id), (i) the visited flag, (iii) the parent after the cost-to-come of the node becomes final, (iv) the cost-to-come for the node, (v) the neighbors as a list of id-cost tuples, and (vi) the id-cost tuple stored in a dictionary. For each X where X [DFS, BFS, UC, ASTAR), you are to implement three functions add to queue_X(node.id, parent_node.id, cost, initialize) is queue.empty_X() pop front.XO Where an item in a queue contains a tuple of the form (node_id, parent node_id). For DFS and BFS, there is no need to maintain the cost. You need to use one or more global variables in your code to hold the queue between calls to these functions. In add.to_queue_X, the last parameter initialize is set to true only when it is called the first time in a search when the start node is inserted into the queue. You should use this chance to initialize your internal queue data structure For each of the search methods, correct implementation will get you 15-20 points. For DFS and BFS (15 points each), there should be a deterministic path and for UC and A* (20 points each), the solution should also be mostly deterministic (there may be some variance due to tie-breaking) For UC and A* with consistent heuristics, the solution path should always be optimal. Note that the optimal cost is maintained for you already; there is nothing you need to do regarding the final cost if your implementation is correct Keep in mind that for actual grading, we will use larger graphs with tens of nodes A sample run of main.py, if you have correctly implemented your side, should produce the results shown as follows Graph search result dump DFS path : [1, 3, 4, 5], cost: 9, #expansions : 4 BFS path : [1,2,5], cost: 13,#expansions: 5 UC path: [1, 2, 3, 4, 5], cost: 8, #expansions : 5 A+ (admissible) path : [1, 3, 4, 5], cost: 9, #expansions : 4 A+ (consistent) path : [1, 2, 3, 4, 5], cost: 8, #expansions: 5 The n-queens problem A random state: [4, 5, 7, 5, 2, 5, 1], conflicting pairs: 5 Final state after hill-climbing: [4, 2, 7, 5, 2, 5, 1], conflicting pairs: 2 A valid solution: [2, 4, 6, 1, 3, 5, 7] Problem 2 [70 points]. Search algorithms. In this problem you are to implement the queue management functionality for DFS. BFS. Uniform-cost, and A* best-first search. Only graph search is required. In main.py, there is an illustration of the data structure used to encode a graph, which is a dictionary indexed by numerical node index numbers from 1 to n for an n-vertex graph. For each node, a multi-type list is used to store (i) the node index (node id), (i) the visited flag, (iii) the parent after the cost-to-come of the node becomes final, (iv) the cost-to-come for the node, (v) the neighbors as a list of id-cost tuples, and (vi) the id-cost tuple stored in a dictionary. For each X where X [DFS, BFS, UC, ASTAR), you are to implement three functions add to queue_X(node.id, parent_node.id, cost, initialize) is queue.empty_X() pop front.XO Where an item in a queue contains a tuple of the form (node_id, parent node_id). For DFS and BFS, there is no need to maintain the cost. You need to use one or more global variables in your code to hold the queue between calls to these functions. In add.to_queue_X, the last parameter initialize is set to true only when it is called the first time in a search when the start node is inserted into the queue. You should use this chance to initialize your internal queue data structure For each of the search methods, correct implementation will get you 15-20 points. For DFS and BFS (15 points each), there should be a deterministic path and for UC and A* (20 points each), the solution should also be mostly deterministic (there may be some variance due to tie-breaking) For UC and A* with consistent heuristics, the solution path should always be optimal. Note that the optimal cost is maintained for you already; there is nothing you need to do regarding the final cost if your implementation is correct Keep in mind that for actual grading, we will use larger graphs with tens of nodes A sample run of main.py, if you have correctly implemented your side, should produce the results shown as follows Graph search result dump DFS path : [1, 3, 4, 5], cost: 9, #expansions : 4 BFS path : [1,2,5], cost: 13,#expansions: 5 UC path: [1, 2, 3, 4, 5], cost: 8, #expansions : 5 A+ (admissible) path : [1, 3, 4, 5], cost: 9, #expansions : 4 A+ (consistent) path : [1, 2, 3, 4, 5], cost: 8, #expansions: 5 The n-queens problem A random state: [4, 5, 7, 5, 2, 5, 1], conflicting pairs: 5 Final state after hill-climbing: [4, 2, 7, 5, 2, 5, 1], conflicting pairs: 2 A valid solution: [2, 4, 6, 1, 3, 5, 7]