?? sacode.cpp
字號(hào):
#include <StdAfx.h>
#include <math.h>
#include <algorithm>
using std::random_shuffle;
using std::swap;
/*********************************************************
InitialSA()——模擬退火算法的初始化
1. 根據(jù)直角坐標(biāo)生成城市距離矩陣
2. 計(jì)算初始溫度
*********************************************************/
void InitialSA()
{
CityNumber = vecCitys.size();
vecCityDistances.clear();
double fMaxCityDistance = 0.0;
double fMinCityDistance = 100000.0;
double fCityDistance = 0.0;
std::vector<SYCity>::iterator iter_from, iter_to;
for( iter_from=vecCitys.begin();iter_from!=vecCitys.end();iter_from++ )
{
for( iter_to=vecCitys.begin();iter_to!=vecCitys.end();iter_to++ )
{
SYCityDistance tmp_citydistance;
fCityDistance = CountCityDistance( *iter_from, *iter_to, tmp_citydistance );
if( fCityDistance > fMaxCityDistance )
fMaxCityDistance = fCityDistance;
if( fCityDistance < fMinCityDistance )
fMinCityDistance = fCityDistance;
vecCityDistances.push_back( tmp_citydistance );
}
}
int rate = 20;
InitialTemperature = CountInitialTemperatureMaxMin( fMaxCityDistance, fMinCityDistance, rate );
NowTemperature = InitialTemperature;
NowExternalIterNumber = 0;
NowInnerIterNumber = 0;
}
/*********************************************************
ClearSA()——清空殘留數(shù)據(jù)
*********************************************************/
void ClearSA()
{
vecCitys.clear();
vecCityDistances.clear();
CityNumber = 0;
InitialTemperature = 0.0;
NowTemperature = 0.0;
NowExternalIterNumber = 0;
NowInnerIterNumber = 0;
}
/*********************************************************
CountCityDistance()——計(jì)算城市之間的距離
輸入?yún)?shù)： 1、FromCity 源城市引用
2、ToCity 目標(biāo)城市引用
3、CityDistance 城市距離利用，返回值
返回值： 源城市與目標(biāo)城市之間的距離，double型
*********************************************************/
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
CityDistance.m_nFromCity = FromCity.m_nIndex;
CityDistance.m_nToCity = ToCity.m_nIndex;
CityDistance.m_fDistance = sqrt( (FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx)*(FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx) +
(FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody)*(FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody) );
return CityDistance.m_fDistance;
}
/*********************************************************
CountInitialTemperatureMaxMin()——計(jì)算起始溫度
輸入?yún)?shù)： 1、maxdis 城市之間的最大距離
2、mindis 城市之間的最小距離
3、rate 比例系數(shù)
返回值： 起始溫度，double型
計(jì)算方法參見(jiàn)《現(xiàn)代優(yōu)化計(jì)算方法》（邢文訓(xùn)等編著） p117
*********************************************************/
double CountInitialTemperatureMaxMin( double maxdis, double mindis, int rate )
{
return( rate*( CityNumber*maxdis - CityNumber*mindis ) );
}
/*********************************************************
CreateCityRouter()——生成城市行走路徑
輸入?yún)?shù)： 1、CityRouter 城市行走路徑的vector引用，返回值
返回值： 空
注：生成1->2->3->......->n的城市行走順序，作為算法初值
*********************************************************/
void CreateCityRouter( CityRouterDef &CityRouter )
{
for( int i=1;i<=CityNumber;i++ )
CityRouter.push_back( i );
// random_shuffle(CityRouter.begin(), CityRouter.end());
}
/*********************************************************
CreateCityRouter2opt()——從某行走路徑的鄰域中隨機(jī)選擇一個(gè)新的行走路徑，鄰域映射為2-opt
輸入?yún)?shù)： 1、preCityRouter 原先行走路徑的vector引用
2、CityRouter 新的行走路徑的vector引用，返回值
返回值： 空
*********************************************************/
void CreateCityRouter2opt( CityRouterDef &preCityRouter, CityRouterDef &CityRouter )
{
int swapA, swapB;
CityRouter = preCityRouter;
while(1)
{
swapA = (rand()%CityNumber)-1;
if( swapA >= 0 )
break;
}
while(1)
{
swapB = (rand()%CityNumber)-1;
if( swapA != swapB && swapB >= 0 )
{
int tmp = CityRouter[swapA];
CityRouter[swapA] = CityRouter[swapB];
CityRouter[swapB] = tmp;
break;
}
}
}
/*********************************************************
CountTotalDistance()——根據(jù)給定路徑計(jì)算該路徑對(duì)應(yīng)的總路程
輸入?yún)?shù)： 1、CityRouter 給定行走路徑的vector引用
返回值： 總路程，double型
*********************************************************/
double CountTotalDistance( CityRouterDef &CityRouter )
{
if( CityRouter.size() != CityNumber )
return 0.0;
double totaldis = 0.0;
for( int i=1;i<CityNumber;i++ )
{
totaldis += FindCityDistance( CityRouter[i-1], CityRouter[i] );
}
totaldis += FindCityDistance( CityRouter[CityNumber-1], CityRouter[0] );
return totaldis;
}
/*********************************************************
FindCityDistance()——根據(jù)兩城市的索引獲得兩城市之間的路程
輸入?yún)?shù)： 1、FromCityIndex 源城市的索引
2、ToCityIndex 目標(biāo)城市的索引
返回值： 兩城市之間的路程，double型
*********************************************************/
double FindCityDistance( int FromCityIndex, int ToCityIndex )
{
int nIndex = (FromCityIndex-1)*CityNumber+(ToCityIndex-1);
std::vector<SYCityDistance>::iterator iter_citydis;
iter_citydis = vecCityDistances.begin()+nIndex;
if( iter_citydis->m_nFromCity == FromCityIndex &&
iter_citydis->m_nToCity == ToCityIndex )
return( iter_citydis->m_fDistance );
else
return( 0.0 );
}
/*********************************************************
CountDownTemperature()——計(jì)算外層循環(huán)的下降后的溫度
輸入?yún)?shù)： 1、nowtemp 當(dāng)前溫度
2、DownMode 下降方式，保留
返回值： 下降后的溫度，double型
注： 溫度下降方式 T（k+1） = K*T（k），K=0.95溫度下降方式 T（k+1） = K*T（k），K=0.95
*********************************************************/
double CountDownTemperature( double nowtemp, int DownMode )
{
return( 0.95*nowtemp );
}
/*********************************************************
JudgeOverInnerLoop()——判斷是否結(jié)束某一溫度下的內(nèi)層循環(huán)
輸入?yún)?shù)： 1、JudgeMode 判斷方式，保留
返回值： 是否結(jié)束標(biāo)志位，BOOL型
注： 某一溫度下的循環(huán)次數(shù)是固定的，即城市個(gè)數(shù)的三次方
*********************************************************/
BOOL JudgeOverInnerLoop( int JudgeMode )
{
if( NowInnerIterNumber >= CityNumber*CityNumber*CityNumber ) //*CityNumber)
return TRUE;
else
return FALSE;
}
/*********************************************************
JudgeOverExternalLoop()——判斷是否結(jié)束模擬退火算法
輸入?yún)?shù)： 1、JudgeMode 判斷方式，保留
返回值： 是否結(jié)束標(biāo)志位，BOOL型
注： 使用“零度法”的判斷方式，T（k）<= 0.01，結(jié)束計(jì)算
*********************************************************/
BOOL JudgeOverExternalLoop( int JudgeMode )
{
if( NowTemperature <= 0.01 ) //InitialTemperature*0.001 )
return TRUE;
else
return FALSE;
}
/*********************************************************
FormRouterString()——根據(jù)行走路徑生成路徑字符串，供顯示使用
輸入?yún)?shù)： 1、CityRouter 給定行走路徑的引用
返回值： 行走路徑的顯示字符串
*********************************************************/
CString FormRouterString( SYRouter &CityRouter )
{
CString strTemp, strValue;
strTemp = "路徑 ";
std::vector<int>::iterator iter_cityindex;
for( iter_cityindex=CityRouter.m_CityRouter.begin();
iter_cityindex!=CityRouter.m_CityRouter.end();
iter_cityindex++ )
{
strValue.Format("%d",*iter_cityindex);
strTemp += strValue;
if( iter_cityindex+1 == CityRouter.m_CityRouter.end() )
strTemp += " ";
else
strTemp +=" ";
}
strTemp += " ";
strTemp += "總路程 ";
strValue.Format("%10.4f",CityRouter.m_fTotalDistance);
strTemp += strValue;
return strTemp;
}
/*********************************************************
GetCoordinatebyCityIndex()——根據(jù)城市索引獲取城市坐標(biāo)
輸入?yún)?shù)： 1、cityindex 城市索引
2、coordx 城市X坐標(biāo)
3、coordy 城市Y坐標(biāo)
返回值： 空
*********************************************************/
void GetCoordinatebyCityIndex( int cityindex, double &coordx, double &coordy )
{
coordx = 0.0;
coordy = 0.0;
if( cityindex > 0 && cityindex <= CityNumber )
{
std::vector<SYCity>::iterator iter_city;
iter_city = vecCitys.begin()+cityindex-1;
if( iter_city->m_nIndex == cityindex )
{
coordx = iter_city->m_Coordinate.m_fcodx;
coordy = iter_city->m_Coordinate.m_fcody;
}
}
}
/*********************************************************
GetRouterFileString()——獲得指定路徑的城市坐標(biāo)字符串
輸入?yún)?shù)： 1、CityRouter 城市路徑索引
2、strTemp 城市坐標(biāo)字符串
返回值： 空
*********************************************************/
void GetRouterFileString( SYRouter &CityRouter, CString &strTemp )
{
strTemp.Empty();
CString strValue;
std::vector<int>::iterator iter_city;
double coordx, coordy;
for( iter_city=CityRouter.m_CityRouter.begin();
iter_city!=CityRouter.m_CityRouter.end();
iter_city++ )
{
GetCoordinatebyCityIndex( *iter_city, coordx, coordy );
strValue.Format("%.4f %.4f\n",coordx, coordy );
strTemp += strValue;
}
}?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -