DAA

PRACTICAL FILE

Submitted to:
Prof. Rupinder Kaur
Prof. Simarjot kaur Submitted by:
Name: SHASHI KUMAR SETH
Group: 4C23
Roll no: 2100428

BABA BANDA SINGH BAHADUR ENGINEERING COLLEGE FATEHGARH SAHIB

INDEX
S.NO. PROGRAM PAGE DATE REMARKS
1. Write a program to implement linear search. 1-2

2. Write a program to Implement binary search. 3-4

3. Write a program to implement bubble sort. 5-6

4. Write a program to implement merge sort. 7-9

5. Write a program to solve knapsack using greedy 10-12

approach.

6. Code and analyze solutions to following problem 13-14

with given strategies:--knapsack using dynamic
approach.

7. Code and analyze to find an optiomal solution to 15

matrix chain multiplication using dynamic
programming.

8. Code and analyze to find an optimal solution to 16-17

Travelling Salesman Problem (TSP) using dynamic
programming.

9. Code and analyze to do a depth-first search (DFS) 18-19

on an undirected graph implementing an
application of DFS such as.
(i) To find the topological sort of a directed
graph.
(ii)To find a path from source to goal in a
maze.

10. Code and analyze to do a breadth-frist search 20-23

(BFS) on an undirected graph implementing of BFS
such as.
(i)To find connected components graph.
(ii)To check wheather a given graph is
bipartite.
11. Code and analyze to find shortest paths in graph 24-27
with positive adge weights using Dijkstra
algorithm.

12. Code and analyze to find shortest paths in a graph 28-31

with arbitrary edge weights using Bellman Ford
algorithm.

13. Code and analyze to find shortest paths in graphs 32-33

with arbitrary edge weights using Floyd algorithm.
14. Code and analyze to find the minimum spanning 34-35
tree in a weighted undirected graph using prim
algorithm.

15. Code and analyze to find the minimum spanning 36-37

tree in a weighted undirected graph using
Kruskal’s algorithm.

16. Code any real world problem or TSP algorithm 38-43

using any heuristic technique.
EXPERIMENT-6
Aim:-Code and analyze solutions to following problem with given
strategies:
Knapsack using dynamic approach.
PROGRAM:-
#include <iostream>
using namespace std;
int max(int x, int y)
{
return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n)
{
int i, wt;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++)
{
for (wt = 0; wt <= W; wt++)
{
if (i == 0 || wt == 0)

K[i][wt] = 0;

else if (w[i - 1] <= wt)

K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);

else

K[i][wt] = K[i - 1][wt];

}
}
return K[n][W];

}
int main()

{
cout << "Enter the number of items in a Knapsack:";

Page | 13
int n, W; cin >> n; int v[n], w[n];

for (int i = 0; i < n; i++)

{
cout << "Enter value and weight for item " << i << ":";

cin >> v[i];

cin >> w[i];
}
cout << "Enter the capacity of knapsack";
cin >> W;

cout << knapSack(W, w, v, n);

return 0;
}

OUT PUT:-

Page | 14
EXPERIMENT-7
Aim:- Code and analyze to find an optimal solution to matrix chain
multiplication using dynamic programming.
PROGRAM:-
#include <bits/stdc++.h>
using namespace std;
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int mini = INT_MAX;
int count;

for (k = i; k < j; k++)

{
count = MatrixChainOrder(p, i, k)+ MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j];

mini = min(count, mini);

}

return mini;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0])
cout << "Minimum number of multiplications is "<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}
OUT PUT:-

Page | 15
EXPERIMENT-8
Aim:- Code and analyze to find an optimal solution to Travelling Salesman Problem
(TSP) using dynamic programming.
PROGRAM:-
#include<iostream>
using namespace std;
int ary[10][10],completed[10],n,cost=0;
void takeInput()
{
int i,j;
cout<<"Enter the number of villages: ";
cin>>n;

cout<<"\nEnter the Cost Matrix\n";

for(i=0;i < n;i++)

{ cout<<"\nEnter Elements of Row: "<<i+1<<"\n";

for( j=0;j < n;j++) cin>>ary[i][j];

completed[i]=0;
}

cout<<"\n\nThe cost list is:";

for( i=0;i < n;i++)

{
cout<<"\n";

for(j=0;j < n;j++) cout<<"\t"<<ary[i][j];

}
}

int least(int c)
{
int i,nc=999; int min=999,kmin;

for(i=0;i < n;i++)

{
if((ary[c][i]!=0)&&(completed[i]==0)) if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i]; kmin=ary[c][i]; nc=i;
}
}

Page | 16
if(min!=999) cost+=kmin;

return nc;
}

void mincost(int city)

{
int i,ncity;

completed[city]=1;

cout<<city+1<<"--->"; ncity=least(city);

if(ncity==999)
{
ncity=0;
cout<<ncity+1;
cost+=ary[city][ncity];

return;
}

mincost(ncity);
}

int main()
{
takeInput();
cout<<"\n\nThe Path is:\n";
mincost(0);

cout<<"\n\nMinimum cost is "<<cost;

return 0;
}
OUT PUT:-

Page | 17
EXPERIMENT-9
Aim:- Code and analyze to do a depth-first search (DFS) on an undirected graph.
Implementing an application of DFS such as .
i.To find the topological sort of a directed cyclic graph.
OR
ii. To find a path from source to goal in a maze.
#include<iostream>
using namespace std;
int a[10][10],n,indegre[10];
void find_indegre()
{
int j,i,sum;
for(j=0;j<n;j++)
{
sum=0;
for(i=0;i<n;i++)
sum+=a[i][j];
indegre[j]=sum;
}
}
void topology()
{
int i,u,v,t[10],s[10],top=-1,k=0;
find_indegre();
for(i=0;i<n;i++)
{
if(indegre[i]==0)
t[k++]=u;
for(v=0;v<n;v++)
{
if(a[u][v]==1)
{
indegre[v]--;
if(indegre[v]==0) s[++top]=v;
}
}
}
cout<<"The topological Sequence is:\n";
for(i=0;i<n;i++) cout<<t[i];

Page | 18
}
int main()
{
int i,j;
cout<<"Enter number of jobs:";
cin>>n;
cout<<"\nEnter the adjacency matrix:\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin>>a[i][j];
}
topology();
return 0;
}

OUTPUT:-

Page | 19
EXPERIMENT-10
Aim:- Code and analyze to do a breadth-first search (BFS) on an undirected graph
implementing application of BFS such as.
i. To find connected components graph.
OR
ii. To check wheather a given graph is bipartite.
#include <iostream>
#include <ctime>
using namespace std;
struct node {
int info;
node *next;
};
class Queue {
private:
node *front;
node *rear;
public:
Queue();
~Queue();
bool isEmpty();
void enqueue(int);
int dequeue();
void display();
};
void Queue::display(){
node *p = new node;
p = front;
if(front == NULL){
cout<<"\nNothing to Display\n";
}else{
while(p!=NULL){
cout<<endl<<p->info;
p = p->next;
}
}
}
Queue::Queue() {
front = NULL;

Page | 20
rear = NULL;
}
Queue::~Queue() {
delete front;
}
void Queue::enqueue(int data) {
node *temp = new node();
temp->info = data;
temp->next = NULL;
if(front == NULL){
front = temp;
}else{
rear->next = temp;
}
rear = temp;
}
int Queue::dequeue() {
node *temp = new node();
int value;
if(front == NULL){
cout<<"\nQueue is Emtpty\n";
}else{
temp = front;
value = temp->info;
front = front->next;
delete temp;
}
return value;
}
bool Queue::isEmpty() {
return (front == NULL);
}
class Graph {
private:
int n; /// n is the number of vertices in the graph
int **A; /// A stores the edges between two vertices
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int u, int v);

Page | 21
void BFS(int );
};
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool Graph::isConnected(int u, int v) {
return (A[u-1][v-1] == 1);
}
void Graph::addEdge(int u, int v) {
A[u-1][v-1] = A[v-1][u-1] = 1;
}
void Graph::BFS(int s) {
Queue Q;
/** Keeps track of explored vertices */
bool *explored = new bool[n+1];
/** Initailized all vertices as unexplored */
for (int i = 1; i <= n; ++i)
explored[i] = false;
/** Push initial vertex to the queue */
Q.enqueue(s);
explored[s] = true; /** mark it as explored */
cout << "Breadth first Search starting from vertex ";
cout << s << " : " << endl;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
int v = Q.dequeue();
/** display the explored vertices */

Page | 22
cout << v << " ";
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= n; ++w)
/** Explores the vertex w if it is connected to v
and and if it is unexplored */
if (isConnected(v, w) && !explored[w]) {
/** adds the vertex w to the queue */
Q.enqueue(w);
/** marks the vertex w as visited */
explored[w] = true;
}
}
cout << endl;
delete [] explored;
}
int main() {
/** Creates a graph with 12 vertices */
Graph g(12);
/** Adds edges to the graph */
g.addEdge(1, 2); g.addEdge(1, 3);
g.addEdge(2, 4); g.addEdge(3, 4);
g.addEdge(3, 6); g.addEdge(4 ,7);
g.addEdge(5, 6); g.addEdge(5, 7);
clock_t t1;
t1 = clock();
/** Explores all vertices findable from vertex 1 */
g.BFS(1);
float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ;
cout <<endl<< "The time taken for Breadth first search: "<< diff << endl;
}
Output:-

