Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #AI ALGORISMS
- #1-BFS
- #declaring the graph as a dictionary
- graph = {
- 'S' : [ 'A','B','D'],
- 'A' : ['C'],
- 'B' : ['D'],
- 'C' : ['D','G'],
- 'D' : ['G'],
- 'G' : []
- }
- def bfs(graph, start, goal):
- #create a list to store the visited nodes and a queue to store the nodes
- visited = []
- queue = [[start]]
- #loop through the queue if it's not empty
- while queue:
- path = queue.pop(0) #remove from the left
- node = path[-1]
- if node == visited:
- continue
- visited.append(node)
- if node == goal:
- return path
- else:
- adjacent_nodes = graph.get(node, [])
- for adjacent_node in adjacent_nodes:
- new_path = path.copy()
- new_path.append(adjacent_node)
- queue.append(new_path)
- return print("The queue is empty, no solution found.")
- solution = bfs(graph,'S','G')
- print('Solution is ' , solution)
- #2-DFS
- #declaring the graph as a dictionary
- graph = {
- 'S' : [ 'A','B','D'],
- 'A' : ['C'],
- 'B' : ['D'],
- 'C' : ['D','G'],
- 'D' : ['G'],
- 'G' : []
- }
- def dfs(graph, start, goal):
- #create a list to store the visited nodes and a stack to store the nodes
- visited = []
- stack = [[start]]
- #loop through the stack if it's not empty
- while stack:
- path = stack.pop() #remove from the right
- node = path[-1]
- if node == visited:
- continue
- visited.append(node)
- if node == goal:
- return path
- else:
- adjacent_nodes = graph.get(node, [])
- for adjacent_node in adjacent_nodes:
- new_path = path.copy()
- new_path.append(adjacent_node)
- stack.append(new_path)
- return print("The stack is empty, no path found.")
- solution = dfs(graph,'S','G')
- print('Solution is ' , solution)
- #3-AlphaBeta
- import math
- def alpha_beta_minimax(cd, node, alpha, beta, maxt, scr, td):
- if cd == td:
- return scr[node]
- if maxt:
- v = -math.inf
- for child in [node*2, node*2+1]:
- v = max(v, alpha_beta_minimax(cd+1, child, alpha, beta, False, scr, td))
- alpha = max(alpha, v)
- if alpha >= beta:
- break
- return v
- else:
- v = math.inf
- for child in [node*2, node*2+1]:
- v = min(v, alpha_beta_minimax(cd+1, child, alpha, beta, True, scr, td))
- beta = min(beta, v)
- if alpha >= beta:
- break
- return v
- scr = []
- x = int(input('Enter Total Number of leaf nodes: '))
- for i in range(x):
- y = int(input('Enter leaf value: '))
- scr.append(y)
- td = math.log(len(scr), 2)
- cd = int(input('Enter current depth value: '))
- nodev = int(input('Enter node value: '))
- alpha = -math.inf
- beta = math.inf
- maxt = True
- answer = alpha_beta_minimax(cd, nodev, alpha, beta, maxt, scr, td)
- print('The answer is: ',answer)
- #4-GBS
- #NOTE that Gready_best_search depends on H_cost only
- graph={
- 'S':[('A',1),('B',4)],
- 'A':[('B',2),('C',5),('G',12)],
- 'B':[('C',2)],
- 'C':[('G',3)]
- }
- # The hurestic of each node
- H_table={
- 'S':7,
- 'A':6,
- 'B':4,
- 'C':2,
- 'G':0
- }
- #To calculate the H_cost of any path
- def path_h_cost(path):
- for (node,cost) in path:
- last_node = path[-1][0] #C
- h_cost = H_table[last_node] #2
- return h_cost , last_node
- #to check the path_h_cost function
- # path=[('S', 0), ('A', 1), ('C', 5)]
- # print(path_f_cost (path))
- #SOLUTION = (2 , C)
- def gready_best_search(graph, start, goal):
- visited=[]
- queue=[[(start,0)]]
- while queue:
- queue.sort(key=path_h_cost) #sorting by least f-cost
- path = queue.pop(0) #pop from left
- node = path[-1][0]
- if node in visited:
- continue
- visited.append(node)
- if node == goal:
- return path
- else:
- adjacent_nodes = graph.get(node,[])
- for (adjacent_node,cost) in adjacent_nodes:
- new_path =path.copy()
- new_path.append((adjacent_node, cost))
- queue.append(new_path)
- solution= gready_best_search(graph, 'S', 'G')
- print('Solution is : ', solution)
- solution_path = [node for (node,_) in solution] #_ to ignore the cost of nodes
- print('The path of Solution : ', solution_path)
- print('H_cost of solution is', path_h_cost(solution)[0])
- #5-A*
- #NOTE that a* depends on F_cost = G_cost + H_cost
- graph={
- 'S':[('A',1),('B',4)],
- 'A':[('B',2),('C',5),('G',12)],
- 'B':[('C',2)],
- 'C':[('G',3)]
- }
- # The hurestic of each node
- H_table={
- 'S':7,
- 'A':6,
- 'B':4,
- 'C':2,
- 'G':0
- }
- #To calculate the F_cost of any path
- def path_f_cost(path):
- g_cost= 0
- for (node,cost) in path:
- g_cost += cost
- last_node = path[-1][0] #C
- h_cost = H_table[last_node] #2
- f_cost = g_cost + h_cost
- return f_cost , last_node
- #to check the path_f_cost function
- # path=[('S', 0), ('A', 1), ('C', 5)]
- # print(path_f_cost (path))
- #SOLUTION = (8 , C)
- def a_star_search(graph, start, goal):
- visited=[]
- queue=[[(start,0)]]
- while queue:
- queue.sort(key=path_f_cost) #sorting by least f-cost
- path = queue.pop(0) #pop from left
- node = path[-1][0]
- if node in visited:
- continue
- visited.append(node)
- if node == goal:
- return path
- else:
- adjacent_nodes = graph.get(node,[])
- for (adjacent_node,cost) in adjacent_nodes:
- new_path =path.copy()
- new_path.append((adjacent_node, cost))
- queue.append(new_path)
- solution= a_star_search(graph, 'S', 'G')
- print('Solution is : ', solution)
- solution_path = [node for (node,_) in solution] #_ to ignore the cost of nodes
- print('The path of Solution : ', solution_path)
- print('F_cost of solution is', path_f_cost(solution)[0])
- #6-UCS
- #NOTE that Uniform_cost_search depends on G_cost of path
- #create a function to calculate path_cost
- def path_cost(path):
- total_cost = 0
- for (node , cost) in path:
- total_cost += cost
- return total_cost , path[-1][0]
- #declaring the graph as a dictionary with it's cost
- graph = {
- 'S' : [ ('A',2),('B',3),('D',5)],
- 'A' : [('C',4)],
- 'B' : [('D',4)],
- 'C' : [('D',1),('G',2)],
- 'D' : [('G',5)],
- 'G' : []
- }
- def ucs(graph, start, goal):
- #create a list to store the visited nodes and a queue to store the nodes
- visited = []
- queue = [[(start,0)]]
- #loop through the queue if it's not empty
- while queue:
- queue.sort(key=path_cost) #sorting by lowest path_cost
- path = queue.pop(0)
- node = path[-1][0]
- if node in visited:
- continue
- visited.append(node)
- if node == goal:
- return path
- else:
- adjacent_nodes = graph.get(node, [])
- for (adjacent_node,cost) in adjacent_nodes:
- new_path = path.copy()
- new_path.append((adjacent_node,cost))
- queue.append(new_path)
- return print("The queue is empty, no solution found.")
- solution = ucs(graph,'S','G')
- print('Solution is ' , solution)
- print('Cost of solution is ' , path_cost(solution)[0])
- #7-MinMax
- import math
- def Minmax(cd,node,maxt,scr,td):
- if(cd==td):
- return scr[node]
- if(maxt):
- return max(Minmax(cd+1,node*2,False,scr,td),Minmax(cd+1,node*2+1,False,scr,td))
- else:
- return min(Minmax(cd+1,node*2,True,scr,td),Minmax(cd+1,node*2+1,True,scr,td))
- scr=[]
- x=int(input('Enter Total Nymber of leaf node= '))
- for i in range (x):
- y=int(input('Enter leaf value: '))
- scr.append(y)
- td=math.log(len(scr),2)
- cd=int(input('Enter current depth value: '))
- nodev=int(input('Enter node value: '))
- maxt=True
- print('The answer is : ',end=" ")
- answer=Minmax(cd,nodev,maxt,scr,td)
- print(answer)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement