algorithms/tsp.cpp at master · dekzz/algorithms · 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
#include <stdio.h>
#define MAX 100
#define INFINITY 999

int tsp_dp (int c[][MAX], int tour[], int start, int n);

int main()
{
int n; /* Number of cities. */
int i, j; /* Loop counters. */
int c[MAX][MAX]; /* Cost matrix. */
int tour[MAX]; /* Tour matrix. */
int cost; /* Least cost. */

printf ("Problem putujeceg trgovca - dinamicko programiranje.");
printf ("\nBroj gradova? ");
scanf ("%d", &n);
printf ("Unesite matricu troskova: (999: ne postoji veza)\n");
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf ("%d", &c[i][j]);

for (i=0; i<n; i++)
tour[i] = i;

cost = tsp_dp (c, tour, 0, n);

printf ("Minimalni trosak: %d.\nTour: ", cost);
for (i=0; i<n; i++)
printf ("%d ", tour[i]+1);
printf ("1\n");
}

int tsp_dp (int c[][MAX], int tour[], int start, int n)
{
int i, j, k; /* Loop counters. */
int temp[MAX]; /* Temporary during calculations. */
int mintour[MAX]; /* Minimal tour array. */
int mincost; /* Minimal cost. */
int ccost; /* Current cost. */

/* End of recursion condition. */
if (start == n - 2)
return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0];

/* Compute the tour starting from the current city. */
mincost = INFINITY;
for (i = start+1; i<n; i++)
{ for (j=0; j<n; j++)
temp[j] = tour[j];

/* Adjust positions. */
temp[start+1] = tour[i];
temp[i] = tour[start+1];

/* Found a better cycle? (Recurrence derivable.) */
if (c[tour[start]][tour[i]] +
(ccost = tsp_dp (c, temp, start+1, n)) < mincost) {
mincost = c[tour[start]][tour[i]] + ccost;
for (k=0; k<n; k++)
mintour[k] = temp[k];
}
}

/* Set the minimum-tour array. */
for (i=0; i<n; i++)
tour[i] = mintour[i];

return mincost;
}