Important concepts for AI

revise.py

#BFS
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph=defaultdict(list)

    def add_edge(self, u , v):
        self.graph[u].append(v)
        self.graph[v].append(u)

def bfs (graph, start):
    visited= [False] * (max(graph.keys())+1)
    queue = [start]
    visited[start] = True

    while queue:
        node = queue.pop(0)
        print(node, end=' ')
        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor]=True

g=Graph()
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,2)
g.add_edge(2,0)
g.add_edge(2,3)
g.add_edge(3,3)

print("\nBFS:")
bfs(g.graph,2)


#DFS
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph=defaultdict(list)
    def add_edge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
 
def dfs(graph, start, visited):
    if not visited[start]:
        print(start,end=' ')
        visited[start]=True
        for neighbor in graph[start]:
            dfs(graph, neighbor, visited)
    
g=Graph()
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,3)
g.add_edge(2,0)

print("\nDFS: ")
not_visited = [False] * (max(g.graph.keys())+1)
dfs(g.graph, 2 , not_visited)


#Jug Problem
def water_jug(x,y,target):
    jug1=0
    jug2=0

    while jug1!=target and jug2!=target:
        print(f"Jug 1: {jug1}, Jug 2: {jug2}")

        if jug1 < x:
            jug1=x
        elif jug2==y:
            jug2=0
        elif jug1>0 and jug2<y:
            pour_amount=min(jug1,y-jug2)
            jug1-=pour_amount
            jug2+=pour_amount
        elif jug2>0 and jug1<x:
            pour_amount=min(jug2,x-jug1)
            jug1+=pour_amount
            jug2-=pour_amount
        else:
            break
    print(f"Jug 1: {jug1}, Jug 2: {jug2}")
    if jug1==target or jug2==target:
        print(f"Target of {target} litres achieved")
    else:
        print("Target cant be reached with these jug sizes")

water_jug(4,9,8)



#N Queens
global N
N=4

def print_solution(board):
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=' ')
        print()

def isSafe(board, row, col):
    for i in range(col):
        if board[row][i]==1:
            return False
    for i,j in zip(range(row, -1,-1),range(col,-1,-1)):
        if board[i][j]==1:
            return False
    for i,j in zip(range(row,N,1),range(col,-1,-1)):
        if(board[i][j]==1):
            return False
    return True

def solveNQUtil(board, col):
    if col>=N:
        return True
    
    for i in range(N):
        if isSafe(board, i, col):
            board[i][col]=1

            if solveNQUtil(board, col+1)==True:
                return True
            
            board[i][col]=0

def solveNQ():
    board=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    if solveNQUtil(board, 0)==False:
        print("Solution does not exist")
        return False
    print_solution(board)
    return True
solveNQ()



#HANOI
def TowerOfHanoi(n, source, destination, auxiliary):
    if n==1:
        print(f"Move Disk 1 from source {source} to destination {destination}")
        return
    TowerOfHanoi(n-1,source, auxiliary, destination)
    print(f"Move Disk {n} from source {source} to destination {destination}")
    TowerOfHanoi(n-1, destination, auxiliary, source)
    
n=3

TowerOfHanoi(n,'A','B','C')



#AO STAR
import heapq

def astar(adj_matrix, start, goal, heuristic):
    num_nodes = len(adj_matrix)
    open_set = [(0, start)]  
    came_from = {} 
    g_score = {node: float('inf') for node in range(num_nodes)}
    g_score[start] = 0
    f_score = {node: float('inf') for node in range(num_nodes)}
    f_score[start] = g_score[start] + heuristic[start]

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor in range(num_nodes):
            if adj_matrix[current][neighbor] != 0: 
                cost = adj_matrix[current][neighbor]
                tentative_g_score = g_score[current] + cost

                if tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = g_score[neighbor] + heuristic[neighbor]


                    if (f_score[neighbor], neighbor) not in open_set:
                        heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None  

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.insert(0, current)
    return path

if __name__ == '__main__':
    adj_matrix = [
        [0, 2, 4, 0, 0],
        [2, 0, 0, 3, 5],
        [4, 0, 0, 0, 0],
        [0, 3, 0, 0, 2],
        [0, 5, 0, 2, 0]
    ]

    heuristic = [5, 4, 7, 2, 3]

    start_node = 2
    goal_node = 4

    path = astar(adj_matrix, start_node, goal_node, heuristic)
    if path:
        print("Path found:", " -> ".join(map(str, path)))
    else:
        print("No path found")