Implement Maps and Search Tree in Python Assignment Solution.

# 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[0].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[0].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[0].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'][0], 'Drayton', weight=100)

# Children of Drayton: Listowel

add_child(tree['children'][0]['children'][0], 'Listowel', weight=100)

# Children of New Hamburg: Stratford

add_child(tree['children'][1], 'Stratford', weight=25)

# Children of Stratford: St. Marys, Drayton

add_child(tree['children'][1]['children'][0], 'St. Marys', weight=30)

add_child(tree['children'][1]['children'][0], 'Drayton', weight=200)

# Children of St. Marys: Mitchell

add_child(tree['children'][1]['children'][0]

['children'][0], 'Mitchell', weight=80)

# Children of Mitchell: Listowel

add_child(tree['children'][1]['children'][0]['children']

[0]['children'][0], 'Listowel', weight=100)

# Children of Drayton: Listowel

add_child(tree['children'][1]['children'][0]

['children'][1], '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()