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

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

+ Implemented File/Save? action.
+ Added "Save Solution" and "Back to Task" buttons to Solution tab for better usability.

  • Increased maximum number of cities to 20. Solving for 18-20 cities is already takes much time, so I thought it doesn't make sense to increase more.
  • Columns and rows are now resized to contents on all platforms.
  • Property svn:keywords set to Id URL
File size: 5.4 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 50 2009-08-03 15:15:46Z 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                        if (matrix[r][c] == 0) {
101                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
102                                if (sum > h) {
103                                        h = sum;
104                                        nRow = r;
105                                        nCol = c;
106                                        alts = false;
107                                } else if (sum == h)
108                                        alts = true;
109                        }
110        return alts;
111}
112
113bool CTSPSolver::hasSubCycles(int nRow, int nCol)
114{
115        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
116                return false;
117int i = nCol;
118        while (true) {
119                if ((i = route[i]) == nRow)
120                        return true;
121                if (!route.contains(i))
122                        return false;
123        }
124        return false;
125}
126
127// TODO: Comment the algorithm
128sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
129{
130        if (numCities <= 1)
131                return NULL;
132        cleanup();
133        nCities = numCities;
134double s;
135QProgressDialog pd(parent);
136QProgressBar *pb = new QProgressBar(&pd);
137        pb->setAlignment(Qt::AlignCenter);
138        pb->setFormat(trUtf8("%v of %m parts found"));
139        pd.setBar(pb);
140        pd.setMaximum(nCities);
141        pd.setMinimumDuration(1000);
142        pd.setLabelText(trUtf8("Calculating optimal route..."));
143        pd.setWindowTitle(trUtf8("Solution Progress"));
144        pd.setWindowModality(Qt::ApplicationModal);
145        pd.setValue(0);
146
147sStep *step = new sStep();
148        step->matrix = task;
149
150        s = align(step->matrix);
151        step->price = s;
152        root = step;
153
154sStep *left, *right;
155int nRow, nCol;
156        while (route.size() < nCities) {
157//              forbidden.clear();
158                step->alts = findCandidate(step->matrix,nRow,nCol,s);
159                while (hasSubCycles(nRow,nCol)) {
160//                      forbidden[nRow] = nCol;
161                        step->matrix[nRow][nCol] = INFINITY;
162                        step->price += align(step->matrix);
163                        step->alts = findCandidate(step->matrix,nRow,nCol,s);
164                }
165                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
166                        root = NULL;
167                        break;
168                }
169
170                // Route with (nRow,nCol) path
171                right = new sStep();
172                right->matrix = step->matrix;
173                for (int k = 0; k < nCities; k++) {
174                        if (k != nCol)
175                                right->matrix[nRow][k] = INFINITY;
176                        if (k != nRow)
177                                right->matrix[k][nCol] = INFINITY;
178                }
179                right->price = step->price + align(right->matrix);
180                // Forbid selected route to exclude its reuse in next steps.
181                right->matrix[nCol][nRow] = INFINITY;
182                right->matrix[nRow][nCol] = INFINITY;
183
184                // Route without (nRow,nCol) path
185                left = new sStep();
186                left->matrix = step->matrix;
187                left->matrix[nRow][nCol] = INFINITY;
188                left->price = step->price + align(left->matrix);
189
190                step->candidate.nRow = nRow;
191                step->candidate.nCol = nCol;
192                step->plNode = left;
193                step->prNode = right;
194
195                if (right->price <= left->price) {
196                        // Route with (nRow,nCol) path is cheaper
197                        step = right;
198                        route[nRow] = nCol;
199                        pd.setValue(route.size());
200                } else {
201                        // Route without (nRow,nCol) path is cheaper
202                        step = left;
203                        qApp->processEvents();
204                }
205        }
206
207        if (!root && !pd.wasCanceled()) {
208                pd.reset();
209                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
210        }
211
212        qApp->processEvents();
213
214        return root;
215}
Note: See TracBrowser for help on using the repository browser.