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

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

+ Added SStep::next that indicates what branch was selected for the next step.
+ Added "Show solution graph" option.
+ New CTSPSolver::getTotalSteps() method that returns a total number of steps in the current solution.

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