Page | 23
EXPERIMENT-11
Aim:-code and analyze to find shortest paths in graph with positive adge
weights using Dijkstra’s algorithm.
PROGRAM:-
#include<iostream>
using namespace std;
#define N 7
#define INT_MAX 1024
int c[N][N],s[N],d[N];
void dj(int );
int main()
{

int i,j,n,min,u;
cout<<"\nenter no of vertices in graph\n";
cin>>n;
int e,sv,ev;
cout<<"\nenter no of edges in graph\n";
cin>>e;
for( i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
{
c[i][j]=INT_MAX;
}
c[i][i]=0;
}
cout<<"\nenter starting vertex, terminal vertex and weight respectively:\n";
for( i=1;i<=e;i++)
{
cout<<"\nEdge "<<i<<endl;

Page | 24
cin>>sv>>ev;
cin>>c[sv][ev];
}
cout<<"\ncost matrix is: \n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<c[i][j]<<"\t";
}
cout<<endl;
}
dj(n);

}
void dj(int n)
{
// logic starts here
int v,u,i,j,min;
cout<<"\nenter the starting vertex: \n";
cin>>v;
for(i=1;i<=n;i++)
{
s[i]=0;
d[i]=c[v][i];
}
s[v]=1;
d[v]=0;
for(i=2;i<n;i++)
{
min= INT_MAX;

Page | 25
for(j=1;j<=n;j++)
{
if((s[j]==0)&&(min>=d[j]))
{
min=d[j];
u=j;
}
}
s[u]=1;
for(j=1;j<=n;j++)
{
if((s[j]==0)&&(d[j]>d[u]+c[u][j]))
{
d[j]=d[u]+c[u][j];
}
}
}
cout<<"\nShortest paths from source vertex "<<v<<endl;
for(i=1;i<=n;i++)
{
cout<<i<<"\t"<<d[i]<<endl;

}
return 0;
}

Page | 26
OUTPUT:-

Page | 27
EXPERIMENT:-12
Aim:- Code and analyze to find shortest paths in a graph with arbitrary edge
weights using Bellman Ford algorithm.
PROGRAM:-
#include<iostream.h>
#include<stdlib.h>
#include <string.h>
#include<conio.h>
#include <limits.h>
#define VV 5
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
return graph;
}
void printArr(int dist[], int n)
{
cout<<"\nVertex Distance from Source\n";
for (int i = 0; i < n; ++i)
cout<< i<<" "<<dist[i]<<endl;

Page | 28
}
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[VV];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (i= 1; i <= V-1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] + weight < dist[v])
cout<<"\n\nGraph contains negative weight cycle";
}
printArr(dist, V);
return;
}
void main()

Page | 29
{
clrscr();
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
getch();
}

Page | 30
OUTPUT:_

Page | 31
EXPERIMENT:-13
Aim:- Code and analyze to find shortest paths in a graph with arbitrary edge
weights using Floyds’ algorithm.
PROGRAM:-
#include <iostream>
#include <conio.h>
using namespace std;
void floyds(int b[][7])
{
int i, j, k;
for (k = 0; k < 7; k++)
{
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
{
if ((b[i][k] * b[k][j] != 0) && (i != j))
{
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
{
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 7; i++)
{
cout<<"\nMinimum Cost With Respect to Node:"<<i<<endl;
for (j = 0; j < 7; j++)
{
cout<<b[i][j]<<"\t";
}

}
}
int main()
{
int b[7][7];

Page | 32
cout<<"ENTER VALUES OF ADJACENCY MATRIX\n\n";
for (int i = 0; i < 7; i++)
{
cout<<"enter values for "<<(i+1)<<" row"<<endl;
for (int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
floyds(b);
getch();
}

OUTPUT:-

Page | 33
EXPERIMENT:-14
Aim:- Code and analyze to find the minimum spanning tree in a weighted,
undirected graph using Prim’s algorithm.
PROGRAM:-
#include <stdio.h>
#include <limits.h>
#include <iostream>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}
int printMST(int parent[], int n, int graph[V][V])
{
cout<<"Edge Weight\n";
for (int i = 1; i < V; i++)
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;

for (int count = 0; count < V - 1; count++)

{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)

Page | 34
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, V, graph);
}
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 }, };
primMST(graph);
return 0;
}

OUTPUT:-

Page | 35
EXPERIMENT:-15
Aim:- Code and analyze to find the minimum spanning tree in a weighted,
undirected graph using Kruskal’s algorithm.
PROGRAM:-
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
int ne=1,min_cost=0;
void main()
{
int n,i,j,min,a,u,b,v,cost[20][20],parent[20];
clrscr();
cout<<"Enter the no. of vertices:";
cin>>n;
cout<<"\nEnter the cost matrix:\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>cost[i][j];
for(i=1;i<=n;i++)
parent[i]=0;
cout<<"\nThe edges of spanning tree are\n";
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];

Page | 36
if(u!=v)
{
cout<<"Edge"<<ne++<<"\t"<<a<<"->"<<b<<"="<<min<<"\n";
min_cost=min_cost+min;
parent[v]=u;
}
cost[a][b]=cost[a][b]=999;
}
cout<<"\nMinimum cost=\n"<<min_cost;
getch();
};

