Program on informed search method.

Implementation of A Star Search Algorithm in python – Artificial Intelligence

In this tutorial, we will understand the A Star Search Algorithm with a solved numerical example and implementation in python.

A Star Solved Numerical Example:

Numbers written on edges represent the distance between nodes. Numbers written on nodes represent the heuristic value.

Given the graph, find the cost-effective path from A to G. That is A is the source node and G is the goal node.

Now from A, we can go to point B or E, so we compute f(x) for each of them,

A → B = g(B) + h(B) = 2 + 6 = 8

A → E = g(E) + h(E) = 3 + 7 = 10

Since the cost for A → B is less, we move forward with this path and compute the f(x) for the children nodes of B.

Now from B, we can go to point C or G, so we compute f(x) for each of them,

A → B → C = (2 + 1) + 99= 102

A → B → G = (2 + 9 ) + 0 = 11

Here the path A → B → G has the least cost but it is still more than the cost of A → E, thus we explore this path further.

Now from E, we can go to point D, so we compute f(x),

A → E → D = (3 + 6) + 1 = 10

Comparing the cost of A → E → D with all the paths we got so far and as this cost is least of all we move forward with this path.

Now compute the f(x) for the children of D

A → E → D → G = (3 + 6 + 1) +0 = 10

Now comparing all the paths that lead us to the goal, we conclude that A → E → D → G is the most cost-effective path to get from A to G.

Implementation of A Star Search Algorithm in python:

def aStarAlgo(start_node, stop_node):
    open_set = set(start_node)
    closed_set = set()
    g = {}               #store distance from starting node
    parents = {}         # parents contains an adjacency map of all nodes
    #distance of starting node from itself is zero
    g[start_node] = 0
    #start_node is root node i.e it has no parent nodes
    #so start_node is set to its own parent node
    parents[start_node] = start_node
    while len(open_set) > 0:
        n = None
        #node with lowest f() is found
        for v in open_set:
            if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
                n = v
        if n == stop_node or Graph_nodes[n] == None:
            pass
        else:
            for (m, weight) in get_neighbors(n):
                #nodes 'm' not in first and last set are added to first
                #n is set its parent
                if m not in open_set and m not in closed_set:
                    open_set.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight
                #for each node m,compare its distance from start i.e g(m) to the
                #from start through n node
                else:
                    if g[m] > g[n] + weight:
                        #update g(m)
                        g[m] = g[n] + weight
                        #change parent of m to n
                        parents[m] = n
                        #if m in closed set,remove and add to open
                        if m in closed_set:
                            closed_set.remove(m)
                            open_set.add(m)
        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:
            path = []
            while parents[n] != n:
                path.append(n)
                n = parents[n]
            path.append(start_node)
            path.reverse()
            print('Path found: {}'.format(path))
            return path
        # remove n from the open_list, and add it to closed_list
        # because all of his neighbors were inspected
        open_set.remove(n)
        closed_set.add(n)
    print('Path does not exist!')
    return None

#define fuction to return neighbor and its distance
#from the passed node
def get_neighbors(v):
    if v in Graph_nodes:
        return Graph_nodes[v]
    else:
        return None
#A star example 1
#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes
def heuristic(n):
    H_dist = {
        'A': 11,
        'B': 6,
        'C': 5,
        'D': 7,
        'E': 3,
        'F': 6,
        'G': 5,
        'H': 3,
        'I': 1,
        'J': 0
    }
    return H_dist[n]

#Describe your graph here
Graph_nodes = {
    'A': [('B', 6), ('F', 3)],
    'B': [('A', 6), ('C', 3), ('D', 2)],
    'C': [('B', 3), ('D', 1), ('E', 5)],
    'D': [('B', 2), ('C', 1), ('E', 8)],
    'E': [('C', 5), ('D', 8), ('I', 5), ('J', 5)],
    'F': [('A', 3), ('G', 1), ('H', 7)],
    'G': [('F', 1), ('I', 3)],
    'H': [('F', 7), ('I', 2)],
    'I': [('E', 5), ('G', 3), ('H', 2), ('J', 3)],
}

