+1 (315) 557-6473 

Implement Maps and Search Tree in Python Assignment Solution.


Instructions

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

Requirements and Specifications

program to implement map and search tree in python
program to implement map and search tree in python 1

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[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()