OUTPUT:-

Page | 37
EXPERIMENT:-16
Aim:- Code any real world problem or TSP algorithm using any heuristic
technique

Genetic Algorithms Applied to Travelling Salesman Problems in C++

Each successive population is evaluated in terms of its fitness. The shorter the overall tour
distance, the higher its fitness. The program identifies the best solution in the population at
each generation, logging its distance to a text file. Then a selection mechanism is used to
obtain the better solutions, in this case a tournament selection mechanism is employed.
After selection, pairs of tours are chosen arbitrarily and portions of their tour cities are
exchanged in order to produce a new offspring. Also some mutation operators are
employed to disrupt randomly selected tours so as to more effectively explore the solution
space.
// Run the genetic algorithm
Tour* GeneticAlgorithm::Run( const int& iter )
{
bestIndex = Evaluate();
Tour* tour = pop.GetTour( bestIndex );
LogResult( tour->GetFitness(), iter, 10 );
Select();
Crossover(); Mutate();

return tour;
}

The PMX Crossover Operator

For this type of problem that consists of ordered lists of cities, the use of a direct exchange
between tours to produce new offspring is not feasible without losing the given ordering. A
number of techniques are available, the one chosen here is the partially matched crossover,
or PMX for short.

In this method, two crossover points are arbitrarily selected and the PMX proceeds by
position wise exchanges. The two crossover points give matching selection. It affects
crossover by using position-by-position exchange operations. Here is the C++
implementation:

// Apply two-point crossover to selected Tour pair void

Population::Crossover( const int& index1,
const int& index2, const int& point1,
const int& point2,
const int& bestIndex )
{
std::vector<int> offspr;

Page | 38
if ( point1 < 0 || point1 >= chrSize ) return;
if ( point2 < 0 || point2 >= chrSize ) return;

int p1 = point1; int

p2 = point2;

if ( p1 > p2 )
{
int tmp = p1;
p1 = p2; p2 =
tmp;
}

// Create new offspring to replace parent

Tour* tour1 = GetTour( index1 );
Tour* tour2 = GetTour( index2 );

std::vector<int> s1; std::vector<int> s2;

for ( int i = p1; i < p2; i++ ) { int city1 = tour1->GetCity( i ); int city2 =
tour2->GetCity( i ); s1.push_back( city1 ); s2.push_back( city2 );
}

std::sort( s1.begin(), s1.end() ); std::sort(

s2.begin(), s2.end() );

// Find all numbers unique to both s1 and s2 std::set<int> intersection;

std::set_intersection( s1.begin(), s1.end(), s2.begin(),
s2.end(), std::inserter( intersection, intersection.end() ) );

std::vector<int> s1_new; std::vector<int>

s2_new;

int size = p2 - p1;

for ( int i = 0; i < size; i++ )

{
int val1 = s1[ i ]; int val2
= s2[ i ];

bool is_in1 = intersection.find(val1) != intersection.end(); bool is_in2 =

intersection.find(val2) != intersection.end();

if ( !is_in1 )

Page | 39
{
s1_new.push_back( val1 );
}

if ( !is_in2 )
{
s2_new.push_back( val2 );
} }

int index = 0;

for ( int i = 0; i < chrSize; i++ ) { if ( i >= p1 && i < p2 ) { int val = tour2->GetCity( i );
offspr.push_back( val );
}
else {
int val = tour1->GetCity( i );

// Is val in s2_new set?

std::vector<int>::iterator it;
it = find( s2_new.begin(), s2_new.end(), val );

bool is_in = it != s2_new.end();

if ( is_in )
{ int val_new = s1_new[ index++ ];
offspr.push_back( val_new );
}
else {
offspr.push_back( val );
}
} }

// Copy the values to create one new offspring int

member = rand() % pop.size();

while ( member == bestIndex )

{
member = rand() % pop.size();
}

Tour* tour = pop.at( member );

tour->SetCities( offspr );
}

