Q. What is A* algorithm?

A. 

It is a searching algorithm that is used to find the shortest path between an initial and a final point.

It is a handy algorithm that is often used for map traversal to find the shortest path to be taken. A* was initially designed as a graph traversal problem, to help build a robot that can find its own course. It still remains a widely popular algorithm for graph traversal.

It searches for shorter paths first, thus making it an optimal and complete algorithm. An optimal algorithm will find the least cost outcome for a problem, while a complete algorithm finds all the possible outcomes of a problem.

Another aspect that makes A* so powerful is the use of weighted graphs in its implementation. A weighted graph uses numbers to represent the cost of taking each path or course of action. This means that the algorithms can take the path with the least cost, and find the best route in terms of distance and time.

​

Q. Define graph of A*.

Q. Represent g(N) and h(N).

Q. How Does the A* Algorithm Work?

A.

Consider the weighted graph depicted above, which contains nodes and the distance between them. Let's say you start from A and have to go to D.

Now, since the start is at the source A, which will have some initial heuristic value. Hence, the results are

f(A) = g(A) + h(A)

f(A) = 0 + 6 = 6

Next, take the path to other neighbouring vertices :

​

f(A-B) = 1 + 4

f(A-C) = 5 + 2

​

Now take the path to the destination from these nodes, and calculate the weights :

f(A-B-D) = (1+ 7) + 0

f(A-C-D) = (5 + 10) + 0

It is clear that node B gives you the best path, so that is the node you need to take to reach the destination.

Q. Implementation of A* in Python

A.

Here you'll find the A* algorithm implemented in Python:

​

from collections import deque

​

class Graph:

    # example of adjacency list (or rather map)

    # adjacency_list = {

    # 'A': [('B', 1), ('C', 3), ('D', 7)],

    # 'B': [('D', 5)],

    # 'C': [('D', 12)]

    # }

​

    def __init__(self, adjacency_list):

        self.adjacency_list = adjacency_list

​

    def get_neighbors(self, v):

        return self.adjacency_list[v]

​

    # heuristic function with equal values for all nodes

    def h(self, n):

        H = {

            'A': 1,

            'B': 1,

            'C': 1,

            'D': 1

        }

​

        return H[n]

​

    def a_star_algorithm(self, start_node, stop_node):

        # open_list is a list of nodes which have been visited, but who's neighbors

        # haven't all been inspected, starts off with the start node

        # closed_list is a list of nodes which have been visited

        # and who's neighbors have been inspected

        open_list = set([start_node])

        closed_list = set([])

​

        # g contains current distances from start_node to all other nodes

        # the default value (if it's not found in the map) is +infinity

        g = {}

​

        g[start_node] = 0

​

        # parents contains an adjacency map of all nodes

        parents = {}

        parents[start_node] = start_node

​

        while len(open_list) > 0:

            n = None

​

            # find a node with the lowest value of f() - evaluation function

            for v in open_list:

                if n == None or g[v] + self.h(v) < g[n] + self.h(n):

                    n = v;

​

            if n == None:

                print('Path does not exist!')

                return None

​

            # if the current node is the stop_node

            # then we begin reconstructin the path from it to the start_node

            if n == stop_node:

                reconst_path = []

​

                while parents[n] != n:

                    reconst_path.append(n)

                    n = parents[n]

​

                reconst_path.append(start_node)

                reconst_path.reverse()

​

                print('Path found: {}'.format(reconst_path))

                return reconst_path

​

            # for all neighbors of the current node do

            for (m, weight) in self.get_neighbors(n):

                # if the current node isn't in both open_list and closed_list

                # add it to open_list and note n as it's parent

                if m not in open_list and m not in closed_list:

                    open_list.add(m)

                    parents[m] = n

                    g[m] = g[n] + weight

​

                # otherwise, check if it's quicker to first visit n, then m

                # and if it is, update parent data and g data

                # and if the node was in the closed_list, move it to open_list

                else:

                    if g[m] > g[n] + weight:

                        g[m] = g[n] + weight

                        parents[m] = n

​

                        if m in closed_list:

                            closed_list.remove(m)

                            open_list.add(m)

​

            # remove n from the open_list, and add it to closed_list

            # because all of his neighbors were inspected

            open_list.remove(n)

            closed_list.add(n)

​

        print('Path does not exist!')

        return None

​

Let's look at an example with the following weighted graph:

We run the code as so:

​

adjacency_list = {

    'A': [('B', 1), ('C', 3), ('D', 7)],

    'B': [('D', 5)],

    'C': [('D', 12)]

}

