source: tspsg/src/tspsolver.cpp @ bc691eca15

0.1.3.145-beta1-symbian0.1.4.170-beta2-bb10appveyorimgbotreadme
Last change on this file since bc691eca15 was 9cf98b9bd6, checked in by Oleksii Serdiuk, 15 years ago

+ Warning about possible non-optimal result.

  • Resulting path is now sorted, always starts from City 1 and has "City 1 -> City n -> ... -> City 1" format.
  • Translations updated.
  • Property mode set to 100644
File size: 6.2 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id$
6 *  $URL$
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        mayNotBeOptimal = false;
36}
37
38double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
39{
40double min = INFINITY;
41        for (int k = 0; k < nCities; k++)
42                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
43                        min = matrix.at(nRow).at(k);
44        return min == INFINITY ? 0 : min;
45}
46
47double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
48{
49double min = INFINITY;
50        for (int k = 0; k < nCities; k++)
51                if ((k != exr) && (min > matrix.at(k).at(nCol)))
52                        min = matrix.at(k).at(nCol);
53        return min == INFINITY ? 0 : min;
54}
55
56void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
57{
58        for (int k = 0; k < nCities; k++)
59                if (k != nRow)
60                        matrix[nRow][k] -= val;
61}
62
63void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
64{
65        for (int k = 0; k < nCities; k++)
66                if (k != nCol)
67                        matrix[k][nCol] -= val;
68}
69
70double CTSPSolver::align(tMatrix &matrix)
71{
72double r = 0;
73double min;
74        for (int k = 0; k < nCities; k++) {
75                min = findMinInRow(k,matrix);
76                if (min > 0) {
77                        r += min;
78                        subRow(matrix,k,min);
79                }
80        }
81        for (int k = 0; k < nCities; k++) {
82                min = findMinInCol(k,matrix);
83                if (min > 0) {
84                        r += min;
85                        subCol(matrix,k,min);
86                }
87        }
88        return r;
89}
90
91bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol)
92{
93        nRow = -1;
94        nCol = -1;
95bool alts = false;
96double h = -1;
97double sum;
98        for (int r = 0; r < nCities; r++)
99                for (int c = 0; c < nCities; c++)
100//                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
101                        if (matrix.at(r).at(c) == 0) {
102                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
103                                if (sum > h) {
104                                        h = sum;
105                                        nRow = r;
106                                        nCol = c;
107                                        alts = false;
108                                } else if ((sum == h) && !hasSubCycles(r,c))
109                                        alts = true;
110                        }
111        return alts;
112}
113
114bool CTSPSolver::hasSubCycles(int nRow, int nCol)
115{
116        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
117                return false;
118int i = nCol;
119        while (true) {
120                if ((i = route[i]) == nRow)
121                        return true;
122                if (!route.contains(i))
123                        return false;
124        }
125        return false;
126}
127
128// TODO: Comment the algorithm
129sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
130{
131        if (numCities <= 1)
132                return NULL;
133        cleanup();
134        nCities = numCities;
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        step->price = align(step->matrix);
150        root = step;
151
152sStep *left, *right;
153int nRow, nCol;
154bool firstStep = true;
155double check;
156        while (this->route.size() < nCities) {
157//              forbidden.clear();
158                step->alts = findCandidate(step->matrix,nRow,nCol);
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);
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                        this->route[nRow] = nCol;
199                        pd.setValue(this->route.size());
200                        if (firstStep) {
201                                check = left->price;
202                                firstStep = false;
203                        }
204                } else {
205                        // Route without (nRow,nCol) path is cheaper
206                        step = left;
207                        qApp->processEvents();
208                        if (firstStep) {
209                                check = right->price;
210                                firstStep = false;
211                        }
212                }
213        }
214
215        if (!root && !pd.wasCanceled()) {
216                pd.reset();
217                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
218        }
219
220        qApp->processEvents();
221
222        if (root) {
223                route = this->route;
224                mayNotBeOptimal = (check < step->price);
225        }
226        return root;
227}
228
229QString CTSPSolver::getSortedPath() const
230{
231        if (!root || route.isEmpty() || (route.size() != nCities))
232                return QString();
233
234int i = 0; // We start from City 1
235QString path = trUtf8("City %1").arg(1) + " -> ";
236        while ((i = route[i]) != 0) {
237                path += trUtf8("City %1").arg(i + 1) + " -> ";
238        }
239        // And finish in City 1, too
240        path += trUtf8("City %1").arg(1);
241
242        return path;
243}
244
245bool CTSPSolver::isOptimal() const
246{
247        return !mayNotBeOptimal;
248}
Note: See TracBrowser for help on using the repository browser.