Permutation Problem

[Gabriel Campos]

I'm having a problem creating a code for the Travelling Salesman Problem using the Brute Force solution (as instructed by my teacher). I have to read a file that contains the euclidean position of n cities (n is defined on the file) and I have to calculate the distance between each of them, store the distances in a matrix, then calculate the shortest path.
When n is a even number (in this case 10, 12 and 14) the calculations run smoothly and I get the right shortest path, when n is a odd number (11 or 13) my program crashes.
Does anyone know why that is happening?

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <fstream>
#include <algorithm>
using namespace std;

struct Cidade
{
    int x;
    int y;
};

void atribuidistancias(float **matriz, Cidade *c, int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            matriz[i][j] = sqrt(pow((c[i].x - c[j].x), 2) + pow((c[i].y - c[j].y), 2));
            //cout << matriz[i][j] << " ";
        }
        cout << endl;
    }
}

float distanciadoVetor(float **matriz, int *v, int n)
{
    float distanciatemp = 0;
    for(int c = 0; c < n-1; c++)
    {
        int o = v[c];
        int p = v[c+1];
        if(p > o)
        {
            distanciatemp = distanciatemp + matriz[p][o];
        }
        else
        {
            distanciatemp = distanciatemp + matriz[o][p];
        }
    }

    int o = v[n-1];
    int p = v[0];
    if(p > o)
    {
            distanciatemp = distanciatemp + matriz[p][o];
    }
    else
    {
            distanciatemp = distanciatemp + matriz[o][p];
    }

    return distanciatemp;
}

float calculaMenorViagem(int *v, int n, float **matriz, int *vetmenor)
{
    std::sort(v, v + (n-1));
    float distancia = distanciadoVetor(matriz, v, n);

    do
    {
        if(distancia > distanciadoVetor(matriz, v, n))
        {
            distancia = distanciadoVetor(matriz, v, n);
            for(int s = 0; s < n; s++)
            {
                vetmenor[s] = v[s];
            }
        }
    }while(std::next_permutation(v, v + (n-1)));

    return distancia;
}

int main()
{
    int n;
    Cidade *c;
    char ccf;
	char cc[150];
	int z, x, y;
	ifstream file;

    cout << "File name: ";
	gets(cc);
	fflush(stdin);

	file.open(cc);
	if(file.is_open())
    {
        file >> ccf >> ccf >> n;
        file >> ccf >> ccf;

        c = new Cidade[n];

        for(int i = 0; i < n; i++)
        {
            file >> z >> ccf >> x >> y;
            c[i].x = x;
            c[i].y = y;
        }
    }

    float **matriz = new float *[n];
    for(int e = 0; e < n; e++)
    {
        matriz[e] = new float [e+1];
    }

    int *v = new int [n-1];

    for(int a = 0; a < n; a++)
    {
        v[a] = a;
    }
    cout << endl;

    for(int i = 0; i < n; i++)
    {
        cout << i << ": (" << c[i].x << "," << c[i].y << ")\n";
    }
    cout << endl;

    atribuidistancias(matriz, c, n);

    int *vetmenor = new int [n];

    cout << "Smaller distance between the " << n << " cities: " << calculaMenorViagem(v, n, matriz, vetmenor) << endl;
    cout << "Travelling order: ";
    for(int e = 0; e < n; e++)
    {
        cout << vetmenor[e] << " -> ";
    }
    cout << vetmenor[0] << endl;
}

[ne555]

http://www.cplusplus.com/forum/general/112111/

By the way, you shouldn't use `gets()' (see bugs http://linux.die.net/man/3/gets )

[histrungalot]

I was unable to reproduce you crashing but I believe your issue is line 114

int *v = new int [n-1]; // <------- n-1 is BAD!! .

Make it
int *v = new int [n]; // <------- n is GOOD!! .

Other places in the code you index beyond that amount of memory you allocated. In fact the for loop right after that you index to n which could be causing your crash. The program seems to work but you are not checking all of the permutation because you are going from v to v + (n-1). This should be v to v+n. If you check the permutation with 3 cities, your do while loop in calculaMenorViagem only tries two permutation when it should be 3! or 6:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

do { // --------------------------------------- // Adding debug so you can see // what is going on for (int i(0);i<n;i++) cout << v[i] << " -> "; cout << endl; if(distancia > distanciadoVetor(matriz, v, n)) { distancia = distanciadoVetor(matriz, v, n); for(int s = 0; s < n; s++) { vetmenor[s] = v[s]; } } }while(std::next_permutation(v, v + (n-1)));

$ ./a.out warning: this program uses gets(), which is unsafe. File name: campos.txt 0: (1,1) 1: (2,4) 2: (1,7) 0 -> 1 -> 2 -> 1 -> 0 -> 2 -> Smaller distance between the 3 cities: 12.3246 Travelling order: 1 -> 0 -> 2 -> 1

Also, in calculaMenorViagem if the first path is the shortest you don't save the value in the vetmenor array. Because then the distancia is set to the shortest and the second call to distanciadoVetor is going to be equal and the if check is not going to be true. Do this float distancia = std::numeric_limits<float>::max();. Now if the first path is the shortest you will set the vetmenor array.
Moving back to your crashing, if I change line 114 and free all of the dynamic memory and compute the correct number of permutation I get:

Check out valgrind: http://valgrind.org/docs/manual/quick-start.html

~/code/c++$ valgrind ./a.out
==2969== Memcheck, a memory error detector
==2969== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==2969== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==2969== Command: ./a.out
==2969== 
File name: campos.txt

0: (2,4)
1: (1,7)
2: (1,1)
3: (3,10)
4: (1,3)
5: (4,4)
6: (3,3)
7: (1,2)
8: (2,2)
9: (5,5)
10: (4,9)

Smaller distance between the 11 cities: 21.3762
Travelling order: 0 -> 1 -> 3 -> 10 -> 9 -> 5 -> 6 -> 8 -> 2 -> 7 -> 4 -> 0
==2969== 
==2969== HEAP SUMMARY:
==2969==     in use at exit: 0 bytes in 0 blocks
==2969==   total heap usage: 22 allocs, 22 frees, 9,344 bytes allocated
==2969== 
==2969== All heap blocks were freed -- no leaks are possible
==2969== 
==2969== For counts of detected and suppressed errors, rerun with: -v
==2969== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

You could also make the function distanciadoVetor easier if you make matriz a n x n matrix. Then you would just have to lookup the indices.