graph1 = Graph(adjacency_list)

graph1.a_star_algorithm('A', 'D')

​

And the output would look like:

Path found: ['A', 'B', 'D']

['A', 'B', 'D']

Thus, the optimal path from A to D, found using A*, is A->B->D. 

Q. What is AO* algorithm?

A.

The AO* algorithm is a knowledge-based search technique, meaning the start state and the goal state is already defined , and the best path is found using heuristics. The time complexity of the algorithm is significantly reduced due to the informed search technique.

​

Q. Represent And Or graph in python.

A. 

​

Q. Code of AO* in python.

A.

Implement AO* Search algorithm.

​

AO* Algorithm Code:

​

def recAOStar(n):

    global finalPath

    print("Expanding Node:",n)

    and_nodes = []

    or_nodes =[]

    if(n in allNodes):

        if 'AND' in allNodes[n]:

            and_nodes = allNodes[n]['AND']

        if 'OR' in allNodes[n]:

            or_nodes = allNodes[n]['OR']

    if len(and_nodes)==0 and len(or_nodes)==0:

        return

    solvable = False

    marked ={}

    while not solvable:

        if len(marked)==len(and_nodes)+len(or_nodes):

            min_cost_least,min_cost_group_least = least_cost_group(and_nodes,or_nodes,{})

            solvable = True

            change_heuristic(n,min_cost_least)

            optimal_child_group[n] = min_cost_group_least

            continue

        min_cost,min_cost_group = least_cost_group(and_nodes,or_nodes,marked)

        is_expanded = False

        if len(min_cost_group)>1:

            if(min_cost_group[0] in allNodes):

                is_expanded = True

                recAOStar(min_cost_group[0])

            if(min_cost_group[1] in allNodes):

                is_expanded = True

                recAOStar(min_cost_group[1])

        else:

            if(min_cost_group in allNodes):

                is_expanded = True

                recAOStar(min_cost_group)

        if is_expanded:

            min_cost_verify, min_cost_group_verify = least_cost_group(and_nodes, or_nodes, {})

            if min_cost_group == min_cost_group_verify:

                solvable = True

                change_heuristic(n, min_cost_verify)

                optimal_child_group[n] = min_cost_group

        else:

            solvable = True

            change_heuristic(n, min_cost)

            optimal_child_group[n] = min_cost_group

        marked[min_cost_group]=1

    return heuristic(n)

def least_cost_group(and_nodes, or_nodes, marked):

    node_wise_cost = {}

    for node_pair in and_nodes:

        if not node_pair[0] + node_pair[1] in marked:

            cost = 0

            cost = cost + heuristic(node_pair[0]) + heuristic(node_pair[1]) + 2

            node_wise_cost[node_pair[0] + node_pair[1]] = cost

    for node in or_nodes:

        if not node in marked:

            cost = 0

            cost = cost + heuristic(node) + 1

            node_wise_cost[node] = cost

    min_cost = 999999

    min_cost_group = None

    for costKey in node_wise_cost:

        if node_wise_cost[costKey] < min_cost:

            min_cost = node_wise_cost[costKey]

            min_cost_group = costKey

    return [min_cost, min_cost_group]

def heuristic(n):

    return H_dist[n]

def change_heuristic(n, cost):

    H_dist[n] = cost

    return

def print_path(node):

    print(optimal_child_group[node], end="")

    node = optimal_child_group[node]

    if len(node) > 1:

        if node[0] in optimal_child_group:

            print("->", end="")

            print_path(node[0])

        if node[1] in optimal_child_group:

            print("->", end="")

            print_path(node[1])

    else:

        if node in optimal_child_group:

            print("->", end="")

            print_path(node)

H_dist = {

 'A': -1,

 'B': 4,

 'C': 2,

 'D': 3,

 'E': 6,

 'F': 8,

 'G': 2,

 'H': 0,

 'I': 0,

 'J': 0

}

allNodes = {

 'A': {'AND': [('C', 'D')], 'OR': ['B']},

 'B': {'OR': ['E', 'F']},

 'C': {'OR': ['G'], 'AND': [('H', 'I')]},

 'D': {'OR': ['J']}

}

optimal_child_group = {}

optimal_cost = recAOStar('A')

print('Nodes which gives optimal cost are')

print_path('A')

print('\nOptimal Cost is :: ', optimal_cost)

Output

​

Expanding Node: A

Expanding Node: B

Expanding Node: C

Expanding Node: D

Nodes which gives optimal cost are

CD->HI->J

Optimal Cost is ::  5

​

​

​