mainfrm.cpp

模拟退火算法、遗传算法求解TSP修改版2 下载

// 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;					//初始温度
double NowTemperature = 0.0;						//当前迭代温度
int	NowExternalIterNumber = 0;						//当前外循环迭代次数
int NowInnerIterNumber = 0;							//当前内循环迭代次数
int FileType;										//文件格式 0 无效格式 1 坐标格式 2 对称距离矩阵格式
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
	}

	// TODO: Delete these three lines if you don't want the toolbar to
	//  be dockable

	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问题";
	m_strTitle = "模拟退火算法求解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::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;
		BOOL readfilesucflg = TRUE;
		strFileName = pFileDialog->GetPathName();
		CStdioFile DataFile( strFileName, CFile::modeRead );
		CString strReadString;

		DataFile.ReadString(strReadString);
		if( strReadString == "coordinate" )
			FileType = 1;
		else if( strReadString == "distancematrix" )
			FileType = 2;
		else
			FileType = 0;

		if( FileType == 0 )
		{
			readfilesucflg = FALSE;
		}
		else
		{
			if( FileType == 1 )
			{
				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++;
				}
			}
			else if( FileType == 2 )
			{
				int nMatrixRow = 1;			//代表第几个城市所对应的行
				int nMatrixCol = 1;
				int nMaxMatrixCol = -1;		//记录第一行的列数,后续行的列数如果不等于第一行,则数据文件错误
				CString strDistance;
				while( DataFile.ReadString(strReadString) )
				{
					strReadString.TrimLeft();
					strReadString.TrimRight();
	
					if( strReadString.IsEmpty() )
						continue;

					int nspace = 0;
					nMatrixCol = 1;
					while(1)
					{
						nspace = strReadString.Find(" ");
						SYCityDistance tmp_citydistance;
						if( nspace > 0 )
						{
							strDistance = strReadString.Left( nspace );
							tmp_citydistance.m_fDistance = atof( strDistance );
							tmp_citydistance.m_nFromCity = nMatrixRow;
							tmp_citydistance.m_nToCity = nMatrixCol;
							vecCityDistances.push_back( tmp_citydistance );

							strReadString = strReadString.Mid( nspace+1 );
							strReadString.TrimLeft();
						}
						else 
						{
							if( !strReadString.IsEmpty() )
							{
								strDistance = strReadString;
								tmp_citydistance.m_fDistance = atof( strDistance );
								tmp_citydistance.m_nFromCity = nMatrixRow;
								tmp_citydistance.m_nToCity = nMatrixCol;
								vecCityDistances.push_back( tmp_citydistance );

								strReadString.Empty();
								break;
							}
							else
								break;
						}
						nMatrixCol++;
					}

					if( nMaxMatrixCol < 0 )
						nMaxMatrixCol = nMatrixCol;
					else
					{
						if( nMaxMatrixCol != nMatrixCol )
						{
							readfilesucflg = FALSE;
							break;
						}
					}
	
					nMatrixRow++;
				}
			}
		}

		DataFile.Close();

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

			strTemp = "计算城市距离完成";
			pView->AddString( strTemp );
		}
		else
		{
			strTemp = "读入数据文件错误";
			pView->AddString( strTemp );
		}
	}
	delete pFileDialog;
}

UINT SACompution(LPVOID pParam)
{
	IsComputing = TRUE;

	srand( (unsigned)time( NULL ) );

	CFile cityfile("C:\\sacitysfile.txt", CFile::modeCreate|CFile::modeWrite);
	CFile iterfile("C:\\saitersfile.txt", CFile::modeCreate|CFile::modeWrite);

	CString strTemp, strValue;
	CTspSAView *pView = (CTspSAView*)pParam;
	HWND ViewHWND = pView->GetSafeHwnd();

	strTemp = "开始计算";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	SYRouter ResultRouter( NowTemperature, NowExternalIterNumber, NowInnerIterNumber );

	strTemp = "生成初始路径:";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	strTemp = FormRouterString( ResultRouter );
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	while(1)
	{
		strTemp = "新的内循环开始，当前温度为";
		strValue.Format("%10.4f",NowTemperature);
		strTemp += strValue;
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
		strTemp = "当前路径为:";
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
		strTemp = FormRouterString( ResultRouter );
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

		double deltatotaldis = 0.0;
		while(1)
		{
			SYRouter SelRouter( ResultRouter.m_CityRouter, NowTemperature, NowExternalIterNumber, NowInnerIterNumber );

			deltatotaldis = SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;
			if( deltatotaldis <= 0.0 )
			{
				ResultRouter = SelRouter;
			}
			else
			{
				double chgprobability = exp( -(deltatotaldis/NowTemperature) );
				int randomnum = rand();
				double random = ((double)(randomnum%10000))/10000.0;
				if(chgprobability > random )
				{
					ResultRouter = SelRouter;
				}
			}

			if( JudgeOverInnerLoop(0) )
			{
				break;
			}
			else
				NowInnerIterNumber++;
		}

		if( JudgeOverExternalLoop(0) )
			break;
		else
		{
			NowTemperature = CountDownTemperature( NowTemperature, 0 );
			NowExternalIterNumber++;
			NowInnerIterNumber = 0;

			strValue.Format("%d %.4f\n",NowExternalIterNumber, ResultRouter.m_fTotalDistance );
			iterfile.Write( strValue, strValue.GetLength() );

		}
	}

	strTemp = "计算得最佳路径为:";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	strTemp = FormRouterString( ResultRouter );
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	
	GetRouterFileString( ResultRouter, strTemp );
	cityfile.Write( strTemp, strTemp.GetLength() );

	cityfile.Close();
	iterfile.Close();

	IsComputing = FALSE;
	return 0;
}

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);	
}