ADA-Tutorial/TravellingSalesmanProblem.cpp at main · Ujwalnaik08/ADA-Tutorial · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
//Salesman Problem
int arr[10][10], n, visit[10];
int cost_opt = 0, cost_apr = 0;
int least_apr(int c);
int least_opt(int c);

void mincost(int city){
    int i, ncity;
    visit[city] = 1;
    cout<<"--> "<<city<<endl;
    ncity = least_opt(city);
    if (ncity == 999){
        ncity = 1;
        cout<<" "<<ncity;
        printf("%d", ncity);
        cost_opt += arr[city][ncity];
        return;
    }
    mincost(ncity);
}
void mincost_apr(int city){
    int i, ncity;
    visit[city] = 1;
    cout<<"--> "<<city;
    ncity = least_apr(city);
    if (ncity == 999){
        ncity = 1;
        cout<<ncity;
        cost_apr += arr[city][ncity];
        return;
    }
    mincost_apr(ncity);
}

int least_opt(int c){
    int i, nc = 999;
    int min = 999, kmin = 999;
    for (i = 1; i <= n; i++){
        if ((arr[c][i] != 0) && (visit[i] == 0))
            if (arr[c][i] < min){
                min = arr[i][1] + arr[c][i];
                kmin = arr[c][i];
                nc = i;
            }
    }
    if (min != 999)
        cost_opt += kmin;
    return nc;
}

int least_apr(int c){
    int i, nc = 999;
    int min = 999, kmin = 999;
    for (i = 1; i <= n; i++){
        if ((arr[c][i] != 0) && (visit[i] == 0))
            if (arr[c][i] < kmin){
                min = arr[i][1] + arr[c][i];
                kmin = arr[c][i];
                nc = i;
            }
        }
    if (min != 999)
        cost_apr += kmin;
    return nc;
}
int  main()
{
    int i, j;
    cout<<"Enter No. of cities: "<<endl;
    cin>>n;
    cout<<"Enter the cost matrix"<<endl;
    for (i = 1; i <= n; i++){
        cout<<"Enter elements of row: "<<i<<endl;
        for (j = 1; j <= n; j++)
            cin>>arr[i][j];
        visit[i] = 0;
    }
    printf("The cost list is \n");
    for (i = 1; i <= n; i++){
        printf("\n\n");
        for (j = 1; j <= n; j++)
            cout<<arr[i][j]<<" ";
    }
    cout<<"Optimal Solution"<<endl;
    cout<<"The path is : "<<endl;
    mincost(1);
    cout<<"Minimum cost is :"<<endl;
    cout<<cost_opt<<endl;
    cout<<"Approximated Solution"<<endl;
    for (i = 1; i <= n; i++)
        visit[i] = 0;
    cout<<"The path is : "<<endl;
    mincost_apr(1);
    cout<<"Minimum cost :"<<cost_apr<<endl;
    cout<<"Error in approximation is approximated solution / optimal solution"<<((float)cost_apr / cost_opt)<<endl;
    return 0;
}