source: tspsg/src/tspsolver.cpp @ 243b53b608

appveyorimgbotreadme
Last change on this file since 243b53b608 was 2940c14782, checked in by Oleksii Serdiuk, 11 years ago

Relicensed TSP Solver and Generator under GPLv2 license.

Due to potential conflicts between GPLv3 and app stores.

  • Property mode set to 100644
File size: 12.8 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2013 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 2 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#include <QCoreApplication>
27
28#ifdef DEBUG
29#   include <QDebug>
30#endif
31
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.
39 * \return A string: <b>\$Id: $Format:%h %ai %an$ $</b>.
40 */
41QString CTSPSolver::getVersionId()
42{
43    return QString("$Id: $Format:%h %ai %an$ $");
44}
45
46/*!
47 * \brief Constructs CTSPSolver object.
48 * \param parent A parent object.
49 */
50CTSPSolver::CTSPSolver(QObject *parent)
51    : QObject(parent), cc(true), nCities(0), total(0), root(NULL) {}
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 *
59 * \sa solve(), setCleanupOnCancel()
60 */
61void CTSPSolver::cleanup(bool processEvents)
62{
63    route.clear();
64    mayNotBeOptimal = false;
65    if (root != NULL)
66        deleteTree(root, processEvents);
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{
80    if (!root || route.isEmpty() || (route.size() != nCities))
81        return QString();
82
83int i = 0; // We start from City 1
84QStringList path;
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);
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{
102    return total;
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{
114    return !mayNotBeOptimal;
115}
116
117/*!
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{
129    cc = enable;
130}
131
132/*!
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{
142    if (numCities < 3)
143        return NULL;
144
145QMutexLocker locker(&mutex);
146    cleanup();
147    canceled = false;
148    locker.unlock();
149
150    nCities = numCities;
151
152SStep *step = new SStep();
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);
158#ifdef DEBUG
159    qDebug() << step->matrix;
160#endif // DEBUG
161    step->price = align(step->matrix);
162    root = step;
163
164SStep *left, *right;
165int nRow, nCol;
166bool firstStep = true;
167double check = INFINITY;
168    total = 0;
169    while (route.size() < nCities) {
170        step->alts = findCandidate(step->matrix,nRow,nCol);
171
172        while (hasSubCycles(nRow,nCol)) {
173#ifdef DEBUG
174            qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
175#endif // DEBUG
176            step->matrix[nRow][nCol] = INFINITY;
177            step->price += align(step->matrix);
178            step->alts = findCandidate(step->matrix,nRow,nCol);
179        }
180
181#ifdef DEBUG
182        qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
183        qDebug() << "Alternate:" << step->alts;
184        qDebug() << "Step price:" << step->price << endl;
185#endif // DEBUG
186
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;
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);
260    return canceled;
261}
262
263/*!
264 * \brief Cancels the solution process.
265 */
266void CTSPSolver::cancel()
267{
268QMutexLocker locker(&mutex);
269    canceled = true;
270}
271
272CTSPSolver::~CTSPSolver()
273{
274    if (root != NULL)
275        deleteTree(root);
276}
277
278/* Privates **********************************************************/
279
280double CTSPSolver::align(TMatrix &matrix)
281{
282double r = 0;
283double min;
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;
301}
302
303void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
304{
305    if (root == NULL)
306        return;
307SStep *step = root;
308SStep *parent;
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    }
336}
337
338void CTSPSolver::denormalize(TMatrix &matrix) const
339{
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;
344}
345
346QList<SStep::SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
347{
348    nRow = -1;
349    nCol = -1;
350QList<SStep::SCandidate> alts;
351SStep::SCandidate cand;
352double h = -1;
353double sum;
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;
370}
371
372double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
373{
374double min = INFINITY;
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;
379}
380
381double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
382{
383double min = INFINITY;
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;
389}
390
391bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
392{
393    if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
394        return false;
395int i = nCol;
396    forever {
397        if ((i = route.value(i)) == nRow)
398            return true;
399        if (!route.contains(i))
400            return false;
401    }
402    return false;
403}
404
405void CTSPSolver::normalize(TMatrix &matrix) const
406{
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;
411}
412
413void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
414{
415    for (int k = 0; k < nCities; k++)
416        if (k != nCol)
417            matrix[k][nCol] -= val;
418}
419
420void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
421{
422    for (int k = 0; k < nCities; k++)
423        if (k != nRow)
424            matrix[nRow][k] -= val;
425}
426
427}
428
429#ifdef DEBUG
430QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix)
431{
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;
438}
439
440QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &cand)
441{
442    dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
443    return dbg;
444}
445#endif // DEBUG
Note: See TracBrowser for help on using the repository browser.