source: tspsg/src/tspsolver.cpp @ 0af510a462

appveyorimgbotreadme
Last change on this file since 0af510a462 was 0af510a462, checked in by Oleksii Serdiuk, 12 years ago

Updated year in copyright headers...

  • Property mode set to 100644
File size: 12.7 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2012 Oleksii Serdiuk <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: $Format:%h %ai %an$ $
6 *  $URL: http://tspsg.info/ $
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: $Format:%h %ai %an$ $</b>.
34 */
35QString CTSPSolver::getVersionId()
36{
37    return QString("$Id: $Format:%h %ai %an$ $");
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.