#include "stdafx.h"
|
#include "GreedyTSP.h"
|
|
#include <math.h>
|
#include <float.h>
|
|
CGreedyTSP::CGreedyTSP(void)
|
{
|
m_pPathGraph = NULL;
|
|
Reset();
|
}
|
|
CGreedyTSP::~CGreedyTSP(void)
|
{
|
Reset();
|
}
|
|
void CGreedyTSP::Reset()
|
{
|
// vector
|
m_vecPathData.clear();
|
m_vecPathResult.clear();
|
m_vecPathAdded.clear();
|
|
// graph
|
if (m_pPathGraph)
|
{
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
delete [] m_pPathGraph[i];
|
}
|
delete [] m_pPathGraph;
|
}
|
m_pPathGraph = NULL;
|
|
m_nStartIndex = -1;
|
m_nPathCount = 0;
|
m_dTotalDistance = 0.0;
|
|
m_ptStart.nPosX = -1;
|
m_ptStart.nPosY = -1;
|
}
|
|
void CGreedyTSP::SetPathData(const VectorPathData& vecPathData, const SPathData& ptStart)
|
{
|
if (vecPathData.size()<0) return;
|
|
Reset();
|
|
m_nPathCount = (int)vecPathData.size();
|
m_pPathGraph = new double*[m_nPathCount];
|
|
m_ptStart = ptStart;
|
|
// path data copy
|
m_vecPathData = vecPathData;
|
m_vecPathResult.resize(m_nPathCount);
|
m_vecPathAdded.resize(m_nPathCount);
|
|
// path graph
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
m_vecPathAdded[i] = false;
|
m_pPathGraph[i] = new double [m_nPathCount];
|
for (int j=0; j<m_nPathCount; j++)
|
{
|
if (i==j)
|
m_pPathGraph[i][j] = 0.0;
|
else
|
m_pPathGraph[i][j] = CalculateDistance(m_vecPathData[i], m_vecPathData[j]);
|
}
|
}
|
|
// path result
|
InitPathResult(ptStart);
|
|
m_dTotalDistance = GetTotalDistance();
|
|
}
|
|
void CGreedyTSP::SetPathData(const VectorPathData& vecPathData, const VectorInteger& vecPathResult)
|
{
|
if (vecPathData.size()<1 || vecPathData.size()!=vecPathResult.size()) return;
|
|
Reset();
|
|
m_nPathCount = (int)vecPathData.size();
|
m_pPathGraph = new double*[m_nPathCount];
|
|
// path data
|
m_vecPathData = vecPathData;
|
m_vecPathResult = vecPathResult;
|
m_vecPathAdded.resize(m_nPathCount);
|
|
// path graph
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
m_vecPathAdded[i] = false;
|
m_pPathGraph[i] = new double[m_nPathCount];
|
for (int j=0; j<m_nPathCount; j++)
|
{
|
if (i==j)
|
m_pPathGraph[i][j] = 0.0;
|
else
|
m_pPathGraph[i][j] = CalculateDistance(m_vecPathData[i], m_vecPathData[j]);
|
}
|
}
|
|
m_dTotalDistance = GetTotalDistance();
|
}
|
|
double CGreedyTSP::CalculateTSP()
|
{
|
if (m_nPathCount<1) return -1.0;
|
|
SortingPathResult();
|
|
return m_dTotalDistance;
|
}
|
|
int CGreedyTSP::GetPathCount() const
|
{
|
return m_nPathCount;
|
}
|
|
int CGreedyTSP::GetPathResult(int nIndex) const
|
{
|
if (nIndex<0 || nIndex>=m_nPathCount) return -1;
|
return m_vecPathResult[nIndex];
|
}
|
|
const SPathData* CGreedyTSP::GetPathData(int nIndex) const
|
{
|
if (nIndex<0 || nIndex>=m_nPathCount) return NULL;
|
return &(m_vecPathData[nIndex]);
|
}
|
|
VectorInteger* CGreedyTSP::GetPathResult()
|
{
|
return &m_vecPathResult;
|
}
|
|
VectorPathData* CGreedyTSP::GetPathData()
|
{
|
return &m_vecPathData;
|
}
|
|
double CGreedyTSP::GetPathResult(VectorInteger& vecPathResult)
|
{
|
vecPathResult.resize(m_nPathCount);
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
vecPathResult[i] = m_vecPathResult[i];
|
}
|
|
return m_dTotalDistance;
|
}
|
|
double CGreedyTSP::GetTotalDistance()
|
{
|
double distance = 0.0;
|
|
if (m_ptStart.nPosX!=-1 || m_ptStart.nPosX!=-1)
|
{
|
distance += CalculateDistance(m_ptStart, m_vecPathData[m_vecPathResult[0]]);
|
}
|
|
for (int i=1; i<m_nPathCount; i++)
|
{
|
distance += m_pPathGraph[m_vecPathResult[i-1]][m_vecPathResult[i]];
|
}
|
return distance;
|
}
|
|
double CGreedyTSP::GetTotalDistance(const VectorInteger& vecPathResult)
|
{
|
int nPathCount = (int)vecPathResult.size();
|
|
double distance = 0.0;
|
for (int i=1; i<nPathCount; i++)
|
{
|
distance += m_pPathGraph[vecPathResult[i-1]][vecPathResult[i]];
|
}
|
return distance;
|
}
|
|
double CGreedyTSP::CalculateDistance(const POINT& pt1, const POINT &pt2)
|
{
|
double dx = double(pt1.x-pt2.x) / 1000.0;
|
double dy = double(pt1.y-pt2.y) / 1000.0;
|
return sqrt(dx*dx + dy*dy);
|
}
|
|
double CGreedyTSP::CalculateDistance(const SPathData& pt1, const SPathData &pt2)
|
{
|
double dx = double(pt1.nPosX-pt2.nPosX) / 1000.0;
|
double dy = double(pt1.nPosY-pt2.nPosY) / 1000.0;
|
return sqrt(dx*dx + dy*dy);
|
}
|
|
double CGreedyTSP::CalculateDistanceX( const POINT& pt1, const POINT &pt2 )
|
{
|
double dx = double(pt1.x-pt2.x) / 1000.0;
|
return fabs(dx);
|
}
|
|
double CGreedyTSP::CalculateDistanceX( const SPathData& pt1, const SPathData &pt2 )
|
{
|
double dx = double(pt1.nPosX-pt2.nPosX) / 1000.0;
|
return fabs(dx);
|
}
|
|
double CGreedyTSP::CalculateDistanceY( const POINT& pt1, const POINT &pt2 )
|
{
|
double dy = double(pt1.y-pt2.y) / 1000.0;
|
return fabs(dy);
|
}
|
|
double CGreedyTSP::CalculateDistanceY( const SPathData& pt1, const SPathData &pt2 )
|
{
|
double dy = double(pt1.nPosY-pt2.nPosY) / 1000.0;
|
return fabs(dy);
|
}
|
|
int CGreedyTSP::SelectPath(int nCurIdx)
|
{
|
int nMinIdx = -1;
|
double dTempMin = DBL_MAX;
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
// Ãß°¡µÈ pathÀÎÁö È®ÀÎ.
|
if (m_vecPathAdded[i]==true) continue;
|
|
if (dTempMin > m_pPathGraph[nCurIdx][i])
|
{
|
dTempMin = m_pPathGraph[nCurIdx][i];
|
nMinIdx = i;
|
}
|
}
|
|
if (nMinIdx==-1)
|
{
|
return -1;
|
}
|
|
// Ãß°¡çÀ½À» ÀúÀå.
|
m_vecPathAdded[nMinIdx] = true;
|
|
return nMinIdx;
|
}
|
|
void CGreedyTSP::InitPathResult(const SPathData& ptStart)
|
{
|
if (m_nPathCount<1) return;
|
|
m_nStartIndex = -1;
|
double dMinDist = DBL_MAX;
|
double dTempDist = 0.0;
|
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
dTempDist = CalculateDistance(ptStart, m_vecPathData[i]);
|
if (dMinDist>dTempDist)
|
{
|
m_nStartIndex = i;
|
dMinDist = dTempDist;
|
}
|
}
|
|
if (m_nStartIndex==-1)
|
{
|
return;
|
}
|
|
m_vecPathResult[0] = m_nStartIndex;
|
|
// Ãß°¡çÀ½À» ÀúÀå.
|
m_vecPathAdded[m_nStartIndex] = true;
|
|
for (int i=1; i<m_nPathCount; i++)
|
{
|
m_vecPathResult[i] = SelectPath(m_vecPathResult[i-1]);
|
}
|
}
|
|
BOOL CGreedyTSP::SortingPathResult()
|
{
|
if (m_nPathCount<1) return FALSE;
|
|
int nStartIndex = -1;
|
double dMinDist = DBL_MAX;
|
double dTempDist = 0.0;
|
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
dTempDist = CalculateDistance(m_ptStart, m_vecPathData[i]);
|
if (dMinDist>dTempDist)
|
{
|
nStartIndex = i;
|
dMinDist = dTempDist;
|
}
|
}
|
|
for (int i=0; i<m_nPathCount; i++)
|
{
|
if (nStartIndex==m_vecPathResult[i])
|
{
|
nStartIndex = i;
|
break;
|
}
|
}
|
|
VectorInteger vecPathResult;
|
vecPathResult.reserve(m_nPathCount);
|
|
for (int i=nStartIndex; i<m_nPathCount; i++)
|
{
|
vecPathResult.push_back(m_vecPathResult[i]);
|
}
|
|
for (int i=0; i<nStartIndex; i++)
|
{
|
vecPathResult.push_back(m_vecPathResult[i]);
|
}
|
|
m_vecPathResult = vecPathResult;
|
|
return TRUE;
|
}
|
