Problem komiwojażera

0

Dzień dobry.
Mam dane 100 miast, każde o współrzędnych X i Y, moim zadaniem jest znaleźć jak najkrótszą trasę łączącą wszystkie miasta. Orientuje się może ktoś, który algorytm sprawdziłby się najlepiej, jeśli maksymalny czas jaki się może wykonywać wynosi 1h (na zwykłym laptopie).

0

Na szybkiego - to jest do zrobienia w godzinę jak masz sieć około tryliona komputerów.

0

@jarekr000000. Nie chodzi mi o znalezienie optymalnej trasy, ale jak najbliższej optymalnej.

0

No to lecisz z (meta)heurystykami.
Algorytmy genetyczne, mrówkowy, wyżarzanie... I szukasz minimum (choć najpewniej lokalnego).

0

Algorytm najbliższego sąsiada daje zwykle niemal optymalne wyniki:

// --------- obliczymy przybliżenie min. drogi -------
double bestn(int k) // zaczynamy od k i dalej szukamy najbliższych
{
  for(int i = 0; i < n_pts; i++) ti[i] = 0;
  ti[k] = 1;

  double tr = 0;

  TFPoint *p = pts+k;
  for(int i = 1; i < n_pts; i++)
  {
   int nxt;
   double mx = 1e6, d;
   for(int j = 0; j < n_pts; j++)
    if( !ti[j] && (d = dist(p, pts+j)) < mx )
    {
      mx = d;
      nxt = j;
    }

   tr += mx;
   p = pts+nxt;
   ti[nxt] = i+1;
  }
 return tr+dist(pts+k, p);
}

0

Prosta metoda wyżarzania (aniling) dla problemu tsp daje dużo lesze wyniki:

#define TFACTR  0.9

void aniling(int *iorder, int ncity)
{
  int nover,nlimit,i1,i2;
  static int n[7];
  float path,de,t;

  nover = 100*ncity; //Maximum number of paths tried at any temperature.
  nlimit = 10*ncity; //Maximum number of successful path changes before continuing.

  t = 0.5*MAX_XY;

 for(int j = 1; j <= 100; j++) // Try up to 100 temperature steps.
  {
   int nsucc = 0, nn;
   for(int k = 1; k <= nover; k++)
   {
    do{
       n[1] = 1+(int)(ncity*randf());     // Choose beginning of segment
       n[2] = 1+(int)((ncity-1)*randf()); // ..and.. end of segment.
       if( n[2] >= n[1] ) ++n[2];
       nn = 1+((n[1]-n[2]+ncity-1) % ncity); //nn is the number of cities not on the segment.
     }while( nn < 3);

                   // Decide whether to do a segment reversal or transport.
    if( flip() )   // Do a transport.
     {
      n[3] = n[2]+(int)(abs(nn-2)*randf())+1;
      n[3] = 1+((n[3]-1) % ncity); // Transport to a location not on the path.
      de = trncst(iorder,ncity,n); // Calculate cost.

      if( metrop(de,t) )  // Consult the oracle.
       {
        ++nsucc;
        trnspt(iorder,ncity,n); // Carry out the transport.
       }
     }
    else   // Do a path reversal.
     {
      de = revcst(iorder,ncity,n); // Calculate cost.

      if( metrop(de,t) )
       {
         ++nsucc;
         reverse(iorder,ncity,n); // Carry out the reversal.
       }
     }

    if( nsucc >= nlimit ) break; // Finish early if we have enough successful changes.
   }

//   printf("\n %s %10.6f %s %12.6f \n","T =",t," Path Length =",path);
//   printf("Successful Moves: %6d\n",nsucc);
   t *= TFACTR; // Annealing schedule.
   if( nsucc == 0 ) return; // If no success, we are done.
  }
}

void doaniling(int *p)
{
  int *ix = ti+n_pts+1;
  for(int i = 1; i <= n_pts; i++) ix[i] = *p++;

//  aproxt = droga(ix+1);

  aniling(ix, n_pts);

  anilingt = droga(ix+1);
}
0

Może się komuś przyda. Najkrótsza ścieżka wynosi coś w granicach 756, a tym algorytmem udało mi się osiągnąć 770 (jest to proste wyżarzanie z przełączaniem 2-opt)

#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cfloat>
#include <cstdio>
#include <cstdlib>
#include <ctime>

float calculateDistanceBetweenPoints(int x1, int y1, int x2, int y2) {
	return sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}

double calculateDistance(std::vector<int> &vecI, std::vector<int> &vecX, std::vector<int> &vecY) {
	double distance = 0;
	int i;
	for (i = 0; i < vecI.size() - 1; i++) {
		distance += calculateDistanceBetweenPoints((int)vecX[vecI[i] - 1], (int)vecY[vecI[i] - 1], (int)vecX[vecI[i + 1] - 1], (int)vecY[vecI[i + 1] - 1]);
	}
	distance += calculateDistanceBetweenPoints((int)vecX[vecI[i] - 1], (int)vecY[vecI[i] - 1], 0, 0);
	return distance;
}

void generate(std::vector<int> &vec, int x, int y) {
	int max;
	int min;
	if (x > y) {
		max = x;
		min = y;
	}
	else {
		max = y;
		min = x;
	}
	std::vector<int> tempVec;
	tempVec = vec;
	for (int i = min; i <= max; i++) {
		vec[i] = tempVec[max + min - i];
	}

}

int main() {
	double vectorX_distance = DBL_MAX;
	double vectorY_distance = DBL_MAX;
	srand(time(NULL));
	int i, x, y;
	std::vector<int> vecI, vecX, vecY;
	std::vector<int> vectorY, vectorX, vextorX1;

	std::ifstream infile("data.txt");
	while (infile >> i >> x >> y) {
		vecI.push_back(i);
		vecX.push_back(x);
		vecY.push_back(y);
	}

	double temperature = 1000.0;
	double coolingRate = 0.9999;
	double absoluteTemperature = 0.005;

	i = 0;
	vextorX1 = vecI;
	while (temperature > absoluteTemperature) {
		int random1 = rand() % vextorX1.size();
		int random2 = rand() % vextorX1.size();
		vectorX = vextorX1;

		//generuje nowy
		vectorY = vectorX;
		generate(vectorY, random1, random2);

		vectorX_distance = calculateDistance(vectorX, vecX, vecY);
		vectorY_distance = calculateDistance(vectorY, vecX, vecY);
		if (vectorX_distance > vectorY_distance) {
			vextorX1 = vectorY;
		}

		else {
			if (((double)rand() / (RAND_MAX)) < pow(M_E, -(vectorY_distance - vectorX_distance) / temperature)) {
				vextorX1 = vectorY;
			}
			else {
				vextorX1 = vectorX;
			}
		}
		if (i % 1000 == 0) {
			std::cout << "\nIlosc iteracji: " << i << "\tNajkrotszy dystans: " << calculateDistance(vextorX1, vecX, vecY) << "\ttemperatura: " << temperature << std::endl;
		}
		i++;
		temperature *= coolingRate;
	}
	//system("pause");
	return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1