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).
- Rejestracja:prawie 8 lat
- Ostatnio:prawie 8 lat
0
- Rejestracja:ponad 8 lat
- Ostatnio:około godziny
- Lokalizacja:U krasnoludów - pod górą
- Postów:4707
0
Na szybkiego - to jest do zrobienia w godzinę jak masz sieć około tryliona komputerów.
- Rejestracja:prawie 8 lat
- Ostatnio:prawie 8 lat
0
@jarekr000000. Nie chodzi mi o znalezienie optymalnej trasy, ale jak najbliższej optymalnej.
jarekr000000
No nie tak to sformułowałeś. To kolejne sformułowanie tez nie jest dobre. Ale jak po prostu szukasz dość dobrej trasy:
http://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/ ("never more than twice the cost of best possible output.")
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);
}
edytowany 1x, ostatnio: hauleth
Pod warunkiem, że mamy graf pełny. W przeciwnym wypadku szybko jesteśmy w stanie znaleźć graf, w którym ten algorytm nie da żadnego wyniku.
no ale akurat tu jest pełny
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);
}
edytowany 1x, ostatnio: hauleth
- Rejestracja:prawie 8 lat
- Ostatnio:ponad 4 lata
- Postów:26
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;
}
- data.txt (1 KB) - ściągnięć: 147