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

Last change on this file since 99 was 99, checked in by laleppa, 15 years ago
  • Fixed a bug when a solution couldn't be found for some tasks while the task had at least one solution (mostly, tasks with a lot of restrictions).
  • Fixed a bug when Save As dialog always appeared (even for non-Untitled files) when selecting Save in Unsaved Changes dialog.
  • Improved the solution algorithm.
  • Moved progress dialog from CTSPSolver to MainWindow?. CTSPSolver doesn't contain any GUI related code now.

+ Added routePartFound() signal to CTSPSolver which is emitted once every time a part of the route is found.
+ Added cancel() slot and wasCanceled() public function to CTSPSolver to be able to cancel a solution process and to know whether it was canceled.
+ Progress is now shown when generating a solution output.
+ Check for updates functionality (only in Windows version at this moment).

  • Property svn:keywords set to Id URL
File size: 10.5 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 99 2010-03-22 20:45:16Z 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
[99]26//! \internal \brief A short for maximum double, used internally in the solution algorithm.
27#define MAX_DOUBLE std::numeric_limits<double>::max()
28
29/*!
30 * \brief Returns CTSPSolver's version ID.
31 * \return A string: <b>\$Id: tspsolver.cpp 99 2010-03-22 20:45:16Z laleppa $</b>.
32 */
33QString CTSPSolver::getVersionId()
[13]34{
[99]35        return QString("$Id: tspsolver.cpp 99 2010-03-22 20:45:16Z laleppa $");
[13]36}
[12]37
[67]38/*!
[99]39 * \brief Constructs CTSPSolver object.
40 * \param parent A parent object.
41 */
42CTSPSolver::CTSPSolver(QObject *parent)
43        : QObject(parent), nCities(0), root(NULL) {}
44
45/*!
46 * \brief Cleans up the object and frees up memory used by the solution tree.
47 * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
48 * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
49 * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
50 *
51 * \sa solve()
52 */
53void CTSPSolver::cleanup(bool processEvents)
54{
55        if (!processEvents)
56                QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
57        route.clear();
58        mayNotBeOptimal = false;
59        if (root != NULL)
60                deleteTree(root, processEvents);
61        if (!processEvents)
62                QApplication::restoreOverrideCursor();
63}
64
65/*!
[67]66 * \brief Returns the sorted optimal path, starting from City 1.
67 * \return A string, containing sorted optimal path.
68 */
69QString CTSPSolver::getSortedPath() const
[13]70{
[67]71        if (!root || route.isEmpty() || (route.size() != nCities))
72                return QString();
[42]73
[67]74int i = 0; // We start from City 1
[87]75QString path = tr("City %1").arg(1) + " -> ";
[67]76        while ((i = route[i]) != 0) {
[87]77                path += tr("City %1").arg(i + 1) + " -> ";
[67]78        }
79        // And finish in City 1, too
[87]80        path += tr("City %1").arg(1);
[12]81
[67]82        return path;
[12]83}
84
[67]85/*!
[99]86 * \brief Indicates whether or not the solution is definitely optimal.
87 * \return \c true if the solution is definitely optimal, otherwise \c false.
[67]88 *
[99]89 *  The solution may need some further iterations to determine whether or not it is optimal.
[67]90 *  In such cases this function returns \c false.
91 */
92bool CTSPSolver::isOptimal() const
[42]93{
[67]94        return !mayNotBeOptimal;
[42]95}
96
[65]97/*!
98 * \brief Solves the given task.
99 * \param numCities Number of cities in the task.
100 * \param task The matrix of city-to-city travel costs.
[66]101 * \return Pointer to the root of the solution tree.
[65]102 *
103 * \todo TODO: Comment the algorithm.
104 */
[99]105SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
[42]106{
[12]107        if (numCities <= 1)
108                return NULL;
[99]109
110QMutexLocker locker(&mutex);
[42]111        cleanup();
[99]112        canceled = false;
113        locker.unlock();
114
[13]115        nCities = numCities;
[42]116
[74]117SStep *step = new SStep();
[13]118        step->matrix = task;
[99]119        // We need to distinguish the values forbidden by the user
120        // from the values forbidden by the algorithm.
121        // So we replace user's infinities by the maximum available double value.
122        normalize(step->matrix);
123#ifdef DEBUG
124        qDebug() << step->matrix;
125#endif // DEBUG
[60]126        step->price = align(step->matrix);
[13]127        root = step;
[12]128
[74]129SStep *left, *right;
[42]130int nRow, nCol;
[60]131bool firstStep = true;
[93]132double check = INFINITY;
[60]133        while (this->route.size() < nCities) {
134                step->alts = findCandidate(step->matrix,nRow,nCol);
[99]135
[42]136                while (hasSubCycles(nRow,nCol)) {
[99]137#ifdef DEBUG
138                        qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
139#endif // DEBUG
[42]140                        step->matrix[nRow][nCol] = INFINITY;
141                        step->price += align(step->matrix);
[60]142                        step->alts = findCandidate(step->matrix,nRow,nCol);
[42]143                }
[99]144
145#ifdef DEBUG
146                qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
147                qDebug() << "Alternate:" << step->alts;
148                qDebug() << "Step price:" << step->price << endl;
149#endif // DEBUG
150
151                locker.relock();
152                if ((nRow == -1) || (nCol == -1) || canceled) {
[74]153                        cleanup();
[99]154                        return NULL;
[42]155                }
[99]156                locker.unlock();
[42]157
158                // Route with (nRow,nCol) path
[74]159                right = new SStep();
[90]160                right->pNode = step;
[42]161                right->matrix = step->matrix;
162                for (int k = 0; k < nCities; k++) {
163                        if (k != nCol)
164                                right->matrix[nRow][k] = INFINITY;
165                        if (k != nRow)
166                                right->matrix[k][nCol] = INFINITY;
167                }
168                right->price = step->price + align(right->matrix);
[99]169                // Forbid the selected route to exclude its reuse in next steps.
[42]170                right->matrix[nCol][nRow] = INFINITY;
171                right->matrix[nRow][nCol] = INFINITY;
172
173                // Route without (nRow,nCol) path
[74]174                left = new SStep();
[90]175                left->pNode = step;
[42]176                left->matrix = step->matrix;
177                left->matrix[nRow][nCol] = INFINITY;
[93]178                left->price = step->price + align(left->matrix);
[42]179
180                step->candidate.nRow = nRow;
181                step->candidate.nCol = nCol;
182                step->plNode = left;
183                step->prNode = right;
184
[99]185                // This matrix is not used anymore. Restoring infinities back.
186                denormalize(step->matrix);
187
[42]188                if (right->price <= left->price) {
189                        // Route with (nRow,nCol) path is cheaper
190                        step = right;
[60]191                        this->route[nRow] = nCol;
[99]192                        emit routePartFound(this->route.size());
[60]193                        if (firstStep) {
194                                check = left->price;
195                                firstStep = false;
196                        }
[42]197                } else {
198                        // Route without (nRow,nCol) path is cheaper
199                        step = left;
200                        qApp->processEvents();
[60]201                        if (firstStep) {
202                                check = right->price;
203                                firstStep = false;
204                        }
[42]205                }
206        }
207
[99]208        route = this->route;
209        mayNotBeOptimal = (check < step->price);
[42]210
211        return root;
[12]212}
[60]213
[99]214/*!
215 * \brief Indicates whether or not the solution process was canceled.
216 * \return \c true if the solution process was canceled, otherwise \c false.
217 */
218bool CTSPSolver::wasCanceled() const
219{
220QMutexLocker locker(&mutex);
221        return canceled;
222}
223
224/*!
225 * \brief Cancels the solution process.
226 */
227void CTSPSolver::cancel()
228{
229QMutexLocker locker(&mutex);
230        canceled = true;
231}
232
[74]233CTSPSolver::~CTSPSolver()
234{
235        if (root != NULL)
[90]236                deleteTree(root);
[74]237}
238
[67]239/* Privates **********************************************************/
240
[89]241double CTSPSolver::align(TMatrix &matrix)
[60]242{
[89]243double r = 0;
244double min;
[67]245        for (int k = 0; k < nCities; k++) {
246                min = findMinInRow(k,matrix);
247                if (min > 0) {
248                        r += min;
[99]249                        if (min < MAX_DOUBLE)
250                                subRow(matrix,k,min);
[67]251                }
[60]252        }
[67]253        for (int k = 0; k < nCities; k++) {
254                min = findMinInCol(k,matrix);
255                if (min > 0) {
256                        r += min;
[99]257                        if (min < MAX_DOUBLE)
258                                subCol(matrix,k,min);
[67]259                }
260        }
261        return r;
262}
[60]263
[99]264void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
[67]265{
[90]266        if (root == NULL)
267                return;
268SStep *step = root;
269SStep *parent;
270        forever {
[99]271                if (processEvents)
272                        QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
[90]273                if (step->plNode != NULL) {
274                        // We have left child node - going inside it
275                        step = step->plNode;
276                        step->pNode->plNode = NULL;
277                        continue;
278                } else if (step->prNode != NULL) {
279                        // We have right child node - going inside it
280                        step = step->prNode;
281                        step->pNode->prNode = NULL;
282                        continue;
283                } else {
284                        // We have no child nodes. Deleting current one.
285                        parent = step->pNode;
286                        delete step;
287                        if (parent != NULL) {
288                                // Going back to the parent node.
289                                step = parent;
290                        } else {
291                                // We came back to the root node. Finishing.
292                                root = NULL;
293                                break;
294                        }
295                }
296        }
[74]297}
298
[99]299void CTSPSolver::denormalize(TMatrix &matrix) const
300{
301        for (int r = 0; r < nCities; r++)
302                for (int c = 0; c < nCities; c++)
303                        if ((r != c) && (matrix.at(r).at(c) == MAX_DOUBLE))
304                                matrix[r][c] = INFINITY;
305}
306
[76]307QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
[74]308{
[67]309        nRow = -1;
310        nCol = -1;
[76]311QList<SCandidate> alts;
312SCandidate cand;
[89]313double h = -1;
314double sum;
[67]315        for (int r = 0; r < nCities; r++)
316                for (int c = 0; c < nCities; c++)
317//                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
318                        if (matrix.at(r).at(c) == 0) {
319                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
320                                if (sum > h) {
321                                        h = sum;
322                                        nRow = r;
323                                        nCol = c;
[74]324                                        alts.clear();
325                                } else if ((sum == h) && !hasSubCycles(r,c)) {
326                                        cand.nRow = r;
327                                        cand.nCol = c;
328                                        alts.append(cand);
329                                }
[67]330                        }
331        return alts;
[63]332}
333
[89]334double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
[60]335{
[89]336double min = INFINITY;
[67]337        for (int k = 0; k < nCities; k++)
338                if ((k != exr) && (min > matrix.at(k).at(nCol)))
339                        min = matrix.at(k).at(nCol);
[99]340        return (min == INFINITY) ? 0 : min;
[60]341}
[67]342
[89]343double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
[67]344{
[89]345double min = INFINITY;
[99]346        for (int k = 0; k < nCities; k++) {
[67]347                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
348                        min = matrix.at(nRow).at(k);
[99]349        }
350        return (min == INFINITY) ? 0 : min;
[67]351}
352
[71]353bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
[67]354{
355        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
356                return false;
357int i = nCol;
358        while (true) {
359                if ((i = route[i]) == nRow)
360                        return true;
361                if (!route.contains(i))
362                        return false;
363        }
364        return false;
365}
366
[99]367void CTSPSolver::normalize(TMatrix &matrix) const
368{
369        for (int r = 0; r < nCities; r++)
370                for (int c = 0; c < nCities; c++)
371                        if ((r != c) && (matrix.at(r).at(c) == INFINITY))
372                                matrix[r][c] = MAX_DOUBLE;
373}
374
[89]375void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
[67]376{
377        for (int k = 0; k < nCities; k++)
378                if (k != nCol)
379                        matrix[k][nCol] -= val;
380}
381
[89]382void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
[67]383{
384        for (int k = 0; k < nCities; k++)
385                if (k != nRow)
386                        matrix[nRow][k] -= val;
387}
[98]388
[99]389#ifdef DEBUG
[98]390QDebug operator<<(QDebug dbg, const TMatrix &matrix)
391{
392        for (int r = 0; r < matrix.count(); r++) {
393                for (int c = 0; c < matrix.at(r).count(); c++)
[99]394                        dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
[98]395                dbg << endl;
396        }
397        return dbg;
398}
[99]399
400QDebug operator<<(QDebug dbg, const SCandidate &cand)
401{
402        dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
403        return dbg;
404}
405#endif // DEBUG
Note: See TracBrowser for help on using the repository browser.