source: tspsg/src/tspsolver.cpp @ b96b44b6b7

appveyorimgbotreadme
Last change on this file since b96b44b6b7 was 07e43cf61a, checked in by Oleksii Serdiuk, 12 years ago

Improved compilation time by about 30%.

By reducing number of includes to only required minimum.

NOTE: Compilation time comparison was done by measuring compilation time
while using only one thread (i.e., "make -j1").

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