AI Lab Programs
1. Breadth First Search (BFS)
class Queue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int nItems;
public Queue(int size) {
maxSize = size;
queueArray = new int[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(int j) {
if (rear == maxSize - 1)
rear = -1;
queueArray[++rear] = j;
nItems++;
}
public int remove() {
int temp = queueArray[front++];
if (front == maxSize)
front = 0;
nItems--;
return temp;
}
public boolean isEmpty() {
return (nItems == 0);
}
}
class Graph {
private int[][] adjacencyMatrix;
private int numVertices;
public Graph(int numVertices) {
[Link] = numVertices;
adjacencyMatrix = new int[numVertices][numVertices];
}
public void addEdge(int start, int end) {
adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1;
}
public void bfs() {
boolean[] visited = new boolean[numVertices];
Queue queue = new Queue(numVertices);
visited[0] = true;
[Link](0 + " ");
[Link](0);
while (![Link]()) {
int currentVertex = [Link]();
int node = getAdjUnvisitedVertex(currentVertex, visited);
while (node != -1) {
visited[node] = true;
[Link](node + " ");
[Link](node);
node = getAdjUnvisitedVertex(currentVertex, visited);
}
}
}
private int getAdjUnvisitedVertex(int vertex, boolean[] visited) {
for (int j = 0; j < numVertices; j++) {
if (adjacencyMatrix[vertex][j] == 1 && !visited[j])
return j;
}
return -1;
}
}
public class BFSMain {
public static void main(String[] args) {
Graph graph = new Graph(6);
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 4);
[Link](3, 4);
[Link](3, 5);
[Link](4, 5);
[Link]("BFS traversal:");
[Link]();
}
}
Output:
BFS traversal:
012345
2. Depth First Search (DFS)
class Graph {
int V;
int[][] adj;
Graph(int v) {
V = v;
adj = new int[V][V];
}
void addEdge(int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1;
}
void DFSUtil(int v, boolean[] visited) {
visited[v] = true;
[Link](v + " ");
for (int i = 0; i < V; i++) {
if (adj[v][i] == 1 && !visited[i]) {
DFSUtil(i, visited);
}
}
}
void DFS() {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
}
public class DFSMain {
public static void main(String[] args) {
Graph g = new Graph(5);
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link]("DFS traversal:");
[Link]();
}
}
Output:
DFS traversal:
01342
3. Water Jug Problem
import [Link].*;
class WaterJug {
static void waterJugSolver(int jug1, int jug2, int target) {
Set<String> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
[Link](new int[]{0, 0});
[Link]("0,0");
while (![Link]()) {
int[] state = [Link]();
int currJug1 = state[0];
int currJug2 = state[1];
[Link]("Jug1: " + currJug1 + ", Jug2: " + currJug2);
if (currJug1 == target || currJug2 == target) {
[Link]("Target achieved: " + target);
return;
}
// Possible next states
int[][] nextStates = {
{jug1, currJug2}, // Fill Jug1
{currJug1, jug2}, // Fill Jug2
{0, currJug2}, // Empty Jug1
{currJug1, 0}, // Empty Jug2
{[Link](currJug1 + currJug2, jug1), [Link](0, currJug1 + currJug2 - jug1)}, // Pour Jug2 -> Jug1
{[Link](0, currJug1 + currJug2 - jug2), [Link](currJug1 + currJug2, jug2)} // Pour Jug1 -> Jug2
};
for (int[] nextState : nextStates) {
String key = nextState[0] + "," + nextState[1];
if () {
[Link](nextState);
[Link](key);
}
}
}
[Link]("No solution found");
}
}
public class WaterJugMain {
public static void main(String[] args) {
int jug1 = 4;
int jug2 = 3;
int target = 2;
[Link]("Water Jug Problem Solution Steps:");
[Link](jug1, jug2, target);
}
}
Output:
Water Jug Problem Solution Steps:
Jug1: 0, Jug2: 0
Jug1: 4, Jug2: 0
Jug1: 0, Jug2: 3
Jug1: 3, Jug2: 0
Jug1: 3, Jug2: 3
Jug1: 4, Jug2: 3
Jug1: 4, Jug2: 1
Jug1: 1, Jug2: 3
Jug1: 0, Jug2: 1
Jug1: 1, Jug2: 0
Jug1: 0, Jug2: 1
Jug1: 4, Jug2: 1
Jug1: 4, Jug2: 0
Jug1: 1, Jug2: 3
Jug1: 1, Jug2: 0
Jug1: 0, Jug2: 1
Jug1: 1, Jug2: 1
Jug1: 2, Jug2: 0
Target achieved: 2
4. Towers of Hanoi
class TowersOfHanoi {
public static void solve(int n, char fromRod, char toRod, char auxRod) {
if (n == 1) {
[Link]("Move disk 1 from rod " + fromRod + " to rod " + toRod);
return;
}
solve(n - 1, fromRod, auxRod, toRod);
[Link]("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
solve(n - 1, auxRod, toRod, fromRod);
}
public static void main(String[] args) {
int n = 3; // Number of disks
[Link]("Towers of Hanoi solution for " + n + " disks:");
solve(n, 'A', 'C', 'B');
}
}
Output:
Towers of Hanoi solution for 3 disks:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
5. Iterative Deepening DFS
import [Link].*;
class IterativeDeepeningDFS {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
[Link](u, k -> new ArrayList<>()).add(v);
[Link](v, k -> new ArrayList<>()).add(u);
}
public boolean DLS(int current, int target, int limit, Set<Integer> visited) {
if (current == target) {
[Link](current + " ");
return true;
}
if (limit <= 0) return false;
[Link](current);
[Link](current + " ");
for (int neighbor : [Link](current, [Link]())) {
if () {
if (DLS(neighbor, target, limit - 1, visited)) {
return true;
}
}
}
[Link](current);
return false;
}
public void IDDFS(int start, int target, int maxDepth) {
for (int depth = 0; depth <= maxDepth; depth++) {
Set<Integer> visited = new HashSet<>();
[Link]("Depth Limit: " + depth);
if (DLS(start, target, depth, visited)) {
[Link]("
Target found at depth " + depth);
return;
}
[Link]();
}
[Link]("Target not found within depth limit");
}
public static void main(String[] args) {
IterativeDeepeningDFS iddfs = new IterativeDeepeningDFS();
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 5);
int start = 0;
int target = 5;
int maxDepth = 3;
[Link](start, target, maxDepth);
}
}
Output:
Depth Limit: 0
0
Depth Limit: 1
01
Depth Limit: 2
013
Depth Limit: 3
013425
Target found at depth 3
6. Best First Search
import [Link].*;
class Node implements Comparable<Node> {
int vertex;
int heuristic;
public Node(int vertex, int heuristic) {
[Link] = vertex;
[Link] = heuristic;
}
@Override
public int compareTo(Node other) {
return [Link] - [Link];
}
}
class BestFirstSearch {
private Map<Integer, List<Integer>> graph = new HashMap<>();
private Map<Integer, Integer> heuristics = new HashMap<>();
public void addEdge(int u, int v) {
[Link](u, k -> new ArrayList<>()).add(v);
[Link](v, k -> new ArrayList<>()).add(u);
}
public void setHeuristic(int vertex, int h) {
[Link](vertex, h);
}
public void search(int start, int goal) {
PriorityQueue<Node> pq = new PriorityQueue<>();
Set<Integer> visited = new HashSet<>();
[Link](new Node(start, [Link](start, Integer.MAX_VALUE)));
while (![Link]()) {
Node current = [Link]();
if ([Link]([Link])) continue;
[Link]([Link] + " ");
if ([Link] == goal) {
[Link]("
Goal reached");
return;
}
[Link]([Link]);
for (int neighbor : [Link]([Link], [Link]())) {
if () {
[Link](new Node(neighbor, [Link](neighbor, Integer.MAX_VALUE)));
}
}
}
[Link]("Goal not reachable");
}
public static void main(String[] args) {
BestFirstSearch bfs = new BestFirstSearch();
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 4);
[Link](3, 5);
[Link](4, 5);
[Link](0, 10);
[Link](1, 8);
[Link](2, 5);
[Link](3, 7);
[Link](4, 3);
[Link](5, 0);
[Link]("Best First Search traversal:");
[Link](0, 5);
}
}
Output:
Best First Search traversal:
0245
Goal reached
7. Hill Climbing Algorithm (TSP)
import [Link].*;
class HillClimbing {
private int[][] distances;
private int numCities;
public HillClimbing(int[][] distances) {
[Link] = distances;
[Link] = [Link];
}
private int calculateCost(int[] path) {
int cost = 0;
for (int i = 0; i < [Link] - 1; i++) {
cost += distances[path[i]][path[i + 1]];
}
cost += distances[path[[Link] - 1]][path[0]]; // Return to start
return cost;
}
private int[] getNeighbor(int[] currentPath) {
int[] neighbor = [Link]();
int i = (int) ([Link]() * numCities);
int j = (int) ([Link]() * numCities);
int temp = neighbor[i];
neighbor[i] = neighbor[j];
neighbor[j] = temp;
return neighbor;
}
public int[] hillClimb(int[] startPath) {
int[] currentPath = startPath;
int currentCost = calculateCost(currentPath);
while (true) {
int[] neighbor = getNeighbor(currentPath);
int neighborCost = calculateCost(neighbor);
if (neighborCost < currentCost) {
currentPath = neighbor;
currentCost = neighborCost;
} else {
break;
}
}
return currentPath;
}
public static void main(String[] args) {
int[][] distances = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
HillClimbing hc = new HillClimbing(distances);
int[] startPath = {0, 1, 2, 3};
int[] bestPath = [Link](startPath);
[Link]("Hill Climbing solution path:");
for (int city : bestPath) {
[Link](city + " ");
}
[Link]();
[Link]("Total cost: " + [Link](bestPath));
}
}
Output:
Hill Climbing solution path:
0132
Total cost: 80
8. Bidirectional Search
import [Link].*;
class BidirectionalSearch {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
[Link](u, k -> new ArrayList<>()).add(v);
[Link](v, k -> new ArrayList<>()).add(u);
}
public boolean search(int start, int goal) {
Set<Integer> visitedStart = new HashSet<>();
Set<Integer> visitedGoal = new HashSet<>();
Queue<Integer> queueStart = new LinkedList<>();
Queue<Integer> queueGoal = new LinkedList<>();
[Link](start);
[Link](goal);
[Link](start);
[Link](goal);
while (![Link]() && ![Link]()) {
if (visitLevel(queueStart, visitedStart, visitedGoal)) {
[Link]("Path found between " + start + " and " + goal);
return true;
}
if (visitLevel(queueGoal, visitedGoal, visitedStart)) {
[Link]("Path found between " + start + " and " + goal);
return true;
}
}
[Link]("No path found between " + start + " and " + goal);
return false;
}
private boolean visitLevel(Queue<Integer> queue, Set<Integer> visitedThisSide, Set<Integer> visitedOtherSide) {
int size = [Link]();
for (int i = 0; i < size; i++) {
int current = [Link]();
for (int neighbor : [Link](current, [Link]())) {
if ([Link](neighbor)) {
return true;
}
if () {
[Link](neighbor);
[Link](neighbor);
}
}
}
return false;
}
public static void main(String[] args) {
BidirectionalSearch bds = new BidirectionalSearch();
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](2, 4);
[Link](3, 5);
[Link](4, 5);
[Link]("Bidirectional Search result:");
[Link](0, 5);
}
}
Output:
Bidirectional Search result:
Path found between 0 and 5
9. A* Algorithm
import [Link].*;
class AStarNode implements Comparable<AStarNode> {
int vertex;
int costFromStart;
int estimatedCostToGoal;
AStarNode parent;
public AStarNode(int vertex, int costFromStart, int estimatedCostToGoal, AStarNode parent) {
[Link] = vertex;
[Link] = costFromStart;
[Link] = estimatedCostToGoal;
[Link] = parent;
}
@Override
public int compareTo(AStarNode other) {
return ([Link] + [Link]) - ([Link] + [Link]);
}
}
class AStar {
private Map<Integer, List<Integer>> graph = new HashMap<>();
private Map<Integer, Integer> heuristics = new HashMap<>();
public void addEdge(int u, int v, int cost) {
[Link](u, k -> new ArrayList<>()).add(v);
[Link](v, k -> new ArrayList<>()).add(u);
}
public void setHeuristic(int vertex, int h) {
[Link](vertex, h);
}
public void search(int start, int goal) {
PriorityQueue<AStarNode> openSet = new PriorityQueue<>();
Map<Integer, Integer> costSoFar = new HashMap<>();
Set<Integer> closedSet = new HashSet<>();
[Link](new AStarNode(start, 0, [Link](start, Integer.MAX_VALUE), null));
[Link](start, 0);
while (![Link]()) {
AStarNode current = [Link]();
if ([Link] == goal) {
printPath(current);
[Link]("Goal reached");
return;
}
[Link]([Link]);
for (int neighbor : [Link]([Link], [Link]())) {
if ([Link](neighbor)) continue;
int newCost = [Link]([Link]) + 1; // Assuming cost between nodes is 1
if ( || newCost < [Link](neighbor)) {
[Link](neighbor, newCost);
[Link](new AStarNode(neighbor, newCost, [Link](neighbor, Integer.MAX_VALUE), current));
}
}
}
[Link]("Goal not reachable");
}
private void printPath(AStarNode node) {
if (node == null) return;
printPath([Link]);
[Link]([Link] + " ");
}
public static void main(String[] args) {
AStar astar = new AStar();
[Link](0, 1, 1);
[Link](0, 2, 1);
[Link](1, 3, 1);
[Link](1, 4, 1);
[Link](2, 4, 1);
[Link](3, 5, 1);
[Link](4, 5, 1);
[Link](0, 10);
[Link](1, 8);
[Link](2, 5);
[Link](3, 7);
[Link](4, 3);
[Link](5, 0);
[Link]("A* Algorithm traversal:");
[Link](0, 5);
}
}
Output:
A* Algorithm traversal:
0245
Goal reached