mainfrm.cpp

模拟退火优化旅行商问题,付城市坐标!vC++代码!

// MainFrm.cpp : implementation of the CMainFrame class
//

#include "stdafx.h"
#include "TspSA.h"
#include "TspSADoc.h"
#include "TspSAView.h"
#include "math.h"
#include "MainFrm.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//似乎必须放在下面，如果把这些全局变量定义放在最顶处则报错 why？
std::vector<SYCity> vecCitys;						//城市列表
std::vector<SYCityDistance> vecCityDistances;		//城市距离列表
int CityNumber = 0;									//城市个数
double InitialTemperature = 0.0;					//初始温度
int NowInnerIterNumber = 0;							//当前内循环迭代次数
BOOL IsComputing = FALSE;

/////////////////////////////////////////////////////////////////////////////
// CMainFrame

IMPLEMENT_DYNCREATE(CMainFrame, CFrameWnd)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
	//{{AFX_MSG_MAP(CMainFrame)
	ON_WM_CREATE()
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	ON_COMMAND(ID_FILE_START, OnFileStart)
	ON_UPDATE_COMMAND_UI(ID_FILE_START, OnUpdateFileStart)
	ON_UPDATE_COMMAND_UI(ID_FILE_OPEN, OnUpdateFileOpen)
	ON_COMMAND(ID_APP_GETCODE, OnAppGetcode)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

static UINT indicators[] =
{
	ID_SEPARATOR,           // status line indicator
};

/////////////////////////////////////////////////////////////////////////////
// CMainFrame construction/destruction

CMainFrame::CMainFrame()
{
}

CMainFrame::~CMainFrame()
{
}

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
	if (CFrameWnd::OnCreate(lpCreateStruct) == -1)
		return -1;
	
	if (!m_wndStatusBar.Create(this) ||
		!m_wndStatusBar.SetIndicators(indicators,
		  sizeof(indicators)/sizeof(UINT)))
	{
		TRACE0("Failed to create status bar\n");
		return -1;      // fail to create
	}
	
	if (!m_wndToolBar.CreateEx(this, TBSTYLE_FLAT, WS_CHILD | WS_VISIBLE | CBRS_TOP
		| CBRS_GRIPPER | CBRS_TOOLTIPS | CBRS_FLYBY | CBRS_SIZE_DYNAMIC) ||
		!m_wndToolBar.LoadToolBar(IDR_MAINFRAME))
	{
		TRACE0("Failed to create toolbar\n");
		return -1;      // fail to create
	}

	m_wndToolBar.EnableDocking(CBRS_ALIGN_ANY);
	EnableDocking(CBRS_ALIGN_ANY);
	DockControlBar(&m_wndToolBar);

	return 0;
}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
	cs.style &= ~FWS_ADDTOTITLE;
	if( !CFrameWnd::PreCreateWindow(cs) )
		return FALSE;
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	m_strTitle = "www.huisoft.com.cn  模拟退火算法求解TSP问题";
	return TRUE;
}

/////////////////////////////////////////////////////////////////////////////
// CMainFrame diagnostics

#ifdef _DEBUG
void CMainFrame::AssertValid() const
{
	CFrameWnd::AssertValid();
}

void CMainFrame::Dump(CDumpContext& dc) const
{
	CFrameWnd::Dump(dc);
}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMainFrame message handlers

void CMainFrame::OnFileStart() 
{
	CTspSAView *pView = (CTspSAView*)GetActiveView();
	AfxBeginThread( SACompution, (LPVOID)pView );
}

void CMainFrame::OnUpdateFileStart(CCmdUI* pCmdUI) 
{
	if( vecCityDistances.empty() || IsComputing )
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);
}

void CMainFrame::OnUpdateFileOpen(CCmdUI* pCmdUI) 
{
	if( IsComputing )
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);
}

void CMainFrame::OnAppGetcode() 
{
	CString strTemp;
	strTemp.LoadString(IDS_HELP_HOMEPAGE);
	::ShellExecute(NULL, "open", strTemp, NULL, NULL, SW_SHOWNORMAL);	
}

