source: tspsg/src/tspsolver.cpp @ c10297cf73

0.1.3.145-beta1-symbian0.1.4.170-beta2-bb10appveyorimgbotreadme
Last change on this file since c10297cf73 was c10297cf73, checked in by Oleksii Serdiuk, 15 years ago
  • mainwindow.ui and mainwindow.ce.ui had differences only in printing actions and statusbar, so I merged them into one. Differences are now applied in source code. This will simplify Main Window maintenance.
  • Changed #ifndef Q_OS_WINCE to #ifndef QT_NO_PRINTER where relevant.
  • Now using method at() instead of operator [] in solving algorithm. This change dramatically decreased solution time (from 13 seconds to 10-40 milliseconds for 20 cities on my PC).
  • Increased maximum number of cities to 30. Setting more makes no sense at this moment, because generated solution output is big and inserting it to QTextEdit takes veeeeery long time.
  • Translations were updated.
  • Property mode set to 100644
File size: 5.4 KB
RevLine 
[67e53c96d7]1/*
[430bd7f7e9]2 *  TSPSG: TSP Solver and Generator
[5354a01311]3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
[67e53c96d7]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"
[2bc8e278b7]25#include "tspmodel.h"
[67e53c96d7]26
[e664262f7d]27CTSPSolver::CTSPSolver()
[430bd7f7e9]28        : nCities(0)
[e664262f7d]29{
30}
[67e53c96d7]31
[430bd7f7e9]32void CTSPSolver::cleanup()
33{
34        route.clear();
35}
36
37double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
[e664262f7d]38{
[2bc8e278b7]39double min = INFINITY;
[e664262f7d]40        for (int k = 0; k < nCities; k++)
[c10297cf73]41                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
42                        min = matrix.at(nRow).at(k);
[2bc8e278b7]43        return min == INFINITY ? 0 : min;
[e664262f7d]44}
[67e53c96d7]45
[430bd7f7e9]46double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
[67e53c96d7]47{
[2bc8e278b7]48double min = INFINITY;
[e664262f7d]49        for (int k = 0; k < nCities; k++)
[c10297cf73]50                if ((k != exr) && (min > matrix.at(k).at(nCol)))
51                        min = matrix.at(k).at(nCol);
[2bc8e278b7]52        return min == INFINITY ? 0 : min;
[67e53c96d7]53}
54
[430bd7f7e9]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++)
[aaf2113307]99//                      if ((matrix[r][c] == 0) && !forbidden.values(r).contains(c)) {
[c10297cf73]100                        if (matrix.at(r).at(c) == 0) {
[430bd7f7e9]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)
[67e53c96d7]129{
130        if (numCities <= 1)
131                return NULL;
[430bd7f7e9]132        cleanup();
[e664262f7d]133        nCities = numCities;
[430bd7f7e9]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
[e664262f7d]147sStep *step = new sStep();
148        step->matrix = task;
[430bd7f7e9]149
150        s = align(step->matrix);
151        step->price = s;
[e664262f7d]152        root = step;
[67e53c96d7]153
[430bd7f7e9]154sStep *left, *right;
155int nRow, nCol;
156        while (route.size() < nCities) {
[aaf2113307]157//              forbidden.clear();
[430bd7f7e9]158                step->alts = findCandidate(step->matrix,nRow,nCol,s);
159                while (hasSubCycles(nRow,nCol)) {
[aaf2113307]160//                      forbidden[nRow] = nCol;
[430bd7f7e9]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()) {
[aaf2113307]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();
[430bd7f7e9]210        }
211
[aaf2113307]212        qApp->processEvents();
213
[430bd7f7e9]214        return root;
[67e53c96d7]215}
Note: See TracBrowser for help on using the repository browser.