?? sacode.cpp
字號:
#include <StdAfx.h>
#include <math.h>
#include <algorithm>
using std::random_shuffle;
using std::swap;
/*********************************************************
InitialSA()——模擬退火算法的初始化
1. 根據直角坐標生成城市距離矩陣
2. 計算初始溫度
*********************************************************/
void InitialSA()
{
if( FileType == 1 )
{
CityNumber = vecCitys.size();
vecCityDistances.clear();
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;
CountCityDistance( *iter_from, *iter_to, tmp_citydistance );
vecCityDistances.push_back( tmp_citydistance );
}
}
}
else if( FileType == 2 )
{
vecCitys.clear();
int nRow = -1;
int ncityindex;
CString strcityname;
std::vector<SYCityDistance>::iterator iter_dis;
for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
{
if( nRow < 0 )
nRow = iter_dis->m_nFromCity;
if( iter_dis->m_nFromCity == nRow )
{
ncityindex = iter_dis->m_nToCity;
strcityname.Format("城市 %d",ncityindex);
SYCity tmpCity;
tmpCity.m_strName = strcityname;
tmpCity.m_nIndex = ncityindex;
tmpCity.m_Coordinate.m_fcodx = 0.0;
tmpCity.m_Coordinate.m_fcody = 0.0;
vecCitys.push_back( tmpCity );
}
else
break;
}
CityNumber = vecCitys.size();
}
double fMaxCityDistance = 0.0;
double fMinCityDistance = 100000.0;
double fCityDistance = 0.0;
std::vector<SYCityDistance>::iterator iter_dis;
for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
{
fCityDistance = iter_dis->m_fDistance;
if( fCityDistance > fMaxCityDistance )
fMaxCityDistance = fCityDistance;
if( fCityDistance < fMinCityDistance )
fMinCityDistance = fCityDistance;
}
int rate = 20;
InitialTemperature = CountInitialTemperatureMaxMin( fMaxCityDistance, fMinCityDistance, rate );
NowTemperature = InitialTemperature;
NowExternalIterNumber = 0;
NowInnerIterNumber = 0;
}
/*********************************************************
ClearSA()——清空殘留數據
*********************************************************/
void ClearSA()
{
vecCitys.clear();
vecCityDistances.clear();
CityNumber = 0;
InitialTemperature = 0.0;
NowTemperature = 0.0;
NowExternalIterNumber = 0;
NowInnerIterNumber = 0;
}
/*********************************************************
CountCityDistance()——計算城市之間的距離
輸入參數： 1、FromCity 源城市引用
2、ToCity 目標城市引用
3、CityDistance 城市距離利用，返回值
返回值： 源城市與目標城市之間的距離，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()——計算起始溫度
輸入參數： 1、maxdis 城市之間的最大距離
2、mindis 城市之間的最小距離
3、rate 比例系數
返回值： 起始溫度，double型
計算方法參見《現代優化計算方法》（邢文訓等編著） p117
*********************************************************/
double CountInitialTemperatureMaxMin( double maxdis, double mindis, int rate )
{
return( rate*( CityNumber*maxdis - CityNumber*mindis ) );
}
/*********************************************************
CreateCityRouter()——生成城市行走路徑
輸入參數： 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()——從某行走路徑的鄰域中隨機選擇一個新的行走路徑，鄰域映射為2-opt
輸入參數： 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()——根據給定路徑計算該路徑對應的總路程
輸入參數： 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()——根據兩城市的索引獲得兩城市之間的路程
輸入參數： 1、FromCityIndex 源城市的索引
2、ToCityIndex 目標城市的索引
返回值： 兩城市之間的路程，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()——計算外層循環的下降后的溫度
輸入參數： 1、nowtemp 當前溫度
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()——判斷是否結束某一溫度下的內層循環
輸入參數： 1、JudgeMode 判斷方式，保留
返回值： 是否結束標志位，BOOL型
注： 某一溫度下的循環次數是固定的，即城市個數的三次方
*********************************************************/
BOOL JudgeOverInnerLoop( int JudgeMode )
{
if( NowInnerIterNumber >= CityNumber*CityNumber*CityNumber ) //*CityNumber)
return TRUE;
else
return FALSE;
}
/*********************************************************
JudgeOverExternalLoop()——判斷是否結束模擬退火算法
輸入參數： 1、JudgeMode 判斷方式，保留
返回值： 是否結束標志位，BOOL型
注： 使用“零度法”的判斷方式，T（k）<= 0.01，結束計算
*********************************************************/
BOOL JudgeOverExternalLoop( int JudgeMode )
{
if( NowTemperature <= 0.01 ) //InitialTemperature*0.001 )
return TRUE;
else
return FALSE;
}
/*********************************************************
FormRouterString()——根據行走路徑生成路徑字符串，供顯示使用
輸入參數： 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()——根據城市索引獲取城市坐標
輸入參數： 1、cityindex 城市索引
2、coordx 城市X坐標
3、coordy 城市Y坐標
返回值： 空
*********************************************************/
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()——獲得指定路徑的城市坐標字符串
輸入參數： 1、CityRouter 城市路徑索引
2、strTemp 城市坐標字符串
返回值： 空
*********************************************************/
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;
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -