Travelling salesman problem

[asxxx]

Hi, I want to solve salesman problem using brute force but choosing random numbers of roads. It is random method ? So I created table with number of points [n] and matrix with locations of this points [n][2] but I dont know what next..So now I have to check for example 1000 randomly possible roads and find witch od these roads is shortest ?

[H00G0]

Hi asxxx,

I'm afraid that we are going to need to have more information before we are able to help you.

-> What problem do you want to solve, can you share at least the instruction for the task?
-> What have you tried to solve your problem and what are you having trouble with?
-> If you have started to write some code please share it so we can help you based on that at least

[asxxx]

What problem do you want to solve, can you share at least the instruction for the task?

Calculate the shortest road in travelling salesman problem using random method.

What have you tried to solve your problem and what are you having trouble with?

I have trouble with how to solve this problem using random method.

If you have started to write some code please share it so we can help you based on that at least

so far I have only two tables

[jonnin]

you have to check every possible path between 2 points that follow the rules (can't go to the same point more than once is a part of TSP) and be able to abort if an attempted path cannot get from A to B (though I think TSP is fully connected but I can't recall?).
note that even for 'only' 1000 nodes this is a HUGE number of possible paths to have to check.

lets look at 5 nodes.
a,b,c,d,e
and you want to get from a to e
you have to check a-e, a-b-e, a-c-e, a-d-e, a-b-c-d-e, a-c-b-d-e, ... and more 4 point combos.
imagine that for 1000 nodes...

[againtry]

https://www.youtube.com/watch?v=XaXsJJh-Q5Y

[asxxx]

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    srand(time(NULL));
    int N;                                                       //number of points
    cout<<"Input number of points: "<<endl;
    cin>>N;
    double ** Points = new double * [N];
    int * Road = new int [N];


    for (int i = 0; i<N; i++)
    {
    Points[i] = new double [2];                               // fill table of points randomly numbers
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<2; j++)
        {
            Points[j]=(rand()%20);                       //error:invalid conversion from int to double
        }
    }


    for (int i = 0; i<N; i++)
    {
    delete [] Points[i];
    }
    delete [] Points;
    delete [] Road;
    return 0;
}

[salem c]

> Points[j]=(rand()%20); //error:invalid conversion from int
But you started with
> double ** Points

So you need two subscripts.
You're half-way there with the nested loop.

[jonnin]

I was thinking shortest path, my above isnt right. Its cheapest to hit all once, not cheapest from a-b. you can ignore the short paths I listed. Even so its a giant number via brute force.

[asxxx]

Its cheapest to hit all once, not cheapest from a-b

Yes, I have to consider all points.
So now I want to check every possible length each permutation but how to create permutation in c++?

[dutch]

Generating permutations.

#include <iostream>
#include <algorithm>

void print(const int *a, int n) {
    for (int i = 0; i < n; ++i) std::cout << a[i] << ' ';
    std::cout << '\n';
}
 
int main() {
    int n;
    std::cout << "Number of points: ";
    std::cin >> n;

    auto a = new int[n];
    std::iota(&a[0], &a[n], 0); // fill with values 0 to n-1

    do {
        print(a, n);
    } while(std::next_permutation(&a[0], &a[n])); // calculate next lexicographic permutation
}

[jonnin]

swaps.
if you have nodes: 1 2 3 4
start there:
1 2 3 4
4 2 3 1 //swap, in the original, first and last
1 4 3 2 //swap, in orig, second and last
1 2 4 3 //swap third and last.
now you have to do the third for each of the above.
for 1234
3214
1324
for 4231
3241
4321
... and on and on.

or you can generate them. This is faster than swapping, but swapping may be easier to see and understand? Think of it like how you count in hex, except you can't have duplicates.
00 //bad, dupe
01
02
03
...
0f
10
11 //bad, dupe... there is a pattern here
12
..
1d
1e
1f
20
21
22//bad, dupe..
...

remember you only need to store the cheapest combo. get the score for the first one, then when you find a score lower, save what permutation that is, until you have checked them all. you don't need to store all this stuff, just generate, evaluate, and move on.
then try the greedy algorithm started once from each node. Compare time taken and answer.

[dhayden]

If you're storing values 0-20 in points, then when is it a double?

Rather than doing your own memory management, use vectors:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;

struct Point {
    double x = {};
    double y = {};
};

int main()
{
    srand(time(NULL));
    int N;                                                       //number of points
    cout<<"Input number of points: "<<endl;
    cin>>N;
    vector<Point> points(N);
    vector<int> roads(N);

    for(int i=0; i<N; i++)
    {
        points[i].x=(rand()%20);
        points[i].y=(rand()%20);
    }
    return 0;
}

[George P]

If you are going to write C++ code, don't use the C library to generate random numbers. Use <random> instead.

http://www.cplusplus.com/reference/random/

Learning to use the features may take a bit of time, but it is worth the effort.

Using rand() is at best sloppy and biased.

https://web.archive.org/web/20180123103235/http://cpp.indi.frih.net/blog/2014/12/the-bell-has-tolled-for-rand/

https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful

Even the C standard recommends NOT using rand() if there are alternatives. C++ does have them.

*GIANT middle finger to the reporting troll, NYAH!*

[asxxx]

I create permute function so far ad trying to calculate lenghts between points in each permutation

void permute(int a[], int l, int r,double **Points)
{
  int d=0;
    if (l == r)
    {
     for(int i=0,j=i+1; i<r+1,j<r+1; i++,j++)
     {
        // cout<<a[i]<<" ";

         d=d+sqrt(pow(Points[i][0]-Points[j][0],2)+pow(Points[i][1]-Points[j][1],2));
         cout<<d<<endl;
     }
         cout<<endl;
    }
    else
    {

        for (int i = l; i <= r; i++)
        {

            swap(a[l], a[i]);


            permute(a, l+1, r,Points);

            swap(a[l], a[i]);
        }
    }
}

[Duthomhas]

Why was Furry Guy reported?


[edit]
BTW, you want to brute-force 1000 vertices?
What supercomputer farm are you planning to use?
Because brute-forcing that will take you several years.

[againtry]

Yeah brute force is definitely a challenge - to say the least.

Trouble with thinking it can be done is Prof Sedgwick probably knows about it already and therefore would be teaching and publishing it.

This exercise with 1000 (even !!) provides the data along with a discussion and guidance:
https://www.cis.upenn.edu/~cis110/13sp/hw/hw08/tsp.shtml

There are one or two papers on using random methods, but it doesn't appear to be relevant to OP's (vague) problem specification.

Good luck with brute force though :)

[jonnin]

the method I gave is very good and very simple to code. It may even give the best answer for fully connected problems (not 100% sure), but it fails to find the best on partially connected (I know this is true). Fail to find best still gives a pretty good answer.

[asxxx]

Why was Furry Guy reported?

I dont know. I dont report him.

[Duthomhas]

Ah, I get reported too, LOL.

@asxxx, is the link posted by againtry your assignment? Because that is definitely not brute-force.

The reason that Travelling Salesman is NP-hard is because doing it by brute-force is impractical, and the way to optimize the problem is not known or, as far as we can tell, possible to do.

Hence, we look for a good-enough way to do it quickly.

[George P]

@Duthomhas,

I've given up trying to figure out why some trollish fool reports me or others. The "slaughter" in the Lounge is more than enough of foolish idiocy to make me utterly indifferent to the whims of morons.

Maybe I was reported for suggesting to use C++ libraries when writing new C++ code instead of using outdated C libraries and ways to craft code.

You likely were reported as well because you "defended" me. *shrug*

I didn't even mention another C++ vs. C "issue," dynamic container arrays. *cough*std::vector*cough*