Page | 40
Mutation Operators
At a given probability of mutation, three different mutation heuristics are used at
approximately equal probabilities. The first heuristic swaps randomly chosen city pairs a
randomly small (1 – 4) number of times. The second heuristic rotates randomly selected
portions of cities a random number of times. The third heuristic reverses cities between two
ranomly selected points in the tour. C++ implementation below:
// Apply mutation to selected Tour
void Population::Mutation( const int& index )
{
Tour* tour = pop.at( index );
int tsize = tour->TourSize();

int p1 = 1 + rand() % ( tsize - 1 ); int p2 = 1 +

rand() % ( tsize - 1 );

while ( p1 == p2 )
{
p2 = 1 + rand() % ( tsize - 1 );
}

int r = rand() % 100;

if ( r < 33 )
{
int n = 1 + rand() % 3;
for ( int i = 0; i < n; i++ ) { p1 = 1 + rand() % ( tsize - 1 ); p2 =
1 + rand() % ( tsize - 1 ); while ( p1 == p2 ) { p2 = 1 + rand() % ( tsize - 1 ); } tour->Swap( p1, p1
);
} }
else if ( r < 67 ) { int c[ 3 ]; c[ 0 ] = 1 + rand() % ( tsize - 1 ); c[ 1 ] = 1 + rand() % ( tsize - 1 );
c[ 2 ] = 1 + rand() % ( tsize - 1 ); while ( c[ 0 ] == c[ 1 ] || c[ 1 ] == c[ 2 ] || c[ 1 ] == c[ 2 ] ) { c[
0 ] = 1 + rand() % ( tsize - 1 ); c[ 1 ] = 1 + rand() % ( tsize - 1 ); c[ 2 ] = 1 + rand() % ( tsize - 1
); } std::sort( c, c + 3 ); tour->Rotate( c[ 0 ], c[ 1 ], c[ 2 ] ); } else {
tour->ReverseCities( p1, p2 );
}
}

The Tour data structure:

Page | 41
The “Tour” class is used to house the ordering of cities for a tour, and perform other utilities
such as calculate the distance between individual cities and tours, store the best tour found,
create a random tour etc. It essentially stores the tours as a standard C++ vector array of
integers, along the fitness value of the tour and is the same structure as that used in a
previous posting that describes the application of simulated annealing to the same travelling
salesperson problem:

class Tour
{
public
:
Tour(void);
Tour( CoordMatrix* mat );
Tour( CoordMatrix* mat, std::vector< int > tour );
~Tour(void);

void Swap( const int& c1,const int& c2 );

void TwoOpt( const int& c1,

const int& c2, const int& c3,
const int& c4 );
void Scramble( const int& p1, const int &p2 );

void Rotate( const int& p1, const int& p2, const int& p3 ); void
ReverseCities( const int& c1, const int& c2 );

double CalcTourFitness( CoordMatrix* mat ) const;

int TourSize() const; int GetCity(

const int& index );
void StoreTour( std::vector<int>& v );

void SetMatrix( CoordMatrix* mat );

void CreateRandomTour( const int& size );

void CreateNearestNeighbourTour( const int& size, CoordMatrix* mat ); void

SetCities( const std::vector<int>& v ); void SetCity( const int& index, const int&
value ); void Reset();
void SetFitness( const double& value ); double
GetFitness() const;
double TourDistance( CoordMatrix* mat ) const;

private:

Page | 42
double Distance( const int& c1,
const int& c2,
CoordMatrix* mat ) const;

int GetNearestNeighbour( const int& c,

std::set<int>& cset, CoordMatrix* mat );

private: std::vector< int >

cities; double fitness;
};

Some initial results

As with simulated annealing, genetic algorithms also have the problem of finding suitable
combinations of tunable parameters, in this case mutation and crossover rates, so as to help
the algorithm generate reasonable solutions within reasonable time scales. After quite a bit
of fooling around, some parameters that were found to be useful were:
Crossover: 20%
Mutation: 5%
Population size: 100
Tournament size: Population / 4

(If you want to play around with some other values, just open the TSPalgorithm.cpp file and
tweak the values given at the top of the page.) Applying the algorithm to the Att48.tsp
problem, over 5000 iterations yielded the following solution:

Page | 43
Page | 44