A * Search Python

Practical 9 :
Write a program to implement A*algorithm.

Code:

import heapq


hfun={
    'A':7,
    'B':6,
    'C':2,
    'D':1,
    'E':0}

gfun={
    'A':{
        'B':1,
        'C':4    },
    'B':{
        'C':2,
        'D':5,
        'E':12    },
    'C':{
        'D':2    },
    'D':{
        'E':3    },
    'E':{

    }
}


class PriorityQueue:
    def __init__(self):
        self.elements = []

    def empty(self):
        return len(self.elements) == 0
    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def get(self):
        return heapq.heappop(self.elements)[1]

class SimpleGraph:
    def __init__(self):
        self.edges = {}

    def neighbors(self, id):
        return self.edges[id]

    def cost(self,current,next):
        return gfun[current][next]


def a_star_search(graph, start, goal):
    frontier = PriorityQueue();
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None    cost_so_far[start] = hfun[start];

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break
        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + hfun[next];
                frontier.put(next, priority)
                came_from[next] = current

    return came_from


example_graph = SimpleGraph()
example_graph.edges = {
    'A': ['B','C'],
    'B': [ 'C', 'D','E'],
    'C': ['D'],
    'D': ['E'],
    'E': []
}

pathMatrix=a_star_search(example_graph,'A','E');
print ("Path is:")
c='E'while c!='A':
    print(c, end='<-')
    c=pathMatrix[c]

Output:

Next Practical 10

http://gndecprogramming.blogspot.in/2018/04/panagram-checking-python.html