void CMainFrame::OnFileOpen() 
{
	CString strFileName;
	char szFilter[200];
	strcpy( szFilter, "TXT Files (*.txt)|*.txt||" );
	CFileDialog *pFileDialog;
	pFileDialog = new CFileDialog( TRUE, 
								NULL, 
								NULL, 
								OFN_HIDEREADONLY,
								szFilter,
								this );
	if( IDOK == pFileDialog->DoModal() )
	{
		CTspSAView *pView = (CTspSAView*)GetActiveView();
		ClearSA();
		pView->ClearInfos();
		
		CString strValue, strTemp;
		strFileName = pFileDialog->GetPathName();
		CStdioFile DataFile( strFileName, CFile::modeRead );
		CString strReadString;
		int ncityindex = 1;
		while( DataFile.ReadString(strReadString) ) 
		{
			strReadString.TrimLeft();
			strReadString.TrimRight();

			CString cityName, citycodx, citycody;
			int nspace = 0;
			nspace = strReadString.Find(" ");
			if( nspace > 0 )
				cityName = strReadString.Left( nspace );

			strReadString = strReadString.Mid( nspace+1 );
			nspace = strReadString.Find(" ");
			if( nspace > 0 )
				citycodx = strReadString.Left( nspace );

			strReadString = strReadString.Mid( nspace+1 );
			citycody = strReadString;

			SYCity tmpCity;
			tmpCity.m_strName = "城市 "+cityName;
			tmpCity.m_nIndex = ncityindex;
			tmpCity.m_Coordinate.m_fcodx = atof( citycodx );
			tmpCity.m_Coordinate.m_fcody = atof( citycody );

			vecCitys.push_back( tmpCity );

			ncityindex++;
		}
		DataFile.Close();

		InitialSA();
		strTemp = "共读入城市信息";
		strValue.Format("%d",CityNumber);
		strTemp += strValue;
		strTemp += "个";
		pView->AddString( strTemp );

		strTemp = "计算城市距离完成";
		pView->AddString( strTemp );
	}	

	delete pFileDialog;
}


double GetProbability(double dDelta,double dTemp)
{//一切玄机在此！！！
	return exp( - dDelta / dTemp );
}


UINT SACompution(LPVOID pParam)
{
	IsComputing = TRUE;
	double NowTemperature = InitialTemperature;//当前迭代温度
	int nIndex(0),NowExternalIterNumber(0),NowInnerIterNumber(0);
	CString format,strTemp("开始计算.........");
	CTspSAView *pView = (CTspSAView*)pParam;
	HWND ViewHWND = pView->GetSafeHwnd();


	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	SYRouter ResultRouter;
	double memLens = ResultRouter.m_fTotalDistance;//记忆优化路程

	srand( (unsigned)time( NULL ) );
	while(1)
	{
		strTemp = FormRouterString( ResultRouter );
		format.Format("温度:%4.2f  次数: %2d,%2d;",NowTemperature,NowExternalIterNumber,nIndex);
		strTemp += format;
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
		double dDelta = 0.0;
		
		if( NowTemperature <= 0.001 ) {break;}//判断是否结束模拟退火
		while(1)
		{
			nIndex++;
			SYRouter SelRouter(ResultRouter.m_CityRouter);//求目标函数
			dDelta = (SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance);
			if( dDelta < 0.0 ){
				ResultRouter = SelRouter;
				memLens = (memLens < SelRouter.m_fTotalDistance)?memLens:SelRouter.m_fTotalDistance;
			}
			else if(GetProbability(dDelta,NowTemperature) > (double)(rand() % 10000) / 10000.0){//随机接受新解
				ResultRouter = SelRouter;	memLens = (memLens < SelRouter.m_fTotalDistance)?memLens:SelRouter.m_fTotalDistance;
			}
			if( NowInnerIterNumber <= CityNumber*CityNumber*CityNumber){NowInnerIterNumber++;}//判断是否结束某一温度下的内层循环
			else{break;}
		}		
		NowExternalIterNumber++;
		NowInnerIterNumber = 0;
		NowTemperature     *= 0.96;//计算外层循环的下降后的温度
	}

	strTemp = "最终优化结果:";
	strTemp += FormRouterString( ResultRouter );
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	format.Format("记忆优化结果: 路程%.2f;",memLens);
	strTemp = format;
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	IsComputing = FALSE;
	return 0;
}