tspdlg.cpp

退火算法的一个演示程序,含有源代码,通过画面演示退火算法的原理!

// TSPDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "TSP.h"
#include "TSPDlg.h"
#include ".\tspdlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

#pragma comment(lib, "../Graph/PEGRP32C.lib")

#define WM_DRAW_PLOT	WM_APP+100
// 参数结构
typedef struct
{
	// 问题规模
	UINT nSize;
	// 初始温度
	double dT0;
	// 衰减因子
	double da;
	// MapKOB链长度（固定）
	UINT nL;
	// 初始接受率
	double dX0;
	// 终止接受率
	double dXk;
	// 迭代次数
	UINT nIter;
	// 问题数据
	CPoint *p_Results;
	// 最大坐标值
	CPoint MaxCoord;
	// 线程是否运行标志
	BOOL *bfThreadRun;
	// 本类指针
	PVOID this_p;
	// 终止温度
	double dTe;
	// 无变动解的 mapkob 链数
	UINT nStopMKB;

} g_COOL_PROCESS_METER, *g_PCOOL_PROCESS_METER;
g_COOL_PROCESS_METER g_cpm;


// 线程对象
CWinThread * pThread;
// 线程函数主体
UINT _threadbody(LPVOID pParam);

// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// 对话框数据
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CTSPDlg 对话框



CTSPDlg::CTSPDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTSPDlg::IDD, pParent)
	, m_hGrahp1(NULL)
	, m_hGrahp2(NULL)
	, bfThreadRun(TRUE)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CTSPDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Control(pDX, IDC_EDIT_To, m_T0);
	DDX_Control(pDX, IDC_EDIT_a, m_a);
	DDX_Control(pDX, IDC_EDIT_L, m_L);
	DDX_Control(pDX, IDC_EDIT_Xo, m_X0);
	DDX_Control(pDX, IDC_EDIT_Xk, m_Xk);
	DDX_Control(pDX, IDC_EDIT_ITERCNT, m_IterCnt);
	DDX_Control(pDX, IDC_S_RESULTE, m_SResulte);
	DDX_Control(pDX, IDC_E_RESULTE, m_EResulte);
	DDX_Control(pDX, IDC_PALETTE, m_Palette1);
	DDX_Control(pDX, IDC_LOADQUESDATA_BTN, m_LoadBtn);
	DDX_Control(pDX, IDC_CALC_BTN, m_CalcBtn);
	DDX_Control(pDX, IDC_PALETTE2, m_Palette2);
	DDX_Control(pDX, IDC_K_RESULTE, m_KResulte);
	DDX_Control(pDX, IDC_EDIT_Te, m_Te);
	DDX_Control(pDX, IDC_EDIT_STOPMKBCNT, m_stop_mkb_cnt);
}

BEGIN_MESSAGE_MAP(CTSPDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_LOADQUESDATA_BTN, OnBnClickedLoadquesdataBtn)
	ON_BN_CLICKED(IDC_CALC_BTN, OnBnClickedCalcBtn)
	ON_WM_DESTROY()
	ON_MESSAGE(WM_DRAW_PLOT ,OnDrawPlot)
END_MESSAGE_MAP()


// CTSPDlg 消息处理程序

BOOL CTSPDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 将\“关于...\”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码
	memset(&g_cpm, 0, sizeof(g_cpm));
	g_cpm.MaxCoord.x = 0;
	g_cpm.MaxCoord.y = 0;
	g_cpm.bfThreadRun = &bfThreadRun;
	g_cpm.this_p = this;
	g_cpm.p_Results = NULL;
	g_cpm.nIter = 0;
	g_cpm.nSize = 0;
	g_cpm.nL = 0;
	g_cpm.da = 0.9;
	g_cpm.dT0 = 0;
	g_cpm.dX0 = 0.9;
	g_cpm.dXk = 0.001;
	g_cpm.dTe = 0.01;
	g_cpm.nStopMKB = 5;

	// 显示默认参数量
	m_a.SetWindowText(_TEXT("0.9"));
	m_X0.SetWindowText(_TEXT("0.9"));
	m_Xk.SetWindowText(_TEXT("0.001"));
	m_Te.SetWindowText(_TEXT("0.01"));
	m_stop_mkb_cnt.SetWindowText(_TEXT("5"));
	
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

void CTSPDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CTSPDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR CTSPDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CTSPDlg::OnBnClickedLoadquesdataBtn()
{
	// TODO: 在此添加控件通知处理程序代码
	// 加载问题数据文件
	CFileDialog dlg(TRUE, _TEXT("INI"), NULL,
		OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,
		_TEXT("INI(*.ini)|*.ini|*.ini|所有文件(*.*)|*.*||"));
	if(dlg.DoModal() != IDOK) return;
	
	g_cpm.MaxCoord.x = 0;
	g_cpm.MaxCoord.y = 0;
	g_cpm.nIter = 0;
	g_cpm.nSize = 0;
	g_cpm.nL = 0;
	g_cpm.da = 0.9;
	g_cpm.dT0 = 0;
	g_cpm.dX0 = 0.9;
	g_cpm.dXk = 0.001;
	g_cpm.dTe = 0.01;
	g_cpm.nStopMKB = 5;

	// 显示默认参数量
	m_a.SetWindowText(_TEXT("0.9"));
	m_Xk.SetWindowText(_TEXT("0.001"));
	m_X0.SetWindowText(_TEXT("0.9"));
	m_Te.SetWindowText(_TEXT("0.01"));
	m_stop_mkb_cnt.SetWindowText(_TEXT("5"));

	CIni m_File(dlg.GetPathName());
	TCHAR szKey[8], szCoord[64];
	// 获取到问题规模
	g_cpm.nSize = m_File.GetInt(_TEXT("SIZE"));
	// 分配保存问题数据内存空间
	if(g_cpm.p_Results)
	{
		delete []g_cpm.p_Results;
		g_cpm.p_Results = NULL;
	}
	g_cpm.p_Results = new CPoint[g_cpm.nSize + 1];
	myASSERT(g_cpm.p_Results);
	// 读取问题数据
	for(int nKey = 0; nKey < (int)g_cpm.nSize; nKey++)
	{
		_stprintf(szKey, _TEXT("%d"), nKey);
		m_File.GetString(szKey, szCoord, 64);
		TCHAR *pPt = _tcschr(szCoord, _TEXT(','));
		if(pPt)
		{
			TCHAR szTmp[64];
			_tcscpy(szTmp, szCoord);
			szTmp[lstrlen(szCoord) - lstrlen(pPt)] = _TEXT('\0');
			g_cpm.p_Results[nKey].x = _tstoi(szTmp);
			g_cpm.p_Results[nKey].y = _tstoi(++pPt);
			// 纪录最大值
			if(g_cpm.p_Results[nKey].x > g_cpm.MaxCoord.x) g_cpm.MaxCoord.x = g_cpm.p_Results[nKey].x;
			if(g_cpm.p_Results[nKey].y > g_cpm.MaxCoord.y) g_cpm.MaxCoord.y = g_cpm.p_Results[nKey].y;
		}
		else
		{
			g_cpm.p_Results[nKey].x = INRANDOM(0, g_cpm.MaxCoord.x);
			g_cpm.p_Results[nKey].y = INRANDOM(0, g_cpm.MaxCoord.y);
		}
	}		// end for nKey
	g_cpm.p_Results[g_cpm.nSize].x = g_cpm.p_Results[0].x;
	g_cpm.p_Results[g_cpm.nSize].y = g_cpm.p_Results[0].y;

	// 计算冷却进度表
	TCHAR szResulte[32];
	// 终止迭代的无变动mapkob链数
	m_stop_mkb_cnt.GetWindowText(szResulte, 32);
	g_cpm.nStopMKB = _tstoi(szResulte);
	// 初始接受率
	m_X0.GetWindowText(szResulte, 32);
	g_cpm.dX0 = _tstof(szResulte);
	// 初始温度
	_stprintf(szResulte, _TEXT("%.2f"), CalcT0(g_cpm.p_Results, g_cpm.nSize + 1, g_cpm.dX0));
	m_T0.SetWindowText(szResulte);
	// MapKOB 链长度
	_stprintf(szResulte, _TEXT("%d"), g_cpm.nSize);
	m_L.SetWindowText(szResulte);
	// 迭代次数
	_stprintf(szResulte, _TEXT("%d"), g_cpm.nSize * g_cpm.nSize * g_cpm.nSize);
	m_IterCnt.SetWindowText(szResulte);
	// 显示默认结果
	double dResulte = CalcEnergyResulte(g_cpm.p_Results, g_cpm.nSize + 1);
	CPoint * point = new CPoint[g_cpm.nSize + 1];
	myASSERT(point);
	for(int i = 0; i < (int)g_cpm.nSize; i++)
		point[i] = g_cpm.p_Results[i];
	for(int i = 0; i < (int)g_cpm.nSize; i++)
		std_pt.push_back(point[i]);
	for(int i = 0; i < (int)g_cpm.nSize; i++)
	{
		CPoint pt(0, (LONG)dResulte);
		int j = 0;
		for(std_itor_pt = std_pt.begin(); std_itor_pt != std_pt.end(); ++std_itor_pt)
		{
			LONG nLong = (LONG)CalcPtoP(point[i], (*std_itor_pt));
			if(pt.y > nLong)
			{
				pt.y = nLong;
				pt.x = j;
			}
			j++;
		}
		j = 0;
		for(std_itor_pt = std_pt.begin(); std_itor_pt != std_pt.end(); ++std_itor_pt)
		{
			if (j++ == pt.x)
			{
				point[i + 1] = (*std_itor_pt);
				std_pt.erase(std_itor_pt);
				break;
			}
		}
	}		// end i
	std_pt.erase(std_pt.begin(), std_pt.end());
	std_pt.clear();
	point[g_cpm.nSize].x = point[0].x;
	point[g_cpm.nSize].y = point[0].y;

	_stprintf(szResulte, _TEXT("原始结果：%d"), (int)dResulte);
	m_SResulte.SetWindowText(szResulte);
	_stprintf(szResulte, _TEXT("优化结果：%d"), (int)CalcEnergyResulte(point, g_cpm.nSize + 1));
	m_KResulte.SetWindowText(szResulte);
	if(point) delete []point;
	// 计算按钮可见
	m_CalcBtn.EnableWindow(true);

	// 发送绘图消息（绘制原始路径）
	SendMessage(WM_DRAW_PLOT, (WPARAM)g_cpm.p_Results, (LPARAM)g_cpm.nSize);
}

