Ongoing50 #3584 CF AOI Review 시뮬레이션 기능 정상화

LYW

2021-08-17 67bcdefa0aae33fcf16333967744a9aafcaf9433

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include "stdafx.h"
#include "DynamicTSP.h"
#include <math.h>
#include <float.h>
 
CDynamicTSP::CDynamicTSP(void)
{
    m_pBitArray = NULL;
    m_pDP = NULL;
 
    Reset();
}
 
CDynamicTSP::~CDynamicTSP(void)
{
    Reset();
}
 
void CDynamicTSP::Reset()
{
    if (m_pDP)
    {
        for (int i=0; i<m_nPathCount; i++)
        {
            delete [] m_pDP[i];
        }
        delete [] m_pDP;
    }
    m_pDP = NULL;
 
    if (m_pBitArray)
    {
        delete [] m_pBitArray;
    }
    m_pBitArray = NULL;
 
    m_nSubSetCount = 0;
}
 
void CDynamicTSP::SetPathData(const VectorPathData& vecPathData, const SPathData& ptStart)
{
    m_nPathCount = (int)vecPathData.size();
    if (m_nPathCount<1) return;
 
    Reset();
 
    CGreedyTSP::SetPathData(vecPathData, ptStart);
 
    // new
    m_pBitArray = new int[m_nPathCount];
    m_pDP = new SDP*[m_nPathCount];
 
    m_nSubSetCount = 1<<m_nPathCount;
 
    for (int i=0; i<m_nPathCount; i++)
    {
        m_pBitArray[i] = 1<<i;
 
        m_pDP[i] = new SDP[m_nSubSetCount];
        memset(m_pDP[i], 0, sizeof(SDP)*m_nSubSetCount);
    }
}
 
int get_bit_index (int path)
{
    for (int i=0; i<32; i++)
    {
        if ((path>>i) & 1)
        {
            return i;
        }
    }
    return -1;
}
 
double CDynamicTSP::TSP_Process(int nFrom, int nPathSet, int nLen)
{
    // setÀÌ ÇϳªÀ϶§
    if (nLen == 1)
    {
        int to = get_bit_index(nPathSet);
        return m_pPathGraph[nFrom][to];
    }
 
    // ÀúÀåÇÑ °ªÀ» ÀÌ¿ë
    if (m_pDP[nFrom][nPathSet].dMinCost)
    {
        return m_pDP[nFrom][nPathSet].dMinCost;
    }
 
    int nMinPathSet = 0;
    double dCost = DBL_MAX;
    
    for(int i=0; i<m_nPathCount; i++)
    {
        if (m_pBitArray[i] & nPathSet)
        {
            // »õ·Î¿î°æ·Î´Â¸ñÀûÁönode¸¦Á¦¿ÜÇѳª¸ÓÁöµµ½Ãµé
            int nNewPathSet = nPathSet - m_pBitArray[i];
 
            // f(N,{N-1,N-2...1}) = cost[N][N-1] + f(N-1, {N-2,N-3...1})
            double dNewCost = m_pPathGraph[nFrom][i] + TSP_Process(i, nNewPathSet, nLen-1);
 
            if (dCost > dNewCost)
            {
                nMinPathSet = nNewPathSet ;
                dCost = dNewCost ;
            }
        }
    }
 
    // ÃÖ¼Òºñ¿ëÀ»ÀúÀå
    m_pDP[nFrom][nPathSet].dMinCost = dCost ;
    m_pDP[nFrom][nPathSet].nPathSet = nMinPathSet ;
 
    return dCost;
}
 
double CDynamicTSP::CalculateTSP()
{
    if (m_nPathCount<1) return -1.0;
 
    if (m_nSubSetCount<1) return -1.0;
 
    if (m_nPathCount<2) 
    {
        return (m_dTotalDistance=GetTotalDistance());
    }
 
    int nPathSet = 0;
    for(int i=0; i<m_nPathCount; i++)
    {
        nPathSet |= 1<<i ;
    }
 
    // start node
    if (m_nStartIndex==-1) m_nStartIndex = 0;
    int nNewPathSet = (nPathSet & ~m_pBitArray[m_nStartIndex]);
 
    // tsp process
    m_dTotalDistance = TSP_Process(m_nStartIndex, nNewPathSet, m_nPathCount-1);
 
    // get result
    int nIndex = 0;
    m_vecPathResult[nIndex++] = m_nStartIndex;
 
    int nNextPathSet = m_pDP[m_nStartIndex][nNewPathSet].nPathSet;
    int nNextNode = get_bit_index(nNewPathSet-nNextPathSet);
 
    do
    {
        m_vecPathResult[nIndex++] = nNextNode;
        nNewPathSet = nNextPathSet ;
        nNextPathSet = m_pDP[nNextNode][nNextPathSet].nPathSet;
 
    } while ((nNextNode=get_bit_index(nNewPathSet-nNextPathSet))!=-1);
 
    SortingPathResult();
 
    return (m_dTotalDistance=GetTotalDistance());
}