AI Algorithms and Programs

Download as pdf or txt
Download as pdf or txt
You are on page 1of 15

CONTENT

1. To implement A* algorithm

2. To implement AO* algorithm

3. To implement Breadth First Search

4. To implement Depth First Search

5. To implement Water Jug Problem

6. To implement Hill Climbing Algorithm

7. To implement MinMax Algorithm

8. 8. To implement predicate logic concepts using Python


(i) Some humans are intelligent
(ii) Sachin likes cricket
(iii) Ravi and Ajay are brothers
(iv) Chinky is a cat
A* ALGORITHM
Step 1. Initialization:

 Begin by initializing two sets: the open set and the closed set.
 The open set initially contains only the starting node, while the closed set is empty.
 Set the cost of reaching the starting node (g-score) to zero and calculate the heuristic cost
estimate to the goal (h-score) for the starting node.

Step 2. Main Loop:

 The main loop continues until one of two conditions is met:


 The goal node is reached, and the optimal path is found.
 The open set is empty, indicating that no path exists to the goal.

Step 3. Selecting the Node for Evaluation:

 At each iteration of the loop, select the node from the open set with the lowest f-score (f = g +
h).
 This node is the most promising candidate for evaluation, as it balances the actual cost incurred
(g) and the estimated remaining cost (h).

Step 4. Evaluating Neighbors:

 For the selected node, consider its neighboring nodes (also known as successors).
 Calculate the actual cost to reach each neighbor from the current node (g-score).
 Calculate the heuristic cost estimate from each neighbor to the goal (h-score).

Step 5. Updating Costs:

 For each neighbor, calculate the total estimated cost (f-score) by summing the actual cost (g-
score) and the heuristic estimate (h-score).
 If a neighbor is not in the open set, add it to the open set.
 If a neighbor is already in the open set and its f-score is lower than the previously recorded f-
score, update the neighbor's f-score and set its parent to the current node. This means a shorter
path to the neighbor has been discovered.

Step 6. Moving to the Next Node:

 After evaluating the neighbors of the current node, move the current node to the closed set,
indicating that it has been fully evaluated.
 Return to the main loop and select the next node for evaluation based on its f-score.

Step 7. Goal Reached or No Path Found:

 If the goal node is reached, the algorithm terminates, and the optimal path can be
reconstructed by backtracking from the goal node to the starting node using the parent
pointers.
 If the open set becomes empty without reaching the goal, the algorithm terminates with the
conclusion that no path exists.

Step 8. Path Reconstruction (Optional):

 Once the goal is reached, you can reconstruct the optimal path by following the parent pointers
from the goal node back to the starting node. This path represents the shortest route.
A* PROGRAM
AO* ALGORITHM
Like A* algorithm here we will use two arrays and one heuristic function.

OPEN: It contains the nodes that have been traversed but yet not been marked solvable or unsolvable.

CLOSE: It contains the nodes that have already been processed.

h(n): The distance from the current node to the goal node.

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

Step 1: Place the starting node into OPEN.

Step 2: Compute the most promising solution tree say T0.

Step 3: Select a node n that is both on OPEN and a member of T0. Remove it from OPEN and place it in
CLOSE

Step 4: If n is the terminal goal node then leveled n as solved and leveled all the ancestors of n as solved.
If the starting node is marked as solved then success and exit.

Step 5: If n is not a solvable node, then mark n as unsolvable. If starting node is marked as unsolvable,
then return failure and exit.

Step 6: Expand n. Find all its successors and find their h (n) value, push them into OPEN.

Step 7: Return to Step 2.

Step 8: Exit.

AO* PROGRAM
# Cost to find the AND and OR path
def Cost(H, condition, weight = 1):
cost = {}
if 'AND' in condition:
AND_nodes = condition['AND']
Path_A = ' AND '.join(AND_nodes)
PathA = sum(H[node]+weight for node in AND_nodes)
cost[Path_A] = PathA

if 'OR' in condition:
OR_nodes = condition['OR']
Path_B =' OR '.join(OR_nodes)
PathB = min(H[node]+weight for node in OR_nodes)
cost[Path_B] = PathB
return cost

# Update the cost


def update_cost(H, Conditions, weight=1):
Main_nodes = list(Conditions.keys())
Main_nodes.reverse()
least_cost= {}
for key in Main_nodes:
condition = Conditions[key]
print(key,':', Conditions[key],'>>>', Cost(H, condition, weight))
c = Cost(H, condition, weight)
H[key] = min(c.values())
least_cost[key] = Cost(H, condition, weight)
return least_cost

# Print the shortest path


def shortest_path(Start,Updated_cost, H):
Path = Start
if Start in Updated_cost.keys():
Min_cost = min(Updated_cost[Start].values())
key = list(Updated_cost[Start].keys())
values = list(Updated_cost[Start].values())
Index = values.index(Min_cost)

# FIND MINIMIMUM PATH KEY


Next = key[Index].split()
# ADD TO PATH FOR OR PATH
if len(Next) == 1:

Start =Next[0]
Path += '<--' +shortest_path(Start, Updated_cost, H)
# ADD TO PATH FOR AND PATH
else:
Path +='<--('+key[Index]+') '

Start = Next[0]
Path += '[' +shortest_path(Start, Updated_cost, H) + ' + '

Start = Next[-1]
Path += shortest_path(Start, Updated_cost, H) + ']'

return Path

H = {'A': -1, 'B': 5, 'C': 2, 'D': 4, 'E': 7, 'F': 9, 'G': 3, 'H': 0,


'I':0, 'J':0}

Conditions = {
'A': {'OR': ['B'], 'AND': ['C', 'D']},
'B': {'OR': ['E', 'F']},
'C': {'OR': ['G'], 'AND': ['H', 'I']},
'D': {'OR': ['J']}
}
# weight
weight = 1
# Updated cost
print('Updated Cost :')
Updated_cost = update_cost(H, Conditions, weight=1)
print('*'*75)
print('Shortest Path :\n',shortest_path('A', Updated_cost,H))
BREADTH FIRST SEARCH ALGORITHM
Breadth-First Search uses a queue data structure technique to store the vertices. And the queue follows
the First In First Out (FIFO) principle, which means that the neighbors of the node will be displayed,
beginning with the node that was put first.

The transverse of the BFS algorithm is approaching the nodes in two ways.

 Visited node
 Not visited node

The steps involved in the BFS algorithm to explore a graph are given as follows –

Step 1: Start with the source node.

Step 2: Add that node at the front of the queue to the visited list.

Step 3: Make a list of the nodes as visited that are close to that vertex

Step 4: And dequeue the nodes once they are visited.

Step 5: Repeat the actions until the queue is empty.

Step 6: Exit

BREADTH FIRST SEARCH PROGRAM

graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}

visited = [] # List for visited nodes.


queue =[] #Initialize a queue

def bfs(visited, graph, node): #function for BFS


visited.append(node)
queue.append(node)

while queue: # Creating loop to visit each node


m =queue.pop(0)
print (m, end =" ")

for neighbour in graph[m]:


if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5') # function calling
DEPTH FIRST SEARCH ALGORITHM
The outcome of a DFS traversal of a graph is a spanning tree. A spanning tree is a graph that is devoid of
loops. To implement DFS traversal, you need to utilize a stack data structure with a maximum size equal
to the total number of vertices in the graph.

To implement DFS traversal, you need to take the following stages.

Step 1: Create a stack with the total number of vertices in the graph as the size.

Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and add it to the
stack.

Step 3: Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.

Step 4: Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the
stack.

Step 5: If there are no new vertices to visit, go back and pop one from the stack using backtracking.

Step 6: Continue using steps 3, 4, and 5 until the stack is empty.

Step 7: When the stack is entirely unoccupied, create the final spanning tree by deleting the graph's
unused edges.

DEPTH FIRST SEARCH PROGRAM


# Using a Python dictionary to act as an adjacency list

graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs


if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')
WATER JUG PROBLEM ALGORITHM
Step 1. Initialize two variables j1 and j2 to represent the current amount of water in each jug.

Step 2. Set a target amount of water to measure out.

Step 3. Create a list of possible actions, including filling a jug, emptying a jug, and pouring water from
one jug to the other.

Step 4. Create an empty set to keep track of visited states.

Step 5. Create a stack to keep track of states to visit, and add the initial state to the stack.

Step 6. While the stack is not empty:

 Pop the top state from the stack.


 If this state has not been visited before, add it to the visited set.
 Check if the state matches the target amount of water. If so, return the seq actions taken to get
to this state.
 If the state does not match the target amount, generate all possible next states from this state
by applying each of the possible actions in turn.
 If it has not been visited before, add it to the stack for each next state.

Step 7. If the stack becomes empty without finding a solution, return None.

WATER JUG PROBLEM PROGRAM

# This function is used to initialize the


# dictionary elements with a default value.
from collections import defaultdict

# jug1 and jug2 contain the value


# for max capacity in respective jugs
# and aim is the amount of water to be measured.
jug1, jug2, aim = 4, 3, 2

# Initialize dictionary with


# default value as false.
visited = defaultdict(lambda: False)

# Recursive function which prints the


# intermediate steps to reach the final
# solution and return boolean value
# (True if solution is possible, otherwise False).
# amt1 and amt2 are the amount of water present
# in both jugs at a certain point of time.
def waterJugSolver(amt1, amt2):

# Checks for our goal and


# returns true if achieved.
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True

# Checks if we have already visited the


# combination or not. If not, then it proceeds further.
if visited[(amt1, amt2)] == False:
print(amt1, amt2)

# Changes the boolean value of


# the combination as it is visited.
visited[(amt1, amt2)] = True

# Check for all the 6 possibilities and


# see if a solution is found in any one of them.
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))

# Return False if the combination is


# already visited to avoid repetition otherwise
# recursion will enter an infinite loop.
else:
return False

print("Steps: ")

# Call the function and pass the


# initial amount of water present in both jugs.
waterJugSolver(0, 0)

Output:

Steps:
0 0
4 0
4 3
0 3
3 0
3 3
4 2
0 2
HILL CLIMBING ALGORITHM
Simple hill climbing is the simplest way to implement a hill climbing algorithm. It only evaluates the
neighbor node state at a time and selects the first one which optimizes current cost and set it as a current
state. It only checks it's one successor state, and if it finds better than the current state, then move else
be in the same state. This algorithm has the following features:

 Less time consuming


 Less optimal solution and the solution is not guaranteed

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

Step 1: Evaluate the initial state, if it is goal state then return success and Stop.

Step 2: Loop Until a solution is found or there is no new operator left to apply.

Step 3: Select and apply an operator to the current state.

Step 4: Check new state:

 If it is goal state, then return success and quit.


 Else if it is better than the current state then assign new state as a current state.
 Else if not better than the current state, then return to step2.

Step 5: Exit.

HILL CLIMBING ALGORITHM PROGRAM


import random
import numpy as np
import networkx as nx

#coordinate of the points/cities


coordinate = np.array([[1,2], [30,21], [56,23], [8,18], [20,50], [3,4],
[11,6], [6,7], [15,20], [10,9], [12,12]])

#adjacency matrix for a weighted graph based on the given coordinates


def generate_matrix(coordinate):
matrix = []
for i in range(len(coordinate)):
for j in range(len(coordinate)) :
p = np.linalg.norm(coordinate[i] - coordinate[j])
matrix.append(p)
matrix = np.reshape(matrix, (len(coordinate),len(coordinate)))
#print(matrix)
return matrix

#finds a random solution


def solution(matrix):
points = list(range(0, len(matrix)))
solution = []
for i in range(0, len(matrix)):
random_point = points[random.randint(0, len(points) - 1)]
solution.append(random_point)
points.remove(random_point)
return solution
#calculate the path based on the random solution
def path_length(matrix, solution):
cycle_length = 0
for i in range(0, len(solution)):
cycle_length += matrix[solution[i]][solution[i - 1]]
return cycle_length

#generate neighbors of the random solution by swapping cities and returns the
best neighbor
def neighbors(matrix, solution):
neighbors = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbor = solution.copy()
neighbor[i] = solution[j]
neighbor[j] = solution[i]
neighbors.append(neighbor)

#assume that the first neighbor in the list is the best neighbor
best_neighbor = neighbors[0]
best_path = path_length(matrix, best_neighbor)

#check if there is a better neighbor


for neighbor in neighbors:
current_path = path_length(matrix, neighbor)
if current_path < best_path:
best_path = current_path
best_neighbor = neighbor
return best_neighbor, best_path

def hill_climbing(coordinate):
matrix = generate_matrix(coordinate)

current_solution = solution(matrix)
current_path = path_length(matrix, current_solution)
neighbor = neighbors(matrix,current_solution)[0]
best_neighbor, best_neighbor_path = neighbors(matrix, neighbor)

while best_neighbor_path < current_path:


current_solution = best_neighbor
current_path = best_neighbor_path
neighbor = neighbors(matrix, current_solution)[0]
best_neighbor, best_neighbor_path = neighbors(matrix, neighbor)

return current_path, current_solution


final_solution = hill_climbing(coordinate)
print("The solution is \n", final_solution[1])

OUTPUT
The solution is

[2, 4, 8, 3, 7, 5, 0, 6, 9, 10, 1]
MINMAX ALGORITHM
The Minimax Algorithm forms a tree-like structure through recursion, where the two players, Min and
Max take the following steps to reach the final goal state of the game.

Step 1. Prepare the complete Game Tree.

Step 2. Evaluate the score of each branch, using the evaluation function.

Step 3. Back-up score from the nodes to the root by:

 Selecting the child node with a maximum score for Max player.
 Selecting the child node with the minimum score for Min player.
 It is based on these values/scores that the quality (good or bad) of the move is decided.

Step 4. At the root node, the node with the max value is selected and the corresponding move is
performed.

Throughout the process, the aim is to minimize the maximum loss or the worst case scenario and get the
best solution for successful game playing

MIN-MAX Algorithm PROGRAM


# A simple Python3 program to find
# maximum score that
# maximizing player can get
import math

def minimax (curDepth, nodeIndex, maxTurn, scores, targetDepth):

# base case : target Depth reached


if (curDepth == targetDepth):
return scores[nodeIndex]

if (maxTurn):
return max(minimax(curDepth + 1, nodeIndex * 2,
False, scores, targetDepth),
minimax(curDepth + 1, nodeIndex * 2 + 1,
False, scores, targetDepth))

else:
return min(minimax(curDepth + 1, nodeIndex * 2,
True, scores, targetDepth),
minimax(curDepth + 1, nodeIndex * 2 + 1,
True, scores, targetDepth))

# Driver code
scores = [3, 5, 2, 9, 12, 5, 23, 23]

treeDepth = math.log(len(scores), 2)

print("The optimal value is : ", end = "")


print(minimax(0, 0, True, scores, treeDepth))

# This code is contributed


# by rootshadow

You might also like