source: tspsg-svn/trunk/src/tspsolver.cpp @ 47

Last change on this file since 47 was 42, checked in by laleppa, 15 years ago

+ Finished solving algorithm (needs thorough testing).
+ Solution can be saved to HTML or OpenDocument? format.
+ Added VERSIONINFO resource for windows builds.

  • Updated translations to have unified terminology everywhere.

NB: This will be the first public alpha build.

  • Property svn:keywords set to Id URL
File size: 5.3 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.cpp 42 2009-07-31 18:23:07Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.cpp $
7 *
8 *  This file is part of TSPSG.
9 *
10 *  TSPSG is free software: you can redistribute it and/or modify
11 *  it under the terms of the GNU General Public License as published by
12 *  the Free Software Foundation, either version 3 of the License, or
13 *  (at your option) any later version.
14 *
15 *  TSPSG is distributed in the hope that it will be useful,
16 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 *  GNU General Public License for more details.
19 *
20 *  You should have received a copy of the GNU General Public License
21 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#include "tspsolver.h"
25#include "tspmodel.h"
26
27CTSPSolver::CTSPSolver()
28        : nCities(0)
29{
30}
31
32void CTSPSolver::cleanup()
33{
34        route.clear();
35}
36
37double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
38{
39double min = INFINITY;
40        for (int k = 0; k < nCities; k++)
41                if (((k != exc)) && (min > matrix[nRow][k]))
42                        min = matrix[nRow][k];
43        return min == INFINITY ? 0 : min;
44}
45
46double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
47{
48double min = INFINITY;
49        for (int k = 0; k < nCities; k++)
50                if ((k != exr) && (min > matrix[k][nCol]))
51                        min = matrix[k][nCol];
52        return min == INFINITY ? 0 : min;
53}
54
55void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
56{
57        for (int k = 0; k < nCities; k++)
58                if (k != nRow)
59                        matrix[nRow][k] -= val;
60}
61
62void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
63{
64        for (int k = 0; k < nCities; k++)
65                if (k != nCol)
66                        matrix[k][nCol] -= val;
67}
68
69double CTSPSolver::align(tMatrix &matrix)
70{
71double r = 0;
72double min;
73        for (int k = 0; k < nCities; k++) {
74                min = findMinInRow(k,matrix);
75                if (min > 0) {
76                        r += min;
77                        subRow(matrix,k,min);
78                }
79        }
80        for (int k = 0; k < nCities; k++) {
81                min = findMinInCol(k,matrix);
82                if (min > 0) {
83                        r += min;
84                        subCol(matrix,k,min);
85                }
86        }
87        return r;
88}
89
90bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
91{
92        h = -1;
93        nRow = -1;
94        nCol = -1;
95bool alts = false;
96double sum;
97        for (int r = 0; r < nCities; r++)
98                for (int c = 0; c < nCities; c++)
99                        if ((matrix[r][c] == 0) && !forbidden.values(r).contains(c)) {
100                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
101                                if (sum > h) {
102                                        h = sum;
103                                        nRow = r;
104                                        nCol = c;
105                                        alts = false;
106                                } else if (sum == h)
107                                        alts = true;
108                        }
109        return alts;
110}
111
112bool CTSPSolver::hasSubCycles(int nRow, int nCol)
113{
114        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
115                return false;
116int i = nCol;
117        while (true) {
118                if ((i = route[i]) == nRow)
119                        return true;
120                if (!route.contains(i))
121                        return false;
122        }
123        return false;
124}
125
126// TODO: Comment the algorithm
127sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
128{
129        if (numCities <= 1)
130                return NULL;
131        cleanup();
132        nCities = numCities;
133double s;
134QProgressDialog pd(parent);
135QProgressBar *pb = new QProgressBar(&pd);
136        pb->setAlignment(Qt::AlignCenter);
137        pb->setFormat(trUtf8("%v of %m parts found"));
138        pd.setBar(pb);
139        pd.setMaximum(nCities);
140        pd.setMinimumDuration(1000);
141        pd.setLabelText(trUtf8("Calculating optimal route..."));
142        pd.setWindowTitle(trUtf8("Solution Progress"));
143        pd.setWindowModality(Qt::ApplicationModal);
144        pd.setValue(0);
145
146sStep *step = new sStep();
147        step->matrix = task;
148
149        s = align(step->matrix);
150        step->price = s;
151        root = step;
152
153sStep *left, *right;
154int nRow, nCol;
155        while (route.size() < nCities) {
156                forbidden.clear();
157                step->alts = findCandidate(step->matrix,nRow,nCol,s);
158                while (hasSubCycles(nRow,nCol)) {
159                        forbidden[nRow] = nCol;
160                        step->matrix[nRow][nCol] = INFINITY;
161                        step->price += align(step->matrix);
162                        step->alts = findCandidate(step->matrix,nRow,nCol,s);
163                }
164                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
165                        root = NULL;
166                        break;
167                }
168
169                // Route with (nRow,nCol) path
170                right = new sStep();
171                right->matrix = step->matrix;
172                for (int k = 0; k < nCities; k++) {
173                        if (k != nCol)
174                                right->matrix[nRow][k] = INFINITY;
175                        if (k != nRow)
176                                right->matrix[k][nCol] = INFINITY;
177                }
178                right->price = step->price + align(right->matrix);
179                // Forbid selected route to exclude its reuse in next steps.
180                right->matrix[nCol][nRow] = INFINITY;
181                right->matrix[nRow][nCol] = INFINITY;
182
183                // Route without (nRow,nCol) path
184                left = new sStep();
185                left->matrix = step->matrix;
186                left->matrix[nRow][nCol] = INFINITY;
187                left->price = step->price + align(left->matrix);
188
189                step->candidate.nRow = nRow;
190                step->candidate.nCol = nCol;
191                step->plNode = left;
192                step->prNode = right;
193
194                if (right->price <= left->price) {
195                        // Route with (nRow,nCol) path is cheaper
196                        step = right;
197                        route[nRow] = nCol;
198                        pd.setValue(route.size());
199                } else {
200                        // Route without (nRow,nCol) path is cheaper
201                        step = left;
202                        qApp->processEvents();
203                }
204        }
205
206        pd.reset();
207        qApp->processEvents();
208
209        if (!root && !pd.wasCanceled()) {
210                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("This task has no solution."),QMessageBox::Ok,parent).exec();
211        }
212
213        return root;
214}
Note: See TracBrowser for help on using the repository browser.