aStarAlgo('A', 'J')
#Output:
#Path found: ['A', 'F', 'G', 'I', 'J']

#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes
def heuristic(n):
    H_dist = {
        'A': 11,
        'B': 6,
        'C': 99,
        'D': 1,
        'E': 7,
        'G': 0,
    }
    return H_dist[n]

#Describe your graph here
Graph_nodes = {
    'A': [('B', 2), ('E', 3)],
    'B': [('A', 2), ('C', 1), ('G', 9)],
    'C': [('B', 1)],
    'D': [('E', 6), ('G', 1)],
    'E': [('A', 3), ('D', 6)],
    'G': [('B', 9), ('D', 1)]
}

aStarAlgo('A', 'G')

Output:

Hill-Climbing in Python– Artificial Intelligence

In hill climbing the basic idea is to always head towards a state which is better than the current one.

So, if you are in town A and you can get to town B and town C (and your target is town D) then you should make a move IF town B or C appear nearer to town D than town A does.

Hill-CLimbing Search Algorithm

1. Evaluate the initial state. 
   If it is also goal state then return it, otherwise continue with the initial state as the current state.

2. Loop until the solution is found or until there are no new operators to be applied in the current state    
   
   a) Select an operator that has not yet been applied to the current state and apply it to produce new state 
  
   b) Evaluate the new state
      i)    If it is a goal state then return it and quit
      ii)   If it is not a goal state but it is better than the current state, then make it as current state
      iii)  If it is not better than the current state, then continue in loop.

Travelling salesman problem

First, let’s code an instantiation of the Travelling salesman problem. If you think about it, such an instantiation should be a list of cities, where each one has information about the distances from there to the other cities. Of course, the distance from each city to itself is zero, and the distance from city A to city B is the same as the distance from city B to city A. That gives us a list, containing n lists of size n (where in this case n equals 4):

tsp = [
	[0, 400, 500, 300],
	[400, 0, 300, 500],
	[500, 300, 0, 400],
	[300, 500, 400, 0]
	] Python Code: import random def randomSolution(tsp): cities = list(range(len(tsp))) solution = [] for i in range(len(tsp)): randomCity = cities[random.randint(0, len(cities) - 1)] solution.append(randomCity) cities.remove(randomCity) return solution def routeLength(tsp, solution): routeLength = 0 for i in range(len(solution)): routeLength += tsp[solution[i - 1]][solution[i]] return routeLength def getNeighbours(solution): neighbours = [] for i in range(len(solution)): for j in range(i + 1, len(solution)): neighbour = solution.copy() neighbour[i] = solution[j] neighbour[j] = solution[i] neighbours.append(neighbour) return neighbours def getBestNeighbour(tsp, neighbours): bestRouteLength = routeLength(tsp, neighbours[0]) bestNeighbour = neighbours[0] for neighbour in neighbours: currentRouteLength = routeLength(tsp, neighbour) if currentRouteLength < bestRouteLength: bestRouteLength = currentRouteLength bestNeighbour = neighbour return bestNeighbour, bestRouteLength def hillClimbing(tsp): currentSolution = randomSolution(tsp) currentRouteLength = routeLength(tsp, currentSolution) neighbours = getNeighbours(currentSolution) bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours) while bestNeighbourRouteLength < currentRouteLength: currentSolution = bestNeighbour currentRouteLength = bestNeighbourRouteLength neighbours = getNeighbours(currentSolution) bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours) return currentSolution, currentRouteLength def main(): tsp = [ [0, 400, 500, 300], [400, 0, 300, 500], [500, 300, 0, 400], [300, 500, 400, 0] ] print(hillClimbing(tsp)) if __name__ == "__main__": main() Output: