Travelling salesman problem

[dutch]

Don't even try to look for meaning in it. It's arbitrary. I got tagged in another thread for no conceivable reason. But reporting has always been essentially meaningless except for removing first-time posters, which is handy for spam.

[againtry]

FWIW, Google OR-tools discusses TSP
https://developers.google.com/optimization

[asxxx]

That is program which solving salesman problem? I can find the shortest road using brute force but max for ten points.. So far I dont use <random> because I dont know how to use it..

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{

    srand(time(NULL));
    int N;
    double d;
    int s=0;
    int m;

    cout<<"Input number of points: "<<endl;
    cin>>N;
    int * Route = new int [N];
    double ** Points = new double * [N];
    int * Road = new int [N];
      for(int i=0; i<N; i++)
      {
         Road[i]=i;
      }

    for (int i = 0; i<N; i++)
    {
    Points[i] = new double [2];
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<2; j++)
        {
            Points[i][j]=(rand()%20);
        }
    }

      sort(Road,Road+N);


  do {

      for(int i=0, j=1; i<N-1,j<N; i++,j++)
      {

         d=sqrt(pow(Points[Road[i]][0]-Points[Road[j]][0],2)+pow(Points[Road[i]][1]-Points[Road[j]][1],2));
         s+=d;

      }
         s+=sqrt(pow(Points[Road[N-1]][0]-Points[Road[0]][0],2)+pow(Points[Road[N-1]][1]-Points[Road[0]][1],2));

         if(s<m)
         {
             m=s;
             for(int k=0; k<N; k++)
             {
                 Route[k]=Road[k];
             }
         }
         s=0;
         d=0;
  } while (next_permutation(Road,Road+N));

   cout<<"The shortes route is: "<<m<<endl;
   for(int k=0; k<N; k++)
   {
       cout<<Route[k]<<" ";
   }


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

[jonnin]

this site has plenty of examples on how to use <random> in the reference area.

I still believe what I gave you is better than anything that uses rand.
Making your code do all that work to find the costs is slowing you down even more. Its much faster to just give the costs to each connection when you make the problem, rather than compute it over and over … or at the very least find a way to compute it once only per connection somehow. Also note that X*X is notably faster than pow(X,2).

[Duthomhas]

Er, the very first thing you should do with every point you get is insert it into the “tour” (ordered, circular list of points, which you are calling the “Route”) using the Nearest Neighbor heuristic.

To perform Nearest Neighbor, insert your new point next to the closest point in the tour.

All TSP solvers start using that (or some similarly greedy heuristic).


Nearest Neighbor works pretty well over randomized data anyway. You may consider yourself done if that is good enough. Otherwise you might want to next apply the 2-opt heuristic to uncross lines in the tour.

Find any two line segments in the tour that cross each other, remove the lines, reverse the points in the disconnected subgraph, then reconnect.

Hope this helps.