void CTSPDlg::OnBnClickedCalcBtn()
{
	// TODO: 在此添加控件通知处理程序代码
	TCHAR szResulte[32];
	m_CalcBtn.GetWindowText(szResulte, 32);
	if(lstrcmp(szResulte, _TEXT("开始计算")) == 0)
	{
		// 先屏蔽掉参数控件的可编辑属性
		m_LoadBtn.EnableWindow(false);
		m_T0.EnableWindow(false);
		m_a.EnableWindow(false);
		m_L.EnableWindow(false);
		m_X0.EnableWindow(false);
		m_Xk.EnableWindow(false);
		m_IterCnt.EnableWindow(false);
		m_CalcBtn.SetWindowText(_TEXT("停止计算"));

		// 终止迭代的无变动mapkob链数
		m_stop_mkb_cnt.GetWindowText(szResulte, 32);
		g_cpm.nStopMKB = _tstoi(szResulte);
		// 终止温度
		m_Te.GetWindowText(szResulte, 32);
		g_cpm.dTe = _tstof(szResulte);
		// 初始接受率
		m_X0.GetWindowText(szResulte, 32);
		g_cpm.dX0 = _tstof(szResulte);
		// 终止接受率
		m_Xk.GetWindowText(szResulte, 32);
		g_cpm.dXk = _tstof(szResulte);
		// MapKOB 链长度
		m_L.GetWindowText(szResulte, 32);
		g_cpm.nL = _tstoi(szResulte);
		// 迭代次数
		m_IterCnt.GetWindowText(szResulte, 32);
		g_cpm.nIter = _tstoi(szResulte);
		// 衰减因子
		m_a.GetWindowText(szResulte, 32);
		g_cpm.da = _tstof(szResulte);
		// 初始温度
		m_T0.GetWindowText(szResulte, 32);
		if(lstrlen(szResulte) == 0)
		{
			g_cpm.dT0 = CalcT0(g_cpm.p_Results, g_cpm.nSize + 1, g_cpm.dX0);
			_stprintf(szResulte, _TEXT("%.2f"), g_cpm.dT0);
			m_T0.SetWindowText(szResulte);
		}
		else g_cpm.dT0 = _tstof(szResulte);

		// 清楚计算过程
		if (std_pt.size() > 0)
		{
			std_pt.erase(std_pt.begin(), std_pt.end());
			std_pt.clear();
		}

		// 启动计算线程
		if(pThread)
		{
			delete pThread;
			pThread = NULL;
		}
		bfThreadRun = TRUE;
		pThread = AfxBeginThread(_threadbody, &g_cpm ,
			THREAD_PRIORITY_NORMAL, 0, CREATE_SUSPENDED, NULL);
		pThread->m_bAutoDelete = false;
		pThread->ResumeThread();