wstsp.cpp

开发环境：Visual C++ .net2003 功能：利用遗传算法求解TSP问题。

}
/*
功能：获取当前城市编号的前一个城市编号
输入：城市序列-->CityOrderDef 当前城市号-->INT
输出：当前城市的前一个城市编号-->INT
错误：输出结果为-1；
*/
INT  WSTSP::GetLeftIndex_Greedy(CityOrderDef _CityOrder, INT _CurCityNum)
{
	INT l_CityNum = _CityOrder.size();
	INT i;
	BOOL l_Find = FALSE;
	for(i = 0; i < l_CityNum; ++i)
	{
		if(_CurCityNum == _CityOrder[i])
		{
			l_Find = TRUE;
			break;
		}
	}

	if(l_Find)
	{
		if(i == 0) return _CityOrder[l_CityNum-1];
		else return _CityOrder[i - 1];
	}

	return -1;
}

/*
功能：获取指定城市(编号)在访问序列中的位序
输入：城市序列-->CityOrderDef 城市号-->INT
输出：当前城市编号-->INT
错误：输出结果为-1；
*/
INT WSTSP::GetCityIndex(CityOrderDef _CityOrder, INT _CurCityNum)
{
	INT l_CityNum = _CityOrder.size();
	INT i;
	BOOL l_Find = FALSE;
	for(i = 0; i < l_CityNum; ++i)
	{
		if(_CurCityNum == _CityOrder[i])
		{
			l_Find = TRUE;
			break;
		}
	}

	if(l_Find) return i;

	return -1;
}
BOOL WSTSP::Show(CityOrderDef _Order)
{
	//INT j;
	//printf("************************************************************\n");
	//printf("+++TSP路径：");
	//for(j = 0; j < _Order.size(); ++j)
	//{
	//	printf("%d ", _Order[j]);
	//}
	//printf("\n");

	return TRUE;
}
/*
功能：获取与某城市最近的城市序号
输入：城市信息--->_CityInfo 城市-->_City 
输出：最近城市序列-->_CitySerial[] 
错误（输出TRUE or FALSE）：处理的结果正确与否 
Time：2007-06-20
*/
BOOL WSTSP::GetShortestCities(CityInfo &_CityInfo,  INT _City, INT *_CitySerial, INT _ShortestCityNum)
{
	INT i = 0;
	if( _ShortestCityNum > _CityInfo.m_CityNum-1 ) return FALSE;
	if(_City > _CityInfo.m_CityNum - 1) return FALSE;

	//先将该城市到各城市的距离算出来
	PFLOAT l_City_Dists = new FLOAT[_CityInfo.m_CityNum];
	for(i = 0; i < _CityInfo.m_CityNum; ++i)
	{
		l_City_Dists[i] = WSTSP::CityDistance(_CityInfo.m_pCities[_City], _CityInfo.m_pCities[i]);
		//printf("%d-->%f \n", i, l_City_Dists[i]);
	}	

	//先预选几个城市序列
	INT j = 0;
	INT k = 0;
	i = 0;
	while( i < _ShortestCityNum )
	{
		if( j == _City ) { ++j; continue;}		
	
		_CitySerial[i] = j;
		INT tmpNum = j;		

		for( k = i; k > 0; --k)
		{			
			if( l_City_Dists[tmpNum] < l_City_Dists[ _CitySerial[k-1] ] )
			{
				_CitySerial[k] = _CitySerial[k-1];
				//printf("%d--->%d\n", _CitySerial[k-1], _CitySerial[k]);
			}
			else
			{
				//printf("current--->%d\n", tmpNum);
				break;				
			}
		}
		_CitySerial[k] =tmpNum;
		
		++i;
		++j;
	}//已经初始化了_CitySerial；

	/*for(k = 0; k < _ShortestCityNum; ++k)
	{
		printf("InitialValue--->%d\n", _CitySerial[k]);
	}*/
	//printf("**************************************************************************\n");

	while( j < _CityInfo.m_CityNum )
	{
		//for(k = 0; k < _ShortestCityNum; ++k)printf("CurrentValue--->%d\n", _CitySerial[k]);
		if( j == _City ) { ++j; continue; }
		//printf("Dist%d--->%f\n",j, l_City_Dists[j]);
		if( l_City_Dists[j] > l_City_Dists[ _CitySerial[_ShortestCityNum - 1] ] ) { ++j; continue; }

		INT tmpNum = j;
		for( k = _ShortestCityNum - 1; k > 0; --k)
		{
			if( l_City_Dists[tmpNum] < l_City_Dists[ _CitySerial[k-1] ] )
			{
				_CitySerial[k] = _CitySerial[k-1];
				//printf("%d--->%d\n", _CitySerial[k-1], _CitySerial[k]);
			}
			else
			{				
				break;
			}
		}
		_CitySerial[k] =tmpNum;
		//printf("current%d--->%d\n",k, tmpNum);
		++j;
	}

	//for(k = 0; k < _ShortestCityNum; ++k)
	//{
	//	printf("%d--->%d \t", _City, _CitySerial[k]);
	//}
	//printf("\n*************************************************\n");

	return TRUE;
}

