www.pudn.com > 基于VC的神经网络开发程序包(源码).rar > tsp.cpp

/*  
 * Travelling Salesman Problem using Kohonen Map. 
 * Author: Asim Shankar 
 * http://annie.sourceforge.net 
 * 
 * This program demonstrates the solving of a travelling salesman problem 
 * using a self-organizing Kohonen map. 
 * 
 * There are 20 cities through which the salesman must cycle through. 
 * The coordinates of the cities are normalized to lie between [0,1). 
 * 
 * The Kohonen Map used is a 1 dimensional map with 40 neurons. 
 * 
 * Training is done as follows: 
 *	1. Map neurons initialized to random values. 
 *  2. Randomly select a city, and generate a random point in it's neighbourhood 
 *  3. Update the weights of the neurons using the Kohonen update rule and the point 
 *     generated above. 
 *  4. Goto step 2. Repeat until the map seems to stabalize. 
 * 
 * The tour is generated from the map as follows: 
 *	1. Feed each city (Ci) to the map and find out the winner neuron (Wi). 
 *  2. Order the cities C1...Cn according to the winners (W1...Wn). 
 *  3. The order above gives the order of visiting. 
 */ 
#include  
#include  
#include  
#include  
 
using namespace std; 
 
using namespace annie; 
 
#define NEAR 0.05		// Random points are generated around the given cities with this radius 
#define NCITIES 20		// Total number of cities 
 
real Cities[NCITIES][2] =	//The normalized coordinates of the cities 
{ 
	{0.25, 0.09}, 
	{0.60, 0.90}, 
	{0.19, 0.46}, 
	{0.93, 0.12}, 
	{0.41, 0.53}, 
	{0.10, 0.39}, 
	{0.65, 0.03}, 
	{0.07, 0.07}, 
	{0.85, 0.63}, 
	{0.57, 0.90}, 
	{0.88, 0.37}, 
	{0.34, 0.20}, 
	{0.56, 0.36}, 
	{0.39, 0.36}, 
	{0.43, 0.15}, 
	{0.62, 0.74}, 
	{0.34, 0.83}, 
	{0.26, 0.96}, 
	{0.24, 0.64}, 
	{0.91, 0.37}, 
}; 
 
//returns the Euclidean distance between city i and city j 
real getCityDistance(int i, int j)  
{ 
	real dx = Cities[i][0]-Cities[j][0]; 
	real dy = Cities[i][1]-Cities[j][1]; 
	return sqrt(dx*dx+dy*dy); 
} 
 
void makePlotFiles(KohonenMap &map,const char *citiesFile, const char *tspFile, int path[], const char *weightsFile) 
{ 
	FILE *cf,*tspf,*mapof; 
	cf = fopen(citiesFile,"w"); 
	tspf = fopen(tspFile,"w"); 
	mapof = fopen(weightsFile,"w"); 
 
	for (int i=0; i>seed; 
	cout<<"Time to train     : "; cin>>timeout; 
	srand(seed); 
 
	KohonenMap1D map(NCITIES*2,2); 
	map.init(0.8,0.995,0.8,0.995); 
	int ctr=0; 
	while (map.getTime() < timeout) 
	{ 
		int city = randomInt(0,NCITIES); 
		//int city = ctr%NCITIES; 
		ctr++; 
		real p[2]; 
		p[0] = Cities[city][0]+annie::random()*NEAR; 
		p[1] = Cities[city][1]+annie::random()*NEAR; 
		map.updateWeights(p); 
	} 
	cout<=0;i--) 
		for (int j=0;jwinners[j+1]) 
			{ 
				int t=winners[j]; 
				winners[j]=winners[j+1]; 
				winners[j+1]=t; 
 
				t=order[j]; 
				order[j]=order[j+1]; 
				order[j+1]=t; 
			} 
		} 
 
	real totalLength = 0.0; 
	for (int i=0;i>seed; 
//	cout<<"Tmax       : "; cin>>timeout; 
//	KohonenMap1D map(3,1); 
//	map.init(0.5,0.995,0.5,0.995); 
//	while (map.getTime() < timeout) 
//	{ 
//		int k = randomInt(0,6); 
//		map.updateWeights(p[k]); 
//	} 
//	 
//	for (int i=0; i<6 ;i++) 
//	{ 
//		map.setInput(p[i]); 
//		printf("%d --> %d\n",i,map.getWinner()); 
//	} 
//} 
//