# Implement Maps and Search Tree in Python Assignment Solution.

## Instructions

Objective
Write a python homework program to implement maps and search tree.

## Requirements and Specifications  Source Code

```# Node with weight # costs initialized with zeros to make calculations efficient. def get_node(name, weight=0): node = {} node['name'] = name node['children'] = [] node['weight'] = weight node['path'] = [] node['total'] = 0 return node def add_child(node, name, weight=0): node['children'].append(get_node(name, weight)) # Depth-first search def DFS(init_state, goal_name): """ Depth-First Search (BFS) Arguments --------- init_state : the root node of a search tree goal_name : A string, the name of a node, e.g. tree.childrend.name """ init_state['path'] = [init_state['name']] frontier = [init_state] explored = [] while len(frontier): state = frontier.pop() # dequeue explored.append(state['name']) if state['name'] == goal_name: return state for child in state['children']: if child['name'] not in explored: # enqueue: insert node at the end child['path'] = list(state['path']) child['path'].append(child['name']) child['total'] = child['weight'] + state['total'] frontier.append(child) return None # Breadth-first search def BFS(init_state, goal_name): """ Breadth-First Search (BFS) Arguments --------- init_state : the root node of a search tree goal_name : A string, the name of a node, e.g. tree.childrend.name """ init_state['path'] = [init_state['name']] frontier = [init_state] explored = [] while len(frontier): state = frontier.pop() # dequeue explored.append(state['name']) if state['name'] == goal_name: return state for child in state['children']: if child['name'] not in explored: # enqueue: insert node at the beginning child['path'] = list(state['path']) child['path'].append(child['name']) child['total'] = child['weight'] + state['total'] frontier.insert(0, child) return None # UCS helper def find_min_weight(frontier): # Helper func to find min weight/distance min_weight_i = 0 if len(frontier) > 1: min_weight = frontier[min_weight_i]['weight'] for i, state in enumerate(frontier): if state['weight'] < min_weight: min_weight_i = i min_weight = state['weight'] return min_weight_i def UCS(init_state, goal_name): """ Uniform Cost Search (UCS) Arguments --------- init_state : the root node of a search tree goal_name : A string, the name of a node, e.g. tree.childrend.name """ init_state['path'] = [init_state['name']] frontier = [init_state] explored = [] while len(frontier): # next state -> state w lowest cost/weight/distance state = frontier.pop(find_min_weight(frontier)) explored.append(state['name']) if state['name'] == goal_name: return True for child in state['children']: if child['name'] not in explored: child['weight'] += state['weight'] child['path'] = list(state['path']) child['path'].append(child['name']) child['total'] = child['weight'] frontier.append(child) return False # Greedy helper def find_min_heuristic(frontier): # Helper func to find min of h (the heuristic function) min_h_i = 0 if len(frontier) > 1: min_h = frontier[min_h_i]['heuristic'] for i, state in enumerate(frontier): if state['heuristic'] < min_h: min_h_i = i min_h = state['heuristic'] return min_h_i def GreedySearch(init_state, goal_name): frontier = [init_state] explored = [] while len(frontier): state = frontier.pop(find_min_heuristic(frontier)) explored.append(state['name']) if state['name'] == goal_name: return True for child in state['children']: if child['name'] not in explored: frontier.append(child) return False def main(): # Building the entire search tree based on the assignment init_state = 'Kitchener' goal_name = 'Listowel' tree = get_node(init_state) # Children of Kitchener: Guelph, New Hamburg add_child(tree, 'Guelph', weight=30) add_child(tree, 'New Hamburg', weight=90) # Children of Guelph: Drayton add_child(tree['children'], 'Drayton', weight=100) # Children of Drayton: Listowel add_child(tree['children']['children'], 'Listowel', weight=100) # Children of New Hamburg: Stratford add_child(tree['children'], 'Stratford', weight=25) # Children of Stratford: St. Marys, Drayton add_child(tree['children']['children'], 'St. Marys', weight=30) add_child(tree['children']['children'], 'Drayton', weight=200) # Children of St. Marys: Mitchell add_child(tree['children']['children'] ['children'], 'Mitchell', weight=80) # Children of Mitchell: Listowel add_child(tree['children']['children']['children'] ['children'], 'Listowel', weight=100) # Children of Drayton: Listowel add_child(tree['children']['children'] ['children'], 'Listowel', weight=100) print('DFS') goal = DFS(tree, goal_name) print('path: ', ', '.join(goal['path'])) print('total: ', str(goal['total'])) print('BFS') goal = BFS(tree, goal_name) print('path: ', ', '.join(goal['path'])) print('total: ', str(goal['total'])) print() if __name__ == '__main__': main()```