fork download
copy 
  1. /**
  2.  * Autor:	Krzysztof Tatarynowicz
  3.  * Indeks:	221497
  4.  *
  5.  * Lista 1 - Travelling Salesman Problem
  6.  *
  7.  * 1.	Założenia i działanie
  8.  *
  9.  * 		Algorytm służy do wyznaczania trasy dla  komiwojażera.
  10.  *		Program otrzymuje na standardowe wejście  plik,  który
  11.  *		zawiera miasta wraz z ich współrzędnymi rzeczywistymi.
  12.  *		Program zwraca na standardowe wyjście  łączną  długość
  13.  *		trasy, wygenerowanej przez  program.   Na  standardowe
  14.  *		wyjście błędów program zwraca wierzchołki miast  doce-
  15.  *		lowych wraz z odległościami do nich, zgodnie ze  sche-
  16.  *		matem:
  17.  *
  18.  * 		x -> y (A.BCD...)
  19.  *
  20.  * 		gdzie x i y to etykiety miast, a A, B, C i D to  cyfry
  21.  * 		tworzące  liczbę  rzeczywistą   stanowiącą   odległość
  22.  * 		między miastami x i y.
  23.  * 
  24.  * 2.	Realizacja
  25.  *
  26.  * 2.	1.	Opis
  27.  * 			
  28.  * 			Algorytm działa na zasadzie wyboru najbliższego sąsiada,
  29.  * 			to jest miasta, które nie zostało jeszcze odwiedzone, a
  30.  * 			ma najkrótszą odległość doń.
  31.  *
  32.  * 2.	2.	Lista TABU
  33.  *
  34.  * 			Listę TABU standardowo stanowią miasta,  które  zostały
  35.  * 			odwiedzone i nie powinno się ich więcej brać pod  uwagę
  36.  * 			wyznaczając  trasę.  W  programie  lista  TABU  została
  37.  * 			zaimplementowana przez kopię listy miast. Z  tej  kopii
  38.  * 			kolejno usuwa się miasta, które zostały  rozpatrzone  i
  39.  * 			uwzględnione w trasie.
  40.  * 			
  41.  * 2.	3.	Uproszczony schemat
  42.  *
  43.  * 			Algorytm tworzy listę miast ze współrzędnymi. Potem tworzy
  44.  * 			dwuwymiarową tablicę odległości między  miastami  (tablica
  45.  * 			jest rozmiaru N x N, gdzie N to liczba wszystkich  miast).
  46.  * 			Następnie tworzy kopię listy miast i pracując na tej kopii
  47.  * 			w pętli:
  48.  * 			
  49.  *				1)	jeśli to pierwsza iteracja, to ustawia wskaźnik  na  ostatnie
  50.  *					rozpatrywane miasto jako pierwsze (etykieta '1') i kończy ten
  51.  *					przebieg pętli (continue)
  52.  *
  53.  *				2)	w kolejnej pętli znajduje miasto, do którego   ma   najbliżej
  54.  *					(korzystając  z  dwuwymiarowej  tablicy   odległości),   przy
  55.  *					okazji zwiększa zmienną-akumulator o wartość  tej  odległości
  56.  *
  57.  * 				3)	po  znalezieniu  takiego  miasta  ustawia  je  jako  ostatnio
  58.  * 					rozpatrywane
  59.  * 
  60.  */
  61.  
  62. // Includes
  63. #include <iostream>
  64. #include <string>
  65. #include <vector>
  66. #include <cmath>
  67. #include <cstdlib>
  68. #include <ctime>
  69. #include <stdio.h>
  70.  
  71. // City class
  72. class City
  73. {
  74. 	public:
  75. 		int label;
  76. 		float x;
  77. 		float y;
  78. 		float distance;
  79. 		bool visited;
  80. 		std::vector<City> nbrs;
  81. };
  82.  
  83. // Define namespace
  84. using namespace std;
  85.  
  86. /**
  87.  * Globals and constants
  88.  */
  89. #define STARTING_LABEL		1		// label of city to start from
  90. #define UNDEFINED			0		// undefined target city (auxiliary constant)
  91.  
  92. /**
  93.  * Sorting compare
  94.  */
  95.  
  96. /**
  97.  * Method returning length of a randomized route
  98.  * @param cities Vector of cities to travel
  99.  * @param matrix Matrix of distances between cities
  100.  */
  101. float GetRandomRoute( vector <City> cities, vector <vector <float> > matrix )
  102. {
  103. 	// The length
  104. 	float len = INFINITY;
  105.  
  106. 	// Copy of the cities vector
  107. 	vector <City> copy = cities;
  108.  
  109. 	// Last city index considered
  110. 	int last = -1;
  111.  
  112. 	// Label of last considered city
  113. 	int lablast = -1;
  114.  
  115. 	// Ziarno losowości oparte na czasie
  116. 	srand( time( NULL ) );
  117.  
  118. 	// Randomize the route
  119. 	while( (int) copy.size() > 0 )
  120. 	{
  121. 		// Random number between [0, copy.size())
  122. 		int rand = std::rand() % copy.size();
  123.  
  124. 		// If there's no last - it's the first iteration
  125. 		if( last == -1 ) len = 0.0;
  126.  
  127. 		// Else get the distance between the last
  128. 		// and the currently considered city
  129. 		else
  130. 		{
  131. 			len += matrix.at( lablast - 1 ).at( copy.at( rand ).label - 1 );
  132. 			cout << lablast << " -> " << copy.at( rand ).label << " (" << matrix.at( lablast - 1 ).at( copy.at( rand ).label - 1 ) << ")" << endl;
  133. 		}
  134.  
  135. 		// Set last city as the currently considered
  136. 		last = rand;
  137.  
  138. 		// Set the label of last conisdered city
  139. 		lablast = copy.at( rand ).label;
  140.  
  141. 		// Remove that city from the copy vector
  142. 		copy.erase( copy.begin() + rand );
  143. 	}
  144.  
  145. 	// Include the travel from last considered city
  146. 	// to the first one
  147. 	len += matrix.at( last ).at( 0 );
  148.  
  149. 	// Return the length
  150. 	return len;
  151. }
  152.  
  153. /**
  154.  * Travelling Salesman function to find the shortest route
  155.  * @param cities Vector of cities to travel
  156.  * @param matrix Matrix of distances between cities
  157.  */
  158. float TravellingSalesman( vector <City> cities, vector <vector <float> > matrix )
  159. {
  160. 	// The shortest distance from city i to city j
  161. 	float shortest;
  162. 	float len = 0;
  163.  
  164. 	// Result vector of cities
  165. 	vector <City> result;
  166.  
  167. 	// Get the matrix size
  168. 	int size = matrix.size();
  169.  
  170. 	// Create vector of targets for each city
  171. 	// Target is a city to travel from considered city
  172. 	vector <int> target( size );
  173.  
  174. 	// Initialize the vector of targets
  175. 	for( int i = 0; i < size; i++ )
  176. 	{
  177. 		target.at( i ) = UNDEFINED;
  178. 	}
  179.  
  180. 	cities.at( 0 ).visited = true;
  181.  
  182. 	// Start from the STARTING_LABEL
  183. 	int curr_id = STARTING_LABEL - 1;
  184. 	int next_id = 0;
  185. 	City curr = cities.at( curr_id );
  186.  
  187. 	// Fill the result vector
  188. 	while( (int) result.size() < size )
  189. 	{
  190. 		// Insert current city to the results
  191. 		result.push_back( curr );
  192.  
  193. 		// Initialize shortest distance
  194. 		shortest = INFINITY;
  195.  
  196. 		// Find nearest neighbour
  197. 		for( int i = 0; i < size; i++ )
  198. 		{
  199. 			// The same target as start
  200. 			if( i == curr_id ) continue;
  201.  
  202. 			// Is already target of another city
  203. 			if( cities.at( i ).visited == true ) continue;
  204.  
  205. 			// Get distance to the i-th city
  206. 			float dist = matrix.at( curr_id ).at( i );
  207.  
  208. 			if( dist < shortest )
  209. 			{
  210. 				// If the current city had a target city
  211. 				// then remove it
  212. 				if( target.at( curr_id ) != UNDEFINED )
  213. 				{
  214. 					cities.at( target.at( curr_id ) ).visited = false;
  215. 					target.at( curr_id ) = UNDEFINED;
  216. 				}
  217.  
  218. 				// Found the nearest neighbour
  219. 				shortest = dist;
  220. 				target.at( curr_id ) = i;
  221. 				next_id = i;
  222. 				cities.at( i ).visited = true;
  223. 			}
  224. 		}
  225.  
  226. 		// Switch the currently considered city
  227. 		curr_id = next_id;
  228. 		curr = cities.at( curr_id );
  229. 	}
  230.  
  231. 	// Also push the first city at the end of the result vector
  232. 	// as it is the ending point of the travel
  233. 	result.push_back( cities.at( STARTING_LABEL - 1 ) );
  234.  
  235. 	// Calculate total length
  236. 	for( int i = 0; i < size; i++ )
  237. 	{
  238. 		int from = result.at( i ).label - 1;
  239. 		int to = result.at( i + 1 ).label - 1;
  240.  
  241. 		len += matrix.at( from ).at( to );
  242.  
  243. 		// Console out the route
  244. 		cerr << from + 1 << " -> " << to + 1 << " (" << matrix.at( from ).at( to ) << ")" << endl;
  245. 	}
  246.  
  247. 	// cout << endl;
  248.  
  249. 	// Console out the total length
  250. 	// cout << len << endl;
  251. 	return len;
  252. }
  253.  
  254. // Calculate euclidean distance
  255. float GetEuclideanDistance( City a, City b )
  256. {
  257. 	float ax = a.x;
  258. 	float ay = a.y;
  259. 	float bx = b.x;
  260. 	float by = b.y;
  261. 	float dx = ax - bx;
  262. 	float dy = ay - by;
  263.  
  264. 	return sqrt( (dx * dx) + (dy * dy) );
  265. }
  266.  
  267. /**
  268.  * Main function
  269.  */
  270. int main( int argc, char **argv )
  271. {
  272. 	int city, count, size;
  273. 	float x;
  274. 	float y;
  275. 	vector <City> cities;
  276.  
  277. 	// Get the first line from stdin
  278. 	scanf( "%d", &count );
  279. 	size = count;
  280.  
  281. 	// Create matrix [count] x [count]
  282. 	vector <vector <float> > matrix( size );
  283.  
  284. 	// Save the cities with their coordinates
  285. 	while( count-- )
  286. 	{
  287. 		City new_city;
  288.  
  289. 		scanf( "%d %f %f", &city, &x, &y );
  290.  
  291. 		new_city.label = city;
  292. 		new_city.x = x;
  293. 		new_city.y = y;
  294. 		new_city.visited = false;
  295.  
  296. 		cities.push_back( new_city );
  297. 	}
  298.  
  299. 	// Prepare the matrix
  300. 	for( int i = 0; i < size; i++ )
  301. 	{
  302. 		vector <float> dists( size );
  303. 		matrix.at( i ) = dists;
  304. 	}
  305.  
  306. 	// Calculate distances between cities and save them into
  307. 	// the matrix
  308. 	for( int i = 0; i < size; i++ )
  309. 	{
  310. 		for( int j = 0; j < size; j++ )
  311. 		{
  312. 			if( i == j )
  313. 			{
  314. 				matrix.at( i ).at( j ) = 0.0;
  315. 				continue;
  316. 			}
  317.  
  318. 			City a, b;
  319. 			a = cities.at( i );
  320. 			b = cities.at( j );
  321.  
  322. 			float dist = GetEuclideanDistance( a, b );
  323.  
  324. 			matrix.at( i ).at( j ) = dist;
  325. 			matrix.at( j ).at( i ) = dist;
  326. 		}
  327. 	}
  328.  
  329. 	// Run the travelling salesman
  330. 	float regular = TravellingSalesman( cities, matrix );
  331.  
  332. 	/*
  333. 	Random generating is worse idea...
  334. 	cout << endl << "Random: " << endl;
  335. 	float random1 = GetRandomRoute( cities, matrix );
  336. 	*/
  337. 	cout << regular << endl;
  338.  
  339. 	// Return from main
  340. 	return 0;
  341. }
Success #stdin #stdout #stderr 0s 2896KB
comments (?)
stdin
copy 
13
1 2.1 1.835
2 2.104 2.64
3 0.591 1.96
4 7.95591 2.642
5 1.025 4.97
6 1.167 1.53
7 1.1912 1.0439
8 3.169 1.9
9 1.09 0.3949
10 -1.10256 3.98
11 -4.0073 -1.358
12 1.01979 1.8
13 3.2322 -1.177
stdout
copy 
38.0133
stderr
copy 
1 -> 2 (0.80501)
2 -> 8 (1.29685)
8 -> 6 (2.0359)
6 -> 12 (0.307524)
12 -> 3 (0.457669)
3 -> 7 (1.09521)
7 -> 9 (0.656843)
9 -> 13 (2.65705)
13 -> 4 (6.07439)
4 -> 5 (7.31144)
5 -> 10 (2.34662)
10 -> 11 (6.07715)
11 -> 1 (6.89162)
https://ideone.com/f93Jxl
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!