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
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 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
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()
34{
35        return QString("$Id: tspsolver.cpp 99 2010-03-22 20:45:16Z laleppa $");
36}
37
38/*!
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/*!
66 * \brief Returns the sorted optimal path, starting from City 1.
67 * \return A string, containing sorted optimal path.
68 */
69QString CTSPSolver::getSortedPath() const
70{
71        if (!root || route.isEmpty() || (route.size() != nCities))
72                return QString();
73
74int i = 0; // We start from City 1
75QString path = tr("City %1").arg(1) + " -> ";
76        while ((i = route[i]) != 0) {
77                path += tr("City %1").arg(i + 1) + " -> ";
78        }
79        // And finish in City 1, too
80        path += tr("City %1").arg(1);
81
82        return path;
83}
84
85/*!
86 * \brief Indicates whether or not the solution is definitely optimal.
87 * \return \c true if the solution is definitely optimal, otherwise \c false.
88 *
89 *  The solution may need some further iterations to determine whether or not it is optimal.
90 *  In such cases this function returns \c false.
91 */
92bool CTSPSolver::isOptimal() const
93{
94        return !mayNotBeOptimal;
95}
96
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.
101 * \return Pointer to the root of the solution tree.
102 *
103 * \todo TODO: Comment the algorithm.
104 */
105SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
106{
107        if (numCities <= 1)
108                return NULL;
109
110QMutexLocker locker(&mutex);
111        cleanup();
112        canceled = false;
113        locker.unlock();
114
115        nCities = numCities;
116
117SStep *step = new SStep();
118        step->matrix = task;
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
126        step->price = align(step->matrix);
127        root = step;
128
129SStep *left, *right;
130int nRow, nCol;
131bool firstStep = true;
132double check = INFINITY;
133        while (this->route.size() < nCities) {
134                step->alts = findCandidate(step->matrix,nRow,nCol);
135
136                while (hasSubCycles(nRow,nCol)) {
137#ifdef DEBUG
138                        qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
139#endif // DEBUG
140                        step->matrix[nRow][nCol] = INFINITY;
141                        step->price += align(step->matrix);
142                        step->alts = findCandidate(step->matrix,nRow,nCol);
143                }
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) {
153                        cleanup();
154                        return NULL;
155                }
156                locker.unlock();
157
158                // Route with (nRow,nCol) path
159                right = new SStep();
160                right->pNode = step;
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);
169                // Forbid the selected route to exclude its reuse in next steps.
170                right->matrix[nCol][nRow] = INFINITY;
171                right->matrix[nRow][nCol] = INFINITY;
172
173                // Route without (nRow,nCol) path
174                left = new SStep();
175                left->pNode = step;
176                left->matrix = step->matrix;
177                left->matrix[nRow][nCol] = INFINITY;
178                left->price = step->price + align(left->matrix);
179
180                step->candidate.nRow = nRow;
181                step->candidate.nCol = nCol;
182                step->plNode = left;
183                step->prNode = right;
184
185                // This matrix is not used anymore. Restoring infinities back.
186                denormalize(step->matrix);
187
188                if (right->price <= left->price) {
189                        // Route with (nRow,nCol) path is cheaper
190                        step = right;
191                        this->route[nRow] = nCol;
192                        emit routePartFound(this->route.size());
193                        if (firstStep) {
194                                check = left->price;
195                                firstStep = false;
196                        }
197                } else {
198                        // Route without (nRow,nCol) path is cheaper
199                        step = left;
200                        qApp->processEvents();
201                        if (firstStep) {
202                                check = right->price;
203                                firstStep = false;
204                        }
205                }
206        }
207
208        route = this->route;
209        mayNotBeOptimal = (check < step->price);
210
211        return root;
212}
213
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
233CTSPSolver::~CTSPSolver()
234{
235        if (root != NULL)
236                deleteTree(root);
237}
238
239/* Privates **********************************************************/
240
241double CTSPSolver::align(TMatrix &matrix)
242{
243double r = 0;
244double min;
245        for (int k = 0; k < nCities; k++) {
246                min = findMinInRow(k,matrix);
247                if (min > 0) {
248                        r += min;
249                        if (min < MAX_DOUBLE)
250                                subRow(matrix,k,min);
251                }
252        }
253        for (int k = 0; k < nCities; k++) {
254                min = findMinInCol(k,matrix);
255                if (min > 0) {
256                        r += min;
257                        if (min < MAX_DOUBLE)
258                                subCol(matrix,k,min);
259                }
260        }
261        return r;
262}
263
264void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
265{
266        if (root == NULL)
267                return;
268SStep *step = root;
269SStep *parent;
270        forever {
271                if (processEvents)
272                        QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
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        }
297}
298
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
307QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
308{
309        nRow = -1;
310        nCol = -1;
311QList<SCandidate> alts;
312SCandidate cand;
313double h = -1;
314double sum;
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;
324                                        alts.clear();
325                                } else if ((sum == h) && !hasSubCycles(r,c)) {
326                                        cand.nRow = r;
327                                        cand.nCol = c;
328                                        alts.append(cand);
329                                }
330                        }
331        return alts;
332}
333
334double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
335{
336double min = INFINITY;
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);
340        return (min == INFINITY) ? 0 : min;
341}
342
343double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
344{
345double min = INFINITY;
346        for (int k = 0; k < nCities; k++) {
347                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
348                        min = matrix.at(nRow).at(k);
349        }
350        return (min == INFINITY) ? 0 : min;
351}
352
353bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
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
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
375void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
376{
377        for (int k = 0; k < nCities; k++)
378                if (k != nCol)
379                        matrix[k][nCol] -= val;
380}
381
382void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
383{
384        for (int k = 0; k < nCities; k++)
385                if (k != nRow)
386                        matrix[nRow][k] -= val;
387}
388
389#ifdef DEBUG
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++)
394                        dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
395                dbg << endl;
396        }
397        return dbg;
398}
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.