mysaaview.cpp

平台vs2005 模拟固体退火算法实现144个城市的旅行商问题

// MySAAView.cpp : CMySAAView 类的实现


//问题描述：利用固体模拟退火算法计算出文件给出的144个城市的旅行商问题，计算出较优解

//主要实现的功能：通过在对话框内输入参数，在视图中描绘出路径，并给出路径长度

//主要参数定义：
//T:设置初始温度
//L:链表长，即循环次数
//TGene：温度衰减因子，即T = T * TGene

//主函数为OnErZhi()

//算法思想：在参数都传入之后，先计算出初始路径长度，然后通过在Generate()中对路径中的一段进
//行倒序，计算路径差值进行判定接受，并相应计算出路径长度，当路径长度连续50次不变，输出结果


#include "iostream.h"
#include <stdlib.h> 
#include <time.h>

#include "stdafx.h"
#include "MySAA.h"


#include "MySAADoc.h"
#include "MySAAView.h"
#include "MyDialog.h"

#include "math.h"
#include <fstream>
using namespace std;

#define N 144


#ifdef _DEBUG
#define new DEBUG_NEW
#endif


CMySAAView* pView;
// CMySAAView

IMPLEMENT_DYNCREATE(CMySAAView, CView)

BEGIN_MESSAGE_MAP(CMySAAView, CView)
	// 标准打印命令
	ON_COMMAND(ID_FILE_PRINT, &CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, &CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, &CView::OnFilePrintPreview)
	ON_COMMAND( ID_BUTTON_ERBIANHUAN,OnErZhi)
END_MESSAGE_MAP()

// CMySAAView 构造/析构

CMySAAView::CMySAAView()
{
	// TODO: 在此处添加构造代码
	pView = this;

}

CMySAAView::~CMySAAView()
{
}

BOOL CMySAAView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: 在此处通过修改
	//  CREATESTRUCT cs 来修改窗口类或样式

	return CView::PreCreateWindow(cs);
}

// CMySAAView 绘制

void CMySAAView::OnDraw(CDC* /*pDC*/)
{
	CMySAADoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if (!pDoc)
		return;

	// TODO: 在此处为本机数据添加绘制代码
}

//计算路径长度
double CMySAAView :: ComputeResult()
{
	double result = 0,disx, disy;
	for(int i = 0; i < N - 1; i++)
	{
		disx = City[i][0] - City[i+1][0];
		disy = City[i][1] - City[i+1][1];
		result = result+ sqrt( disx * disx + disy * disy );
	}
	disx = City[N-1][0] - City[0][0];
	disy = City[N-1][1] - City[0][1];
	result = result + sqrt( disx * disx + disy * disy );

	return result;
}

//计算city中两城市的路程
double CMySAAView::CityComputeSqrt( int n )
{
	double disx, disy, SqrtResult;
	if( n == 143 || n == -1 )
	{
		disx = City[143][0] - City[0][0];
		disy = City[143][1] - City[0][1];
	}
	else
	{
		disx = City[n+1][0] - City[n][0];
		disy = City[n+1][1] - City[n][1];
	}
	SqrtResult = sqrt( disx * disx + disy *disy );
	return SqrtResult;
}

//计算temcity中两城市的路程
double CMySAAView::TemCityComputeSqrt( int n )
{
	double disx, disy, SqrtResult;
	if( n == 143 || n == -1 )
	{
		disx = TempCity[143][0] - TempCity[0][0];
		disy = TempCity[143][1] - TempCity[0][1];
	}
	else
	{
		disx = TempCity[n+1][0] - TempCity[n][0];
		disy = TempCity[n+1][1] - TempCity[n][1];
	}

	SqrtResult = sqrt( disx * disx + disy *disy );
	return SqrtResult;
}


//变换路径,结果保存在TempCity中，采用2变换法
//////////////////////////////////////////////////////////////////////////
double CMySAAView::Generate()
{
	int length,u, v;


	length = 2 + rand() % 141;             //选择要变换路径数[2,142]

	u = rand() % ( 145 - length );     //变换路径的首位置
	v = u + length - 1;                //变换路径的末位置

	//变换之外的位置先赋予TempCity
	//////////////////////////////////////////////////////////////////////////
	for( int i = 0; i < u ; i++ )
	{
		TempCity[i][0] = City[i][0];
		TempCity[i][1] = City[i][1];
	}
	if( v < N-1 )
	{
		for( int i = v + 1; i < N; i++ )
		{
			TempCity[i][0] = City[i][0];
			TempCity[i][1] = City[i][1];
		}
	}

	//如果length为奇数，将变换路径的中间结点赋予TempCity
	//////////////////////////////////////////////////////////////////////////
	if( length % 2 != 0 )
	{
		TempCity[u+length/2][0] = City[u+length/2][0];
		TempCity[u+length/2][1] = City[u+length/2][1];
	}

	//倒序
	//////////////////////////////////////////////////////////////////////////
	for( int i = 0; i < length / 2; i++ )
	{

		int uu = u + i;
		int vv = v - i;
		TempCity[uu][0] = City[vv][0];
		TempCity[vv][0] = City[uu][0];

		TempCity[uu][1] = City[vv][1];
		TempCity[vv][1] = City[uu][1];
	}
	double DisResult;       //变换后的结果的改变量
	double FirDisResult;    //第一个改变量
	double SecDisResult;    //第二个改变量

	FirDisResult = TemCityComputeSqrt( u -1 ) - CityComputeSqrt( u - 1 );
	SecDisResult = TemCityComputeSqrt( v ) - CityComputeSqrt( v );
	DisResult = FirDisResult + SecDisResult;
	return DisResult;

}

//2变法处理SAA
void CMySAAView :: OnErZhi()
{
	MyDialog Dlg;
	Dlg.DoModal();           //调用参数设置对话框
	
	//从对话框传入数据
	T = Dlg.Temp;
	L = Dlg.Le;
	TGene = Dlg.TGene;

	//窗口重绘
	Invalidate();
 	UpdateWindow();

	CClientDC dc(pView);           //设置dc

	int i, b, bChange = 0, s = 0;
	double result = 0;          //计算的路程长

	//打开文件并初始化路径
	ifstream ifs("CHN144.txt");
	ifs >> b;
	for( i = 0; i < N; ++i)
	{
		ifs >> b ;
		ifs >> City[i][0];
		ifs >> City[i][1];
	}

	//初始化路程长度
	result = ComputeResult();
	Excell = result ;
	printf( "%lf\n",result );

	//初始化随机种子
	srand( (unsigned)time( NULL ) );//使用当前的系统时间初始化随机数种子

	for( i = 0; i < N; i++ )
	{
		ExCity[i][0] = City[i][0];
		ExCity[i][1] = City[i][1];
	}


	s = 0;
	//连续50个解不变的时候终止

	while( s < 5 )
	{
	//	srand( (unsigned)time( NULL ) );
		bChange = 0;
		for( i = 0; i < L; i++ )
		{

			double dis_result = Generate();

			//	printf("dis_result=%lf\n", dis_result);

			double randomtime = double(rand()) /RAND_MAX ;

			//判断新解是否可接受
			if ( dis_result <= 0 || ( dis_result > 0 && exp( -1 * dis_result / T )>						randomtime ))
			{
				//	printf("dis_result=%lf\n", dis_result);
				for( int i = 0; i < N; i++ )
				{
					City[i][0] = TempCity[i][0];
					City[i][1] = TempCity[i][1];

				}

				result = result + dis_result ;
				bChange = 1;
			}

		}

		if( Excell > result)
		{
			Excell = result;
			for( i = 0; i < N; i++ )
			{
				ExCity[i][0] = City[i][0];
				ExCity[i][1] = City[i][1];
			}

		}


		//	printf("s=%d  t=%.16lf   %.13lf  %.11lf\n",s, T, result, Excell);
		T = T * 0.95;                      //温度的衰减函数
		if( bChange == 0 )
			s = s + 1;
		else
			s = 0;
	}

	//如果最终值大于最优值则最终结果取最优值
	if( Excell < result )
	{
		result = Excell;
		for( i = 0; i < N; i ++ )
		{
			City[i][0] = ExCity[i][0];
			City[i][1] = ExCity[i][1];
		}
	}

	
	//绘出路径//
	//////////////////////////////////////////////////////////////////////////
	for( i = 0;i < N-1; i++ )
	{
		dc.MoveTo( City[i][0]/10, City[i][1]/10 );
		dc.LineTo( City[i+1][0]/10, City[i+1][1]/10);
	}
	dc.MoveTo( City[N-1][0]/10, City[N-1][1]/10);
 	dc.LineTo( City[0][0]/10, City[0][1]/10 );

	//在视图中写出路径长度
	//////////////////////////////////////////////////////////////////////////
	CString str; 
	str.Format(_T("%lf"),result); 
	dc.SetBkMode(TRANSPARENT );
	dc.TextOut( 600, 80, "路径长度为：");
	dc.TextOut( 600, 100, str );
}



// CMySAAView 打印

BOOL CMySAAView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// 默认准备
	return DoPreparePrinting(pInfo);
}

void CMySAAView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 添加额外的打印前进行的初始化过程
}

void CMySAAView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 添加打印后进行的清除过程
}


// CMySAAView 诊断

#ifdef _DEBUG
void CMySAAView::AssertValid() const
{
	CView::AssertValid();
}

void CMySAAView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMySAADoc* CMySAAView::GetDocument() const // 非调试版本是内联的
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMySAADoc)));
	return (CMySAADoc*)m_pDocument;
}
#endif //_DEBUG


// CMySAAView 消息处理程序