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

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

Translations updated...

  • Property svn:keywords set to Id URL
File size: 7.7 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.cpp 79 2009-12-18 13:07:48Z 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//! Class constructor
27CTSPSolver::CTSPSolver()
28        : nCities(0), root(NULL)
29{
30}
31
32/*!
33 * \brief Returns the sorted optimal path, starting from City 1.
34 * \return A string, containing sorted optimal path.
35 */
36QString CTSPSolver::getSortedPath() const
37{
38        if (!root || route.isEmpty() || (route.size() != nCities))
39                return QString();
40
41int i = 0; // We start from City 1
42QString path = trUtf8("City %1").arg(1) + " -> ";
43        while ((i = route[i]) != 0) {
44                path += trUtf8("City %1").arg(i + 1) + " -> ";
45        }
46        // And finish in City 1, too
47        path += trUtf8("City %1").arg(1);
48
49        return path;
50}
51
52/*!
53 * \brief Returns CTSPSolver's version ID.
54 * \return A string: <b>\$Id: tspsolver.cpp 79 2009-12-18 13:07:48Z laleppa $</b>.
55 */
56QString CTSPSolver::getVersionId()
57{
58        return QString("$Id: tspsolver.cpp 79 2009-12-18 13:07:48Z laleppa $");
59}
60
61/*!
62 * \brief Returns whether or not the solution is definitely optimal.
63 * \return \c true if solution is definitely optimal, otherwise \c false.
64 *
65 *  The solution may need some further interations to determine whether it is optimal.
66 *  In such cases this function returns \c false.
67 */
68bool CTSPSolver::isOptimal() const
69{
70        return !mayNotBeOptimal;
71}
72
73/*!
74 * \brief Solves the given task.
75 * \param numCities Number of cities in the task.
76 * \param task The matrix of city-to-city travel costs.
77 * \param parent The parent widget for displaying messages and dialogs.
78 * \return Pointer to the root of the solution tree.
79 *
80 * \todo TODO: Comment the algorithm.
81 */
82SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
83{
84        if (numCities <= 1)
85                return NULL;
86        cleanup();
87        nCities = numCities;
88QProgressDialog pd(parent);
89QProgressBar *pb = new QProgressBar(&pd);
90        pb->setAlignment(Qt::AlignCenter);
91        pb->setFormat(trUtf8("%v of %m parts found"));
92        pd.setBar(pb);
93        pd.setMaximum(nCities);
94        pd.setMinimumDuration(1000);
95        pd.setLabelText(trUtf8("Calculating optimal route..."));
96        pd.setWindowTitle(trUtf8("Solution Progress"));
97        pd.setWindowModality(Qt::ApplicationModal);
98        pd.setValue(0);
99
100SStep *step = new SStep();
101        step->matrix = task;
102        step->price = align(step->matrix);
103        root = step;
104
105SStep *left, *right;
106int nRow, nCol;
107bool firstStep = true;
108double check;
109        while (this->route.size() < nCities) {
110//              forbidden.clear();
111                step->alts = findCandidate(step->matrix,nRow,nCol);
112                while (hasSubCycles(nRow,nCol)) {
113//                      forbidden[nRow] = nCol;
114                        step->matrix[nRow][nCol] = INFINITY;
115                        step->price += align(step->matrix);
116                        step->alts = findCandidate(step->matrix,nRow,nCol);
117                }
118                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
119                        cleanup();
120                        break;
121                }
122
123                // Route with (nRow,nCol) path
124                right = new SStep();
125                right->matrix = step->matrix;
126                for (int k = 0; k < nCities; k++) {
127                        if (k != nCol)
128                                right->matrix[nRow][k] = INFINITY;
129                        if (k != nRow)
130                                right->matrix[k][nCol] = INFINITY;
131                }
132                right->price = step->price + align(right->matrix);
133                // Forbid selected route to exclude its reuse in next steps.
134                right->matrix[nCol][nRow] = INFINITY;
135                right->matrix[nRow][nCol] = INFINITY;
136
137                // Route without (nRow,nCol) path
138                left = new SStep();
139                left->matrix = step->matrix;
140                left->matrix[nRow][nCol] = INFINITY;
141                left->price = step->price + align(left->matrix);
142
143                step->candidate.nRow = nRow;
144                step->candidate.nCol = nCol;
145                step->plNode = left;
146                step->prNode = right;
147
148                if (right->price <= left->price) {
149                        // Route with (nRow,nCol) path is cheaper
150                        step = right;
151                        this->route[nRow] = nCol;
152                        pd.setValue(this->route.size());
153                        if (firstStep) {
154                                check = left->price;
155                                firstStep = false;
156                        }
157                } else {
158                        // Route without (nRow,nCol) path is cheaper
159                        step = left;
160                        qApp->processEvents();
161                        if (firstStep) {
162                                check = right->price;
163                                firstStep = false;
164                        }
165                }
166        }
167
168        if (!root && !pd.wasCanceled()) {
169                pd.reset();
170                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
171        }
172
173        qApp->processEvents();
174
175        if (root) {
176                route = this->route;
177                mayNotBeOptimal = (check < step->price);
178        }
179        return root;
180}
181
182CTSPSolver::~CTSPSolver()
183{
184        if (root != NULL)
185                deleteNode(root);
186}
187
188/* Privates **********************************************************/
189
190double CTSPSolver::align(TMatrix &matrix)
191{
192double r = 0;
193double min;
194        for (int k = 0; k < nCities; k++) {
195                min = findMinInRow(k,matrix);
196                if (min > 0) {
197                        r += min;
198                        subRow(matrix,k,min);
199                }
200        }
201        for (int k = 0; k < nCities; k++) {
202                min = findMinInCol(k,matrix);
203                if (min > 0) {
204                        r += min;
205                        subCol(matrix,k,min);
206                }
207        }
208        return r;
209}
210
211void CTSPSolver::cleanup()
212{
213        QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
214        route.clear();
215        mayNotBeOptimal = false;
216        if (root != NULL)
217                deleteNode(root);
218        QApplication::restoreOverrideCursor();
219}
220
221void CTSPSolver::deleteNode(SStep *&node)
222{
223//static int x;
224//      x++;
225//qDebug() << ">>>" << x;
226        if (node->plNode != NULL)
227                deleteNode(node->plNode);
228        if (node->prNode != NULL)
229                deleteNode(node->prNode);
230        delete node;
231        node = NULL;
232//qDebug() << "<<<" << x;
233//      x--;
234}
235
236QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
237{
238        nRow = -1;
239        nCol = -1;
240QList<SCandidate> alts;
241SCandidate cand;
242double h = -1;
243double sum;
244        for (int r = 0; r < nCities; r++)
245                for (int c = 0; c < nCities; c++)
246//                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
247                        if (matrix.at(r).at(c) == 0) {
248                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
249                                if (sum > h) {
250                                        h = sum;
251                                        nRow = r;
252                                        nCol = c;
253                                        alts.clear();
254                                } else if ((sum == h) && !hasSubCycles(r,c)) {
255                                        cand.nRow = r;
256                                        cand.nCol = c;
257                                        alts.append(cand);
258                                }
259                        }
260        return alts;
261}
262
263double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
264{
265double min = INFINITY;
266        for (int k = 0; k < nCities; k++)
267                if ((k != exr) && (min > matrix.at(k).at(nCol)))
268                        min = matrix.at(k).at(nCol);
269        return min == INFINITY ? 0 : min;
270}
271
272double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
273{
274double min = INFINITY;
275        for (int k = 0; k < nCities; k++)
276                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
277                        min = matrix.at(nRow).at(k);
278        return min == INFINITY ? 0 : min;
279}
280
281bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
282{
283        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
284                return false;
285int i = nCol;
286        while (true) {
287                if ((i = route[i]) == nRow)
288                        return true;
289                if (!route.contains(i))
290                        return false;
291        }
292        return false;
293}
294
295void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
296{
297        for (int k = 0; k < nCities; k++)
298                if (k != nCol)
299                        matrix[k][nCol] -= val;
300}
301
302void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
303{
304        for (int k = 0; k < nCities; k++)
305                if (k != nRow)
306                        matrix[nRow][k] -= val;
307}
Note: See TracBrowser for help on using the repository browser.