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

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

+ Preliminary Symbian support.

  • Property svn:keywords set to Id URL
File size: 8.2 KB
RevLine 
[12]1/*
[42]2 *  TSPSG: TSP Solver and Generator
[87]3 *  Copyright (C) 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
[12]4 *
5 *  $Id: tspsolver.cpp 93 2010-02-23 22:17:48Z 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
[65]26//! Class constructor
[13]27CTSPSolver::CTSPSolver()
[74]28        : nCities(0), root(NULL)
[13]29{
30}
[12]31
[67]32/*!
33 * \brief Returns the sorted optimal path, starting from City 1.
34 * \return A string, containing sorted optimal path.
35 */
36QString CTSPSolver::getSortedPath() const
[13]37{
[67]38        if (!root || route.isEmpty() || (route.size() != nCities))
39                return QString();
[42]40
[67]41int i = 0; // We start from City 1
[87]42QString path = tr("City %1").arg(1) + " -> ";
[67]43        while ((i = route[i]) != 0) {
[87]44                path += tr("City %1").arg(i + 1) + " -> ";
[67]45        }
46        // And finish in City 1, too
[87]47        path += tr("City %1").arg(1);
[12]48
[67]49        return path;
[12]50}
51
[67]52/*!
53 * \brief Returns CTSPSolver's version ID.
54 * \return A string: <b>\$Id: tspsolver.cpp 93 2010-02-23 22:17:48Z laleppa $</b>.
55 */
56QString CTSPSolver::getVersionId()
[12]57{
[67]58        return QString("$Id: tspsolver.cpp 93 2010-02-23 22:17:48Z laleppa $");
[42]59}
60
[67]61/*!
62 * \brief Returns whether or not the solution is definitely optimal.
63 * \return \c true if solution is definitely optimal, otherwise \c false.
64 *
65 *  The solution may need some further interations to determine whether it is optimal.
66 *  In such cases this function returns \c false.
67 */
68bool CTSPSolver::isOptimal() const
[42]69{
[67]70        return !mayNotBeOptimal;
[42]71}
72
[65]73/*!
74 * \brief Solves the given task.
75 * \param numCities Number of cities in the task.
76 * \param task The matrix of city-to-city travel costs.
77 * \param parent The parent widget for displaying messages and dialogs.
[66]78 * \return Pointer to the root of the solution tree.
[65]79 *
80 * \todo TODO: Comment the algorithm.
81 */
[74]82SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
[42]83{
[12]84        if (numCities <= 1)
85                return NULL;
[42]86        cleanup();
[13]87        nCities = numCities;
[42]88QProgressDialog pd(parent);
89QProgressBar *pb = new QProgressBar(&pd);
90        pb->setAlignment(Qt::AlignCenter);
[87]91        pb->setFormat(tr("%v of %m parts found"));
[42]92        pd.setBar(pb);
93        pd.setMaximum(nCities);
94        pd.setMinimumDuration(1000);
[87]95        pd.setLabelText(tr("Calculating optimal route..."));
96        pd.setWindowTitle(tr("Solution Progress"));
[42]97        pd.setWindowModality(Qt::ApplicationModal);
98        pd.setValue(0);
99
[74]100SStep *step = new SStep();
[13]101        step->matrix = task;
[60]102        step->price = align(step->matrix);
[13]103        root = step;
[12]104
[74]105SStep *left, *right;
[42]106int nRow, nCol;
[60]107bool firstStep = true;
[93]108double check = INFINITY;
[60]109        while (this->route.size() < nCities) {
[50]110//              forbidden.clear();
[60]111                step->alts = findCandidate(step->matrix,nRow,nCol);
[42]112                while (hasSubCycles(nRow,nCol)) {
[50]113//                      forbidden[nRow] = nCol;
[42]114                        step->matrix[nRow][nCol] = INFINITY;
115                        step->price += align(step->matrix);
[60]116                        step->alts = findCandidate(step->matrix,nRow,nCol);
[42]117                }
118                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
[74]119                        cleanup();
[42]120                        break;
121                }
122
123                // Route with (nRow,nCol) path
[74]124                right = new SStep();
[90]125                right->pNode = step;
[42]126                right->matrix = step->matrix;
127                for (int k = 0; k < nCities; k++) {
128                        if (k != nCol)
129                                right->matrix[nRow][k] = INFINITY;
130                        if (k != nRow)
131                                right->matrix[k][nCol] = INFINITY;
132                }
133                right->price = step->price + align(right->matrix);
134                // Forbid selected route to exclude its reuse in next steps.
135                right->matrix[nCol][nRow] = INFINITY;
136                right->matrix[nRow][nCol] = INFINITY;
137
138                // Route without (nRow,nCol) path
[74]139                left = new SStep();
[90]140                left->pNode = step;
[42]141                left->matrix = step->matrix;
142                left->matrix[nRow][nCol] = INFINITY;
[93]143                left->price = step->price + align(left->matrix);
[42]144
145                step->candidate.nRow = nRow;
146                step->candidate.nCol = nCol;
147                step->plNode = left;
148                step->prNode = right;
149
150                if (right->price <= left->price) {
151                        // Route with (nRow,nCol) path is cheaper
152                        step = right;
[60]153                        this->route[nRow] = nCol;
154                        pd.setValue(this->route.size());
155                        if (firstStep) {
156                                check = left->price;
157                                firstStep = false;
158                        }
[42]159                } else {
160                        // Route without (nRow,nCol) path is cheaper
161                        step = left;
162                        qApp->processEvents();
[60]163                        if (firstStep) {
164                                check = right->price;
165                                firstStep = false;
166                        }
[42]167                }
168        }
169
170        if (!root && !pd.wasCanceled()) {
[50]171                pd.reset();
[87]172                QMessageBox(QMessageBox::Warning,tr("Solution Result"),tr("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
[42]173        }
174
[50]175        qApp->processEvents();
176
[60]177        if (root) {
178                route = this->route;
179                mayNotBeOptimal = (check < step->price);
180        }
[42]181        return root;
[12]182}
[60]183
[74]184CTSPSolver::~CTSPSolver()
185{
186        if (root != NULL)
[90]187                deleteTree(root);
[74]188}
189
[67]190/* Privates **********************************************************/
191
[89]192double CTSPSolver::align(TMatrix &matrix)
[60]193{
[89]194double r = 0;
195double min;
[67]196        for (int k = 0; k < nCities; k++) {
197                min = findMinInRow(k,matrix);
198                if (min > 0) {
199                        r += min;
200                        subRow(matrix,k,min);
201                }
[60]202        }
[67]203        for (int k = 0; k < nCities; k++) {
204                min = findMinInCol(k,matrix);
205                if (min > 0) {
206                        r += min;
207                        subCol(matrix,k,min);
208                }
209        }
210        return r;
211}
[60]212
[67]213void CTSPSolver::cleanup()
214{
[78]215        QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
[67]216        route.clear();
217        mayNotBeOptimal = false;
[74]218        if (root != NULL)
[90]219                deleteTree(root);
[78]220        QApplication::restoreOverrideCursor();
[60]221}
222
[90]223void CTSPSolver::deleteTree(SStep *&root)
[63]224{
[90]225        if (root == NULL)
226                return;
227SStep *step = root;
228SStep *parent;
229        forever {
230                if (step->plNode != NULL) {
231                        // We have left child node - going inside it
232                        step = step->plNode;
233                        step->pNode->plNode = NULL;
234                        continue;
235                } else if (step->prNode != NULL) {
236                        // We have right child node - going inside it
237                        step = step->prNode;
238                        step->pNode->prNode = NULL;
239                        continue;
240                } else {
241                        // We have no child nodes. Deleting current one.
242                        parent = step->pNode;
243                        delete step;
244                        if (parent != NULL) {
245                                // Going back to the parent node.
246                                step = parent;
247                        } else {
248                                // We came back to the root node. Finishing.
249                                root = NULL;
250                                break;
251                        }
252                }
253        }
[74]254}
255
[76]256QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
[74]257{
[67]258        nRow = -1;
259        nCol = -1;
[76]260QList<SCandidate> alts;
261SCandidate cand;
[89]262double h = -1;
263double sum;
[67]264        for (int r = 0; r < nCities; r++)
265                for (int c = 0; c < nCities; c++)
266//                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
267                        if (matrix.at(r).at(c) == 0) {
268                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
269                                if (sum > h) {
270                                        h = sum;
271                                        nRow = r;
272                                        nCol = c;
[74]273                                        alts.clear();
274                                } else if ((sum == h) && !hasSubCycles(r,c)) {
275                                        cand.nRow = r;
276                                        cand.nCol = c;
277                                        alts.append(cand);
278                                }
[67]279                        }
280        return alts;
[63]281}
282
[89]283double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
[60]284{
[89]285double min = INFINITY;
[67]286        for (int k = 0; k < nCities; k++)
287                if ((k != exr) && (min > matrix.at(k).at(nCol)))
288                        min = matrix.at(k).at(nCol);
289        return min == INFINITY ? 0 : min;
[60]290}
[67]291
[89]292double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
[67]293{
[89]294double min = INFINITY;
[67]295        for (int k = 0; k < nCities; k++)
296                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
297                        min = matrix.at(nRow).at(k);
298        return min == INFINITY ? 0 : min;
299}
300
[71]301bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
[67]302{
303        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
304                return false;
305int i = nCol;
306        while (true) {
307                if ((i = route[i]) == nRow)
308                        return true;
309                if (!route.contains(i))
310                        return false;
311        }
312        return false;
313}
314
[89]315void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
[67]316{
317        for (int k = 0; k < nCities; k++)
318                if (k != nCol)
319                        matrix[k][nCol] -= val;
320}
321
[89]322void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
[67]323{
324        for (int k = 0; k < nCities; k++)
325                if (k != nRow)
326                        matrix[nRow][k] -= val;
327}
Note: See TracBrowser for help on using the repository browser.