AI Programs

                                       IMPLEMENT A* SEARCH ALGORITHM.

class Node():

    def __init__(self, parent=None, position=None):

        self.parent = parent

        self.position = position

        self.g = 0

        self.h = 0

        self.f = 0

    def __eq__(self, other):

        return self.position == other.position

def astar(maze, start, end):

    start_node = Node(None, start)

    start_node.g = start_node.h = start_node.f = 0

    end_node = Node(None, end)

    end_node.g = end_node.h = end_node.f = 0

    open_list = []

    closed_list = []

    open_list.append(start_node)

    while len(open_list) > 0:

        current_node = open_list[0]

        current_index = 0

        for index, item in enumerate(open_list):

            if item.f < current_node.f:

                current_node = item

                current_index = index

        open_list.pop(current_index)

        closed_list.append(current_node)

        if current_node == end_node:

            path = []

            current = current_node

            while current is not None:

                path.append(current.position)

                current = current.parent

            return path[::-1]

        children = []

        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:

            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (

                    len(maze[len(maze) - 1]) - 1) or node_position[1] < 0:

                continue

            if maze[node_position[0]][node_position[1]] != 0:

                continue

            new_node = Node(current_node, node_position)

            children.append(new_node)

        for child in children:

            for closed_child in closed_list:

                if child == closed_child:

                    continue

            child.g = current_node.g + 1

            child.h = ((child.position[0] - end_node.position[0]) ** 2) + (

                    (child.position[1] - end_node.position[1]) ** 2)

            child.f = child.g + child.h

            for open_node in open_list:

                if child == open_node and child.g > open_node.g:

                    continue

            open_list.append(child)

def main():

    maze = [[0, 0, 0, 0, 1, 0],

            [0, 0, 0, 0, 1, 0],

            [0, 0, 0, 0, 1, 0],

            [0, 0, 0, 0, 1, 0],

            [0, 0, 0, 0, 1, 0],

            [0, 0, 0, 0, 0, 0]]

    graph = [[0, 1, 0, 0, 0, 0],

             [1, 0, 1, 0, 1, 0],

             [0, 1, 0, 0, 0, 1],

             [0, 0, 0, 0, 1, 0],

             [0, 1, 0, 1, 0, 0],

             [0, 0, 1, 0, 0, 0]]

    start = (0, 0)

    end = (5, 5)

    end1 = (5, 5)

    path = astar(maze, start, end)

    print("path",path)

    path1 = astar(graph, start, end1)

    print("path1",path1)

if __name__ == '__main__':

    main()

           Output of A Star Search Algorithm

              path [(0,0),(1,1),(2,2),(3,3),(4.3),(5,4),(5,5)]

                   Path1 [(0,0),(1,1),(2,2),(3,3),(4,4),(5,5)]

-----------------------------------------------------------------------------------------------------------------------------

                                         IMPLEMENT AO* SEARCH ALGORITHM.

class Graph:

    def __init__(self, graph, heuristicNodeList, startNode): #instantiate graph object with graph topology, heuristic values, start node

        self.graph = graph

        self.H=heuristicNodeList

        self.start=startNode

        self.parent={}

        self.status={}

        self.solutionGraph={}

    def applyAOStar(self): # starts a recursive AO* algorithm

        self.aoStar(self.start, False)

    def getNeighbors(self, v): # gets the Neighbors of a given node

        return self.graph.get(v,'')

    def getStatus(self,v): # return the status of a given node

        return self.status.get(v,0)

    def setStatus(self,v, val): # set the status of a given node

        self.status[v]=val

    def getHeuristicNodeValue(self, n):

        return self.H.get(n,0) # always return the heuristic value of a given node

    def setHeuristicNodeValue(self, n, value):

        self.H[n]=value # set the revised heuristic value of a given node

    def printSolution(self):

        print("FOR GRAPH SOLUTION, TRAVERSE THE GRAPH FROM THE START NODE:",self.start)

        print("------------------------------------------------------------")

        print(self.solutionGraph)

        print("------------------------------------------------------------")

    def computeMinimumCostChildNodes(self, v): # Computes the Minimum Cost of child nodes of a given node v

        minimumCost=0

        costToChildNodeListDict={}

        costToChildNodeListDict[minimumCost]=[]

        flag=True

        for nodeInfoTupleList in self.getNeighbors(v): # iterate over all the set of child node/s

            cost=0

            nodeList=[]

            for c, weight in nodeInfoTupleList:

                cost=cost+self.getHeuristicNodeValue(c)+weight

                nodeList.append(c)

            if flag==True: # initialize Minimum Cost with the cost of first set of child node/s

                minimumCost=cost

                costToChildNodeListDict[minimumCost]=nodeList # set the Minimum Cost child node/s

                flag=False

            else: # checking the Minimum Cost nodes with the current Minimum Cost

                if minimumCost>cost:

                    minimumCost=cost

                    costToChildNodeListDict[minimumCost]=nodeList # set the Minimum Cost child node/s

        return minimumCost, costToChildNodeListDict[minimumCost] # return Minimum Cost and Minimum Cost child node/s

    def aoStar(self, v, backTracking): # AO* algorithm for a start node and backTracking status flag

        print("HEURISTIC VALUES :", self.H)

        print("SOLUTION GRAPH :", self.solutionGraph)

        print("PROCESSING NODE :", v)

        print("-----------------------------------------------------------------------------------------")

        if self.getStatus(v) >= 0: # if status node v >= 0, compute Minimum Cost nodes of v

            minimumCost, childNodeList = self.computeMinimumCostChildNodes(v)

            print(minimumCost, childNodeList)

            self.setHeuristicNodeValue(v, minimumCost)

            self.setStatus(v,len(childNodeList))

            solved=True # check the Minimum Cost nodes of v are solved

            for childNode in childNodeList:

                self.parent[childNode]=v

                if self.getStatus(childNode)!=-1:

                    solved=solved & False

            if solved==True: # if the Minimum Cost nodes of v are solved, set the current node status as solved(-1)

                self.setStatus(v,-1)

                self.solutionGraph[v]=childNodeList # update the solution graph with the solved nodes which may be a part of solution

            if v!=self.start: # check the current node is the start node for backtracking the current node value

                self.aoStar(self.parent[v], True) # backtracking the current node value with backtracking status set to true

            if backTracking==False: # check the current call is not for backtracking

                for childNode in childNodeList: # for each Minimum Cost child node

                    self.setStatus(childNode,0) # set the status of child node to 0(needs exploration)

                    self.aoStar(childNode, False) # Minimum Cost child node is further explored with backtracking status as false

#for simplicity we ll consider heuristic distances given

print ("Graph - 1")

h1 = {'A': 1, 'B': 6, 'C': 2, 'D': 12, 'E': 2, 'F': 1, 'G': 5, 'H': 7, 'I': 7, 'J': 1}

graph1 = {

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

    'B': [[('G', 1)], [('H', 1)]],

    'C': [[('J', 1)]],

    'D': [[('E', 1), ('F', 1)]],

    'G': [[('I', 1)]]

}

G1= Graph(graph1, h1, 'A')

G1.applyAOStar()

G1.printSolution()

                     Output of AO Star Search Algorithm

HEURISTIC VALUES : {‘A’: 1, ‘B’: 6, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 5, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : A

10 [‘B’, ‘C’]
HEURISTIC VALUES : {‘A’: 10, ‘B’: 6, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 5, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : B

6 [‘G’]
HEURISTIC VALUES : {‘A’: 10, ‘B’: 6, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 5, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : A

10 [‘B’, ‘C’]
HEURISTIC VALUES : {‘A’: 10, ‘B’: 6, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 5, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : G

8 [‘I’]
HEURISTIC VALUES : {‘A’: 10, ‘B’: 6, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 8, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : B

8 [‘H’]
HEURISTIC VALUES : {‘A’: 10, ‘B’: 8, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 8, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : A

12 [‘B’, ‘C’]
HEURISTIC VALUES : {‘A’: 12, ‘B’: 8, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 8, ‘H’: 7, ‘I’: 7, ‘J’: 1}
SOLUTION GRAPH : {}

PROCESSING NODE : I

0 []
HEURISTIC VALUES : {‘A’: 12, ‘B’: 8, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 8, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: []}

PROCESSING NODE : G

1 [‘I’]
HEURISTIC VALUES : {‘A’: 12, ‘B’: 8, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’]}

PROCESSING NODE : B

2 [‘G’]
HEURISTIC VALUES : {‘A’: 12, ‘B’: 2, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’]}

PROCESSING NODE : A

6 [‘B’, ‘C’]
HEURISTIC VALUES : {‘A’: 6, ‘B’: 2, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’]}

PROCESSING NODE : C

2 [‘J’]
HEURISTIC VALUES : {‘A’: 6, ‘B’: 2, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’]}

PROCESSING NODE : A

6 [‘B’, ‘C’]
HEURISTIC VALUES : {‘A’: 6, ‘B’: 2, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 1}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’]}