/*
功能：获取与各城市最近的城市序号
输入：城市信息--->_CityInfo 城市-->_City 最近序列数--->_ShortestCityNum
输出：最近城市序列-->_CitySerial[][] 
错误（输出TRUE or FALSE）：处理的结果正确与否 
Time：2007-06-21
*/
BOOL WSTSP::MakeCityDistStyle(CityInfo &_CityInfo, INT **_CitySerial, INT _ShortestCityNum)
{
	INT i;
	for(i = 0; i < _CityInfo.m_CityNum; ++i)
	{
		GetShortestCities(_CityInfo, i, _CitySerial[i], _ShortestCityNum);
	}

	//for(i = 0; i < _CityInfo.m_CityNum; ++i)
	//{
	//	for(int k = 0; k < _ShortestCityNum; ++k)
	//	{
	//		printf("%d--->%d \t", i, _CitySerial[i][k]);
	//	}
	//	printf("\n*************************************************\n");
	//}

	return TRUE;
}

/*
功能：调整城市的序号
输入：城市信息--->_CityInfo
输出：排好序的城市序列（以0为开始）-->_CitySerial[][] 
错误（输出TRUE or FALSE）：处理的结果正确与否 
Time：2007-06-21
*/
BOOL WSTSP::AdjustCityOrder(CityInfo &_CityInfo)
{
	CityOrderDef newOrder;
	INT i = 0;

	//先为newOrder分配存储空间
	for(i = 0; i < _CityInfo.m_CityNum; ++i) newOrder.push_back(0);

	for(i = 0; i < _CityInfo.m_CityNum; ++i)
	{
		if(_CityInfo.m_pCityOrder[i] == 0) break;
	}

	INT j = 0;
	for(j = i; j < _CityInfo.m_CityNum; ++j)
	{
		newOrder[j - i] = _CityInfo.m_pCityOrder[j];
	}
	for(j = 0; j < i; ++j)
	{
		newOrder[j + _CityInfo.m_CityNum - i] = _CityInfo.m_pCityOrder[j];
	}

	_CityInfo.m_pCityOrder.clear();
	_CityInfo.m_pCityOrder = newOrder;
	newOrder.clear();

	return TRUE;
}
/*
功能：生成一组城市序列
输入：城市信息--->_CityInfo，单个城市模式数--->_ShortestCityNum
输出：排好序的城市序列（以0为开始）-->_CitySerial[][] 
错误（输出TRUE or FALSE）：处理的结果正确与否 
Time：2007-06-21
*/
BOOL WSTSP::MakeStyleCityOrder(CityInfo &_CityInfo, INT **_CitySerial, INT _ShortestCityNum)
{
	CityOrderDef l_CityOrder;
	INT i;
	//初始化l_CityOrder;
	for(i = 0; i < _CityInfo.m_CityNum; ++i)
	{
		l_CityOrder.push_back(i);
	}

	_CityInfo.m_pCityOrder.clear();
	INT startCity = WSRandom::GenRand(0, _CityInfo.m_CityNum - 1);
	
	_CityInfo.m_pCityOrder.push_back(startCity);
	l_CityOrder.erase(l_CityOrder.begin() + startCity);

	INT nextCity;
	INT j;
	BOOL bFind = FALSE;
	while(TRUE)
	{
		//for(j = 0; j < l_CityOrder.size(); ++j)
		//{
		//	printf("%d \t", l_CityOrder[j]);
		//}
		//printf("\nCurrentCity-->%d\n", startCity);
		//printf("\n************************************************\n");

		bFind = FALSE;
		for(j = 0; j < _ShortestCityNum; ++j)
		{			
			nextCity = _CitySerial[startCity][j];
			for(i = 0; i < l_CityOrder.size(); ++i)
			{
				if(nextCity == l_CityOrder[i])
				{
					_CityInfo.m_pCityOrder.push_back(nextCity);
					l_CityOrder.erase(l_CityOrder.begin() + i);
					startCity = nextCity;
					bFind = TRUE;
					break;
				}
			}
			if(bFind) break;
		}

		if(bFind) continue;
		if(l_CityOrder.size() == 0) break;

		i = WSRandom::GenRand(0, l_CityOrder.size()-1);
		startCity = l_CityOrder[ i ];
		_CityInfo.m_pCityOrder.push_back( startCity );
		l_CityOrder.erase( l_CityOrder.begin() + i );

		if(l_CityOrder.size() == 0) break;
	}
	l_CityOrder.clear();

	AdjustCityOrder(_CityInfo);
	
	//for(j = 0; j < _CityInfo.m_CityNum; ++j)
	//{
	//	printf("%d \t",_CityInfo.m_pCityOrder[j]); 
	//}
	//printf("\n");

	return TRUE;
}

