[C++] Traveling Salesman Problem - Problem

[Romsl]

Hi,

ich möchte das Traveling Salesman Problem implementieren, weiß aber nicht genau wie ich das realisieren soll.

Ich habe eine Datei cities.txt

Konstanz	9.183	47.667
Muenchen	11.583	48.150
Freiburg	7.850	48.000
Aachen		6.100	50.767
Leipzig		12.333	51.300
Cottbus		14.333	51.767
Magdeburg	11.667	52.167
Berlin		13.400	52.517
Bremen		8.800	53.083
Rostock		12.133	54.083
Koeln		6.950	50.933
Dresden		13.750	51.050

Diese Datei lese ich ein in 3 verschiedene Vektoren, Städtenamen, x-coordinate, y-coordinate. Danach erstelle ich eine Matrix mit den einzelnen Abständen von den Städten zueinander.
Nun soll ich durch Eingabe von n die Anzahl der zu laufenden Wege angeben. Am Schluss soll eine summierte Strecke und die n durchlaufenen Städte herauskommen.

Mein bisheriger Ansatz

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

class TSP
{
	public:
		//vectors with city names, x-coordinate, y-coordinate
		vector<string> city_vector;
		vector<double> x_coordinate;
		vector<double> y_coordinate;
		
		double **matrix;
		
		TSP()
		{
			//empty
		}
		
		void read_file(char *file)
		{
			ifstream file_stream (file);
		
			string tmp_city;
			double tmp_x;
			double tmp_y;
		
			while(!file_stream.eof())
			{
				file_stream >> tmp_city >> tmp_x >> tmp_y;
				
				city_vector.push_back(tmp_city);
				x_coordinate.push_back(tmp_x);
				y_coordinate.push_back(tmp_y);
			}
		}
		
		int get_city_index(string city_string)
		{
			for (int i = 0; i < city_vector.size(); i++)
			{
				if (city_vector[i] == city_string)
				{
					return i;
				}
			}
		}
		
		void create_matrix()
		{
			matrix = new double*[city_vector.size()];
			
			for (int i = 0; i < city_vector.size(); i++)
			{
				matrix[i] = new double[city_vector.size()];
			}
		}
		
		void fill_matrix()
		{
			double value;
			double x_distance;
			double y_distance;
		
			for (int i = 0; i < city_vector.size(); i++)
			{
				for (int j = 0; j < city_vector.size(); j++)
				{
					x_distance = x_coordinate[j] - x_coordinate[i];
					y_distance = y_coordinate[j] - y_coordinate[i];
					
					value = sqrt(pow(x_distance, 2) + pow (y_distance, 2));
					
					matrix[j][i] = value;
				}
			}
		}
		
		~TSP()
		{
			//empty
		}
};

int main(int argc, char *argv[])
{
	if (argc == 3)
	{
		//filename with city name, x-coordinate and y-coordinate
		char *file = argv[1];
		
		//city that is the start point of the traveling salesman problem
		string city_string = argv[2];
		
		//number of steps -> visit cities
		int n;
		
		TSP *tsp = new TSP();
		tsp->read_file(file);
		cout << "index of the city in the vector: " << tsp->get_city_index(city_string) << endl;
		
		tsp->create_matrix();
		tsp->fill_matrix();
		
		return 0;
	}
	else
	{
		cerr << "wrong number of parameters" << endl;
		
		return -1;
	}
}

Gruß

Romsl

 

[MFC openGL]

Hi,

ich würde einfach jedem Standort eine ID geben, z.b. 1 2 3 .... Danach würde ich eine Liste mit all den benutzten IDs erstellen, und diese z.b. nach diesem ALGO tauschen

void swap(int anzahl, int max)  //PERMUTATION   //anzahl = anzahl der städte
{
 int puffer, k = 0;
 while(k != max)  //max ist das ergebnis der fakultät, also die maximale permutierende anzahl
 {
  for(int i = 0; i < anzahl-1; i++)
  {
   //ausgabe(anzahl);  //hier käme deine rechnung hin, also strecken berechnung
   puffer = zk[i];
   zk[i] = zk[i+1];
   zk[i+1] = puffer;  //zk ist die liste mit den zu permutierenden zahlen
   k++;
  }
 }
}
 
 
int faku(int anzahl)
{
 if(anzahl == 0)  
  return(1); 
 else   
  return(anzahl*faku(anzahl-1)); 
}

Wenn du das gemacht hast, und dir jeweils die Kombination nach dem Permutieren mit der kürzesten Strecke in eine Liste schreibst, dann brauchste nur noch die Liste anhand der IDs auslesen, und du hast dein Problem gelößt



Aber Achtung, durch die Permutation / Fakultät geht die Rechenzeit exponenziell nach oben !

Also je mehr Städte du hast, desto wesendlich länger wird die Berechnung dauern.


Hoffe trotzdem das du damit klar kommst, wenn nicht schick mir eine PN.

Gruss

MFC OpenGL

 

[Romsl]

Danke erstmal,

werds mir am Sonntag mal anschauen. Hab im Moment leider keine Zeit. Wenns nicht klappt werde ich mich dann bei dir melden.

Romsl