PROCESSING NODE : J

0 []
HEURISTIC VALUES : {‘A’: 6, ‘B’: 2, ‘C’: 2, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 0}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’], ‘J’: []}

PROCESSING NODE : C

1 [‘J’]
HEURISTIC VALUES : {‘A’: 6, ‘B’: 2, ‘C’: 1, ‘D’: 12, ‘E’: 2, ‘F’: 1, ‘G’: 1, ‘H’: 7, ‘I’: 0, ‘J’: 0}
SOLUTION GRAPH : {‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’], ‘J’: [], ‘C’: [‘J’]}

PROCESSING NODE : A

5 [‘B’, ‘C’]

FOR GRAPH SOLUTION, TRAVERSE THE GRAPH FROM THE START NODE: A

{‘I’: [], ‘G’: [‘I’], ‘B’: [‘G’], ‘J’: [], ‘C’: [‘J’], ‘A’: [‘B’, ‘C’]}

Comments

Post a Comment

Popular posts from this blog

ML programs

Image
1.Implement and demonstrate FIND-S alorithm for finding the mot spcific hypotheis based on a given set of training data samples. Read the training data from a .CSV file. import csv with open('C:/xampp/htdocs/girish/PlayTennis.csv', 'r') as f:     reader = csv.reader(f)     your_list = list(reader)     h = [['0', '0', '0', '0', '0', '0']]     for i in your_list:         print(i)         if i[-1] == "True":             j = 0             for x in i:                 if x != "True":                     if x != h[0][j] and h[0][j] == '0':                         h[0][j] = x                     elif x != h[0][j] and h[0] * [j] != '0':                         h[0][j] = '?'                     else:                         pass                     j = j + 1 print("Most specific hypothesis is") print(h) output: ['Outlook', 'Temperature', 'Humidity', 'W
Read more

big data 8

                                                                             PRACTICAL NO – 8 Aim: Implementing Clustering Algorithm Using Map-Reduce   Algorithm for Mapper Input: A set of objects X = {x1, x2… xn}, A Set ofinitial Centroids C = {c1, c2, ,ck} Output: An output list which contains pairs of (Ci, xj)where 1 ≤ i≤ n and 1 ≤j ≤ k Procedure M1←{x1, x2… xm} current_centroids←C Distance (p, q) =√Σd i=1 (pi– qi) 2 (where pi (or qi)is the coordinate of p (or q) in dimension i) for all xi ϵ M1 such that 1≤i≤m do bestCentroid←null minDist←∞ for all c ϵ current_centroids do       emit (bestCentroid, xi) i+=1   dist← distance (xi, c) if (bestCentroid = null || dist<minDist) then minDist←dist bestCentroid ← c end if end for     end for return Outputlist   Algorithm for Reducer Input: (Key, Value), where key = bestCentroid and Value =Objects assigned to the lpgr'; 1\] x centroid by the mapper Output:
Read more

big data 6

                                                          PRACTICAL NO – 6 Aim: Implementing Bloom Filter using Map-Reduce. 1.                  import java.io.DataOutputStream; 2.                  import java.io.FileOutputStream; 3.                  import java.io.IOException; 4.                  import org.apache.hadoop.util.bloom.BloomFilter; 5.                  import org.apache.hadoop.util.bloom.Key; 6.                  import org.apache.hadoop.util.hash.Hash; 7. 8.                  public class DepartmentBloomFilterTrainer { 9.                  public static int getBloomFilterOptimalSize (int numElements, float falsePosRate) { 10.         return (int) (-numElements * (float) Math.log(falsePosRate) / Math.pow(Math.log(2), 2)); 11. } 12.         public static int getOptimalK (float numElements, float vectorSize) { 13.         return (int) Math.round(vectorSize * Math.log(2) / numElements); 14. } 15.         public static void main (String[]
Read more