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

Last change on this file since 136 was 124, checked in by laleppa, 14 years ago

+ Added support for Windows 7 Taskbar Extensions (namely, Progress Bars).

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