Faculty of Computing and Information Technology
University of the Punjab
Artificial Intelligence Lab 4
1. Simulated Annealing
Problem: Traveling Salesman Problem (TSP)
Description: Given a set of cities with coordinates, find the shortest possible route that visits
each city exactly once and returns to the starting city.
Example:
Cities: A (0, 0), B (1, 2), C (3, 1), D (2, 3)
Distance Matrix:
A B C D
A 0 2.24 3.16 3.61
B 2.24 0 2.24 1.41
C 3.16 2.24 0 2.24
D 3.61 1.41 2.24 0
Task: Implement Simulated Annealing to find the shortest tour that visits all cities and returns to
the starting point.
2. Tabu Search
Problem: Graph Coloring
Description: Given a graph where nodes represent tasks and edges represent constraints (tasks
that cannot be performed simultaneously), assign a color to each node such that no adjacent
nodes share the same color.
Example:
Graph with nodes connected by edges defining constraints.
Task: Implement Tabu Search to minimize the number of conflicting pairs (nodes with the same
color) in the graph.
3. Local Beam Search
Problem: N-Queens Problem
Description: Place N queens on an N x N chessboard such that no two queens threaten each
other (i.e., no two queens share the same row, column, or diagonal).
Example:
For N=4, place four queens on the board such that no two queens can attack each other.
Task: Implement Local Beam Search to find a solution to the N-Queens problem.
4. Ant Colony Optimization (ACO)
Problem: Traveling Salesman Problem (TSP)
Description: Given a set of cities with coordinates, find the shortest possible route that visits
each city exactly once and returns to the starting city.
Task: Implement Ant Colony Optimization to find the shortest tour that visits all cities and
returns to the starting point.
5. Best First Search
Problem: Maze Solving
Description: Given a maze represented as a grid with obstacles, find the shortest path from a
start position to a goal position.
Example:
Grid with walls (obstacles) and open passages.
Task: Implement Best First Search to find the shortest path through the maze.
6. A* Search
Problem: Pathfinding in a Grid
Description: Given a grid with obstacles, find the shortest path from a start position to a goal
position. Movement is restricted to adjacent cells (up, down, left, right).
Example:
Grid with obstacles represented as a 2D array.
Task: Implement A* Search to find the shortest path from a given start position to a goal
position in the grid.