VOID WSTSP::SwapTwoCity(CityOrderDef &_CityOrder)
{
	INT l_Len = _CityOrder.size();
	if(l_Len == 1) return ;
	INT n1, n2;
	do{
		n1 = WSRandom::GenRand(0, l_Len - 1);
		n2 = WSRandom::GenRand(0, l_Len - 1);
	}while(n1 == n2);

	SwapTwoCity(_CityOrder, n1, n2);
	
}

VOID WSTSP::SwapTwoCity(CityOrderDef &_CityOrder, INT i, INT j)
{
	SwapValues(_CityOrder[i], _CityOrder[j]);
}

INT WSTSP::GetBestRoute(TaboTable p_TaboTable)
{
	INT l_Len = p_TaboTable.size();
	INT i = 0, bestRouteNo = 0;
	float bestdist = p_TaboTable[0].m_distance;

	for(i = 1; i < l_Len; ++i)
	{
		if(bestdist > p_TaboTable[i].m_distance)
		{
			bestdist = p_TaboTable[i].m_distance;
			bestRouteNo = i;
		}
	}

	return bestRouteNo;
}

INT WSTSP::GetBestRoute(CityPeerInfoVector p_CityPeerInfoVector)
{
	INT l_Len = p_CityPeerInfoVector.size();
	INT i = 0, bestRouteNo = 0;
	float bestdist = p_CityPeerInfoVector[0].m_Distance;

	for(i = 1; i < l_Len; ++i)
	{
		if(bestdist > p_CityPeerInfoVector[i].m_Distance)
		{
			bestdist = p_CityPeerInfoVector[i].m_Distance;
			bestRouteNo = i;
		}
	}

	return bestRouteNo;
}