📄 tspdlg.cpp
字号:
}
else if(lstrcmp(szResulte, _TEXT("停止计算")) == 0)
{
bfThreadRun = FALSE;
DWORD nExitCode = GetExitCodeThread(pThread->m_hThread, &nExitCode);
if(nExitCode == STILL_ACTIVE) pThread->ResumeThread();
WaitForSingleObject(pThread->m_hThread, /*INFINITE*/1000);
m_LoadBtn.EnableWindow(true);
m_CalcBtn.EnableWindow(false);
m_T0.EnableWindow(true);
m_a.EnableWindow(true);
m_L.EnableWindow(true);
m_X0.EnableWindow(true);
m_Xk.EnableWindow(true);
m_IterCnt.EnableWindow(true);
m_CalcBtn.SetWindowText(_TEXT("开始计算"));
}
}
double CTSPDlg::CalcEnergyDisp(const CPoint * pPoint, const UINT &nU, const UINT &nV, const UINT &nW)
{
double dResulte1 = 0, dResulte2 = 0;
if(nW == 0)
{
// 变化 2
// 计算当前状态能量
for(int i = (int)nU + 1; i <= (int)nV; i++)
{
dResulte1 += sqrt(double((pPoint[i].x - pPoint[i - 1].x) * (pPoint[i].x - pPoint[i - 1].x) +
(pPoint[i].y - pPoint[i - 1].y) * (pPoint[i].y - pPoint[i - 1].y)));
}
dResulte1 += sqrt(double((pPoint[nU - 1].x - pPoint[nU].x) * (pPoint[nU - 1].x - pPoint[nU].x) +
(pPoint[nU - 1].y - pPoint[nU].y) * (pPoint[nU - 1].y - pPoint[nU].y)));
dResulte1 += sqrt(double((pPoint[nV].x - pPoint[nV + 1].x) * (pPoint[nV].x - pPoint[nV + 1].x) +
(pPoint[nV].y - pPoint[nV + 1].y) * (pPoint[nV].y - pPoint[nV + 1].y)));
// 计算变化后态能量
for(int i = (int)nU + 1; i <= (int)nV; i++)
{
dResulte2 += sqrt(double((pPoint[i].x - pPoint[i - 1].x) * (pPoint[i].x - pPoint[i - 1].x) +
(pPoint[i].y - pPoint[i - 1].y) * (pPoint[i].y - pPoint[i - 1].y)));
}
dResulte2 += sqrt(double((pPoint[nU - 1].x - pPoint[nV].x) * (pPoint[nU - 1].x - pPoint[nV].x) +
(pPoint[nU - 1].y - pPoint[nV].y) * (pPoint[nU - 1].y - pPoint[nV].y)));
dResulte2 += sqrt(double((pPoint[nU].x - pPoint[nV + 1].x) * (pPoint[nU].x - pPoint[nV + 1].x) +
(pPoint[nU].y - pPoint[nV + 1].y) * (pPoint[nU].y - pPoint[nV + 1].y)));
}
else
{
// 变化 3
// 计算当前状态能量
dResulte1 += sqrt(double((pPoint[nU - 1].x - pPoint[nU].x) * (pPoint[nU - 1].x - pPoint[nU].x) +
(pPoint[nU - 1].y - pPoint[nU].y) * (pPoint[nU - 1].y - pPoint[nU].y)));
dResulte1 += sqrt(double((pPoint[nV].x - pPoint[nV + 1].x) * (pPoint[nV].x - pPoint[nV + 1].x) +
(pPoint[nV].y - pPoint[nV + 1].y) * (pPoint[nV].y - pPoint[nV + 1].y)));
dResulte1 += sqrt(double((pPoint[nW].x - pPoint[nW + 1].x) * (pPoint[nW].x - pPoint[nW + 1].x) +
(pPoint[nW].y - pPoint[nW + 1].y) * (pPoint[nW].y - pPoint[nW + 1].y)));
// 计算变化后态能量
dResulte2 += sqrt(double((pPoint[nU - 1].x - pPoint[nV + 1].x) * (pPoint[nU - 1].x - pPoint[nV + 1].x) +
(pPoint[nU - 1].y - pPoint[nV + 1].y) * (pPoint[nU - 1].y - pPoint[nV + 1].y)));
dResulte2 += sqrt(double((pPoint[nW].x - pPoint[nU].x) * (pPoint[nW].x - pPoint[nU].x) +
(pPoint[nW].y - pPoint[nU].y) * (pPoint[nW].y - pPoint[nU].y)));
dResulte2 += sqrt(double((pPoint[nV].x - pPoint[nW + 1].x) * (pPoint[nV].x - pPoint[nW + 1].x) +
(pPoint[nV].y - pPoint[nW + 1].y) * (pPoint[nV].y - pPoint[nW + 1].y)));
}
return dResulte2 - dResulte1;
}
double CTSPDlg::CalcEnergyResulte(const CPoint * pPoint, const UINT &size)
{
double dResults = 0;
for(int i = 0; i < (int)size - 1; i++)
{
dResults += sqrt(double((pPoint[i].x - pPoint[i + 1].x) * (pPoint[i].x - pPoint[i + 1].x) +
(pPoint[i].y - pPoint[i + 1].y) * (pPoint[i].y - pPoint[i + 1].y)));
}
dResults += sqrt(double((pPoint[size - 1].x - pPoint[0].x) * (pPoint[size - 1].x - pPoint[0].x) +
(pPoint[size - 1].y - pPoint[0].y) * (pPoint[size - 1].y - pPoint[0].y)));
return dResults;
}
// 变化能量
void CTSPDlg::ChangeEnergy(CPoint * pPoint, const UINT &size, const UINT &nU, const UINT &nV, const UINT &nW)
{
if(nW == 0)
{
// 变换 2
for(int i = 0; i < (int)((nV - nU + 1) / 2); i++)
{
pPoint[nU + i] = pPoint[nU + i] + pPoint[nV - i];
pPoint[nV - i] = pPoint[nU + i] - pPoint[nV - i];
pPoint[nU + i] = pPoint[nU + i] - pPoint[nV - i];
}
}
else
{
// 变换 3
CPoint * p_Point = new CPoint[size];
if(p_Point)
{
int j = 0;
for(int i = 0; i <= (int)nU - 1; i++) p_Point[j++] = pPoint[i];
for(int i = (int)nV + 1; i <= (int)nW; i++) p_Point[j++] = pPoint[i];
for(int i = (int)nU; i <= (int)nV; i++) p_Point[j++] = pPoint[i];
for(int i = (int)nW + 1; i <= (int)size - 1; i++) p_Point[j++] = pPoint[i];
}
for(int i = 0; i < (int)size; i++) pPoint[i] = p_Point[i];
delete []p_Point;
}
}
UINT _threadbody(LPVOID pParam)
{
g_PCOOL_PROCESS_METER lp_cpm = (g_COOL_PROCESS_METER *)pParam;
ASSERT(lp_cpm);
// 得到主程序类指针
CTSPDlg * this_tb = (CTSPDlg *)lp_cpm->this_p;
// 初始温度
double dT0 = lp_cpm->dT0;
// 终止温度
double dTe = lp_cpm->dTe;
// 初始接受率
double dX0 = lp_cpm->dX0;
// 终止接受率
double dXk = lp_cpm->dXk;
// 衰减因子
double da = lp_cpm->da;
// 接受 MapKOB 链长度
UINT nL = lp_cpm->nL;
// 迭代次数
UINT nIter = 0;
// 问题规模
UINT nSize = lp_cpm->nSize;
// 总变换数
UINT nMapKOB_all = nL * nL;
// 试验数据
CPoint * p_Results = lp_cpm->p_Results;
//
UINT nStopMKB = lp_cpm->nStopMKB;
// 纪录连续不接受解的次数
UINT nDebarMapkobCnt = 0;
// 迭代开始
while(*lp_cpm->bfThreadRun)
{
// 平均增量
double dEqualIncrement = 0;
// 增大变换个数
UINT nIncrementCnt = 0;
// 减小变换个数
UINT nLessenCnt = 0;
// 实际接受的变换数
UINT nMapKOB = 0;
for(int i = 0; i < (int)(nMapKOB_all); i++)
{
UINT nU = INRANDOM(1, nSize - 3);
UINT nV = INRANDOM(nU + 1, nSize - 2);
UINT nW = INRANDOM(nV + 1, nSize - 1);
// 产生新解并计算新旧解的温度能量差
double dIncrement = this_tb->CalcEnergyDisp(p_Results, nU, nV, nIter & 1 ? nW : 0);
// 判断
if(dIncrement > 0)
{
if(exp(-dIncrement / dT0) * 1000000.0 > (double)INRANDOM(0, 999999))
{
// 接受
this_tb->ChangeEnergy(p_Results, nSize + 1, nU, nV, nIter & 1 ? nW : 0);
nMapKOB++;
}
// 纪录增量个数
nIncrementCnt++;
// 纪录累加增量
dEqualIncrement += dIncrement;
}
else
{
// 接受
this_tb->ChangeEnergy(p_Results, nSize + 1, nU, nV, nIter & 1 ? nW : 0);
// 纪录减小个数
nLessenCnt++;
nMapKOB++;
}
// 纪录实际 MapKOB 链长度
if(nMapKOB >= nL) break;
} // end for nMapKOB
// 显示实时状态
TCHAR szResulte[32];
// 显示当前温度
_stprintf(szResulte, _TEXT("%.5f"), dT0);
this_tb->m_T0.SetWindowText(szResulte);
// 显示当前迭代次数
_stprintf(szResulte, _TEXT("%d/%d"), nIter + 1, lp_cpm->nIter);
this_tb->m_IterCnt.SetWindowText(szResulte);
// 显示当前结果
double dResulting = this_tb->CalcEnergyResulte(p_Results, nSize + 1);
_stprintf(szResulte, _TEXT("中间 %s%s：%d"),
nIter & 1 ? _TEXT("●") : _TEXT("◎"), nIter & 1 ? _TEXT("◎") : _TEXT("●"),
(int)dResulting);
this_tb->m_EResulte.SetWindowText(szResulte);
// 保存计算过程
CPoint point(nIter + 1, (int)dResulting);
this_tb->std_pt.push_back(point);
// 温度衰减
dT0 *= da;
// 纪录已迭代次数
nIter++;
// 判断终止条件
// 计算终止接受率
double dXt = this_tb->CalcXk(dEqualIncrement / (double)nIncrementCnt, nLessenCnt, nIncrementCnt, dT0);
// 显示当前接受率
_stprintf(szResulte, _TEXT("%.8f"), dXt);
this_tb->m_X0.SetWindowText(szResulte);
// 如果当前接受率小于终止接受率且满足当前温度足够小条件则停止迭代
if(dXt < dXk && dXt < dX0 && dT0 <= dTe) break;
// 如果迭代次数达到最大迭代次数则停止迭代
if(nIter >= lp_cpm->nIter) break;
// 纪录每条 Mapkob 链中的解，用于当 5 条 Mapkob 链中的解无变化时终止迭代
if(nMapKOB == 0) nDebarMapkobCnt++;
else nDebarMapkobCnt = 0;
if(nDebarMapkobCnt == nStopMKB) break;
}
// 发送绘图消息
PostMessage(this_tb->GetSafeHwnd(), WM_DRAW_PLOT, (WPARAM)p_Results, (LPARAM)nSize);
return 0;
}
void CTSPDlg::OnDestroy()
{
CDialog::OnDestroy();
// TODO: 在此处添加消息处理程序代码
if(pThread)
{
bfThreadRun = FALSE;
WaitForSingleObject(pThread->m_hThread, INFINITE);
}
if(g_cpm.p_Results)
{
delete []g_cpm.p_Results;
g_cpm.p_Results = NULL;
}
if(pThread)
{
delete pThread;
pThread = NULL;
}
}
LRESULT CTSPDlg::OnDrawPlot(WPARAM wParam, LPARAM lParam)
{
// 开始绘图（演示最终结果）
if(m_hGrahp1)
{
PEdestroy(m_hGrahp1);
Invalidate();
m_hGrahp1 = NULL;
}
CRect rect;
m_Palette1.GetClientRect(rect);
m_hGrahp1 = PEcreate(PECONTROL_SGRAPH, WS_VISIBLE, &rect, m_Palette1.GetSafeHwnd(), 1000);
UINT nSize = (UINT)lParam;
// 显示 1 条曲线（计算结果）
PEnset(m_hGrahp1, PEP_nSUBSETS, 1);
PEnset(m_hGrahp1, PEP_nPOINTS, nSize + 1);
// 绘图
CPoint * lpPoint = (CPoint *)wParam;
for(int i = 0; i < (int)nSize; i++)
{
float faXDARA = (float)lpPoint[i].x;
float faYDATA = (float)lpPoint[i].y;
PEvsetcellEx(m_hGrahp1, PEP_faXDATA, 0, i, &faXDARA);
PEvsetcellEx(m_hGrahp1, PEP_faYDATA, 0, i, &faYDATA);
}
// 高亮无边框
PEnset(m_hGrahp1, PEP_nQUICKSTYLE, PEQS_LIGHT_NO_BORDER);
// 主标题
PEszset(m_hGrahp1, PEP_szMAINTITLE, _TEXT("货郎担问题求解结果图"));
// 副标题（取消）
PEszset(m_hGrahp1, PEP_szSUBTITLE, _TEXT(""));
// 曲线颜色
DWORD dwColor[1] = {RGB(0, 0, 255)};
PEvset(m_hGrahp1, PEP_dwaSUBSETCOLORS, dwColor, 1);
// 曲线标签
PEvsetcell(m_hGrahp1, PEP_szaSUBSETLABELS, 0, _TEXT("结果演示"));
// 设置第一个工作轴
PEnset(m_hGrahp1, PEP_nWORKINGAXIS, 0);
// X 轴标签
PEszset(m_hGrahp1, PEP_szXAXISLABEL, _TEXT("城市位置坐标 X 轴"));
// 第一个 Y 轴标签
PEszset(m_hGrahp1, PEP_szYAXISLABEL, _TEXT("城市位置坐标 Y 轴"));
// 曲线风格
PEnset(m_hGrahp1, PEP_nPLOTTINGMETHODII, PEGPM_LINE);
// 显示点
PEnset(m_hGrahp1, PEP_bMARKDATAPOINTS, TRUE);
// 开始绘图（演示最终结果）
UINT nCourseSize = (UINT)std_pt.size();
if(nCourseSize <= 0) goto DRAW_END;
CPoint *pCourse = new CPoint[nCourseSize];
myASSERT(pCourse);
// 保存过程数据
int k = 0;
for (std_itor_pt = std_pt.begin(); std_itor_pt != std_pt.end(); ++std_itor_pt)
pCourse[k++] = (*std_itor_pt);
// 清除链表
std_pt.erase(std_pt.begin(), std_pt.end());
std_pt.clear();
if(m_hGrahp2)
{
PEdestroy(m_hGrahp2);
Invalidate();
m_hGrahp2 = NULL;
}
m_Palette2.GetClientRect(rect);
m_hGrahp2 = PEcreate(PECONTROL_SGRAPH, WS_VISIBLE, &rect, m_Palette2.GetSafeHwnd(), 1000);
// 显示 1 条曲线（计算结果）
PEnset(m_hGrahp2, PEP_nSUBSETS, 1);
PEnset(m_hGrahp2, PEP_nPOINTS, nCourseSize);
// 绘图
for(int i = 0; i < (int)nCourseSize; i++)
{
float faXDARA = (float)pCourse[i].x;
float faYDATA = (float)pCourse[i].y;
PEvsetcellEx(m_hGrahp2, PEP_faXDATA, 0, i, &faXDARA);
PEvsetcellEx(m_hGrahp2, PEP_faYDATA, 0, i, &faYDATA);
}
// 高亮无边框
PEnset(m_hGrahp2, PEP_nQUICKSTYLE, PEQS_LIGHT_NO_BORDER);
// 主标题
PEszset(m_hGrahp2, PEP_szMAINTITLE, _TEXT("货郎担问题求解过程图"));
// 副标题（取消）
PEszset(m_hGrahp2, PEP_szSUBTITLE, _TEXT(""));
// 曲线颜色
DWORD dwColor2[1] = {RGB(128, 128, 128)};
PEvset(m_hGrahp2, PEP_dwaSUBSETCOLORS, dwColor2, 1);
// 曲线标签
PEvsetcell(m_hGrahp2, PEP_szaSUBSETLABELS, 0, _TEXT("过程演示"));
// 设置第一个工作轴
PEnset(m_hGrahp2, PEP_nWORKINGAXIS, 0);
// X 轴标签
PEszset(m_hGrahp2, PEP_szXAXISLABEL, _TEXT("迭代次数"));
// 第一个 Y 轴标签
PEszset(m_hGrahp2, PEP_szYAXISLABEL, _TEXT("当前结果"));
// 曲线风格
PEnset(m_hGrahp2, PEP_nPLOTTINGMETHODII, PEGPM_LINE);
// 显示点
PEnset(m_hGrahp2, PEP_bMARKDATAPOINTS, TRUE);
if(pCourse) delete []pCourse;
// 显示文字结果
TCHAR szResult[32];
_stprintf(szResult, _TEXT("最终结果：%d"), (int)CalcEnergyResulte(lpPoint, nSize + 1));
m_EResulte.SetWindowText(szResult);
m_LoadBtn.EnableWindow(true);
m_T0.EnableWindow(true);
m_a.EnableWindow(true);
m_L.EnableWindow(true);
m_X0.EnableWindow(true);
m_Xk.EnableWindow(true);
m_IterCnt.EnableWindow(true);
m_CalcBtn.SetWindowText(_TEXT("开始计算"));
DRAW_END:
return 0;
}
double CTSPDlg::CalcT0(CPoint * pPoint, const UINT &size, const double dX0)
{
// 增大变换个数
UINT nIncrementCnt = 0;
// 减小变换个数
UINT nLessenCnt = 0;
// 平均增量
double dEqualIncrement = 0;
// 变换个数
int nNumber = (int)size < 10 ? 100 : (int)(size * size);
for(int i = 0; i < nNumber; i++)
{
UINT nU = INRANDOM(1, size - 3);
UINT nV = INRANDOM(nU + 1, size - 2);
UINT nW = INRANDOM(nV + 1, size - 1);
// 产生新解并计算新旧解的温度能量差
double dIncrement = CalcEnergyDisp(pPoint, nU, nV, i & 1 ? nW : 0);
// 计算增大变换个数和减小变换个数
if(dIncrement >= 0)
{
//if(exp(-dIncrement / 0.0) * 1000000.0 > (double)INRANDOM(0, 999999))
// ChangeEnergy(pPoint, size, nU, nV, i & 1 ? nW : 0);
dEqualIncrement += dIncrement;
nIncrementCnt++;
}
else
{
// ChangeEnergy(pPoint, size, nU, nV, i & 1 ? nW : 0);
nLessenCnt++;
}
}
dEqualIncrement /= (double)nIncrementCnt;
return (dEqualIncrement / log((double)nIncrementCnt / ((double)nIncrementCnt * dX0 - (double)nLessenCnt * (1.0 - dX0))));
}
double CTSPDlg::CalcXk(const double &dEqualIncrement, const UINT &nM1, const UINT &nM2, const double dT0)
{
return ((double)nM1 + (double)nM2 * exp(-dEqualIncrement / dT0)) / ((double)nM1 + (double)nM2);
}
double CTSPDlg::CalcPtoP(const CPoint &Point1, const CPoint &Point2)
{
return sqrt(double((Point1.x - Point2.x) * (Point1.x - Point2.x) +
(Point1.y - Point2.y) * (Point1.y - Point2.y)));
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -