source: tspsg-svn/trunk/src/tspsolver.h @ 102

Last change on this file since 102 was 99, checked in by laleppa, 15 years ago
  • Fixed a bug when a solution couldn't be found for some tasks while the task had at least one solution (mostly, tasks with a lot of restrictions).
  • Fixed a bug when Save As dialog always appeared (even for non-Untitled files) when selecting Save in Unsaved Changes dialog.
  • Improved the solution algorithm.
  • Moved progress dialog from CTSPSolver to MainWindow?. CTSPSolver doesn't contain any GUI related code now.

+ Added routePartFound() signal to CTSPSolver which is emitted once every time a part of the route is found.
+ Added cancel() slot and wasCanceled() public function to CTSPSolver to be able to cancel a solution process and to know whether it was canceled.
+ Progress is now shown when generating a solution output.
+ Check for updates functionality (only in Windows version at this moment).

  • Property svn:keywords set to Id URL
File size: 3.7 KB
Line 
1/*!
2 * \file tspsolver.h
3 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.h 99 2010-03-22 20:45:16Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
8 * \brief Defines #TMatrix typedef, SCandidate and SStep structs and CTSPSolver class.
9 *
10 *  <b>TSPSG: TSP Solver and Generator</b>
11 *
12 *  This file is part of TSPSG.
13 *
14 *  TSPSG is free software: you can redistribute it and/or modify
15 *  it under the terms of the GNU General Public License as published by
16 *  the Free Software Foundation, either version 3 of the License, or
17 *  (at your option) any later version.
18 *
19 *  TSPSG is distributed in the hope that it will be useful,
20 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
21 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22 *  GNU General Public License for more details.
23 *
24 *  You should have received a copy of the GNU General Public License
25 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
26 */
27
28#ifndef TSPSOLVER_H
29#define TSPSOLVER_H
30
31#include "globals.h"
32
33#include "tspmodel.h"
34
35//! A matrix of city-to-city travel costs.
36typedef QList<QList<double> > TMatrix;
37
38/*!
39 * \brief A structure that represents a candidate for branching.
40 */
41struct SCandidate {
42        int nRow; //!< A zero-based row number of the candidate
43        int nCol; //!< A zero-based column number of the candidate
44
45        //! Assigns default values
46        SCandidate() {
47                nCol = nRow = -1;
48        }
49        //! An operator == implementation
50        bool operator ==(const SCandidate &cand) const {
51                return ((cand.nRow == nRow) && (cand.nCol == nCol));
52        }
53};
54
55/*!
56 * \brief This structure represents one step of solving.
57 *
58 *  A tree of such elements will represent the solving process.
59 */
60struct SStep {
61        TMatrix matrix; //!< This step's matrix
62        double price; //!< The price of travel to this step
63        SCandidate candidate; //!< A candiadate for branching in the current matrix
64        QList<SCandidate> alts; //!< A list of alternative branching candidates
65        SStep *pNode; //!< Pointer to the parent step
66        SStep *plNode; //!< Pointer to the left branch step
67        SStep *prNode; //!< Pointer to the right branch step
68
69        //! Assigns default values
70        SStep() {
71                price = -1;
72                pNode = plNode = prNode = NULL;
73        }
74};
75
76/*!
77 * \brief This class solves Travelling Salesman Problem task.
78 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
79 */
80class CTSPSolver: public QObject
81{
82        Q_OBJECT
83
84public:
85        static QString getVersionId();
86
87        CTSPSolver(QObject *parent = NULL);
88        void cleanup(bool processEvents = false);
89        QString getSortedPath() const;
90        bool isOptimal() const;
91        SStep *solve(int numCities, const TMatrix &task);
92        bool wasCanceled() const;
93        ~CTSPSolver();
94
95public slots:
96        void cancel();
97
98signals:
99        /*!
100         * \brief This signal is emitted once every time a part of the route is found.
101         * \param n Indicates the number of the route parts found.
102         */
103        void routePartFound(int n);
104
105private:
106        bool mayNotBeOptimal, canceled;
107        int nCities;
108        SStep *root;
109        QHash<int,int> route;
110        mutable QMutex mutex;
111
112        double align(TMatrix &matrix);
113        void deleteTree(SStep *&root, bool processEvents = false);
114        void denormalize(TMatrix &matrix) const;
115        QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
116        double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
117        double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
118        bool hasSubCycles(int nRow, int nCol) const;
119        void normalize(TMatrix &matrix) const;
120        void subCol(TMatrix &matrix, int nCol, double val);
121        void subRow(TMatrix &matrix, int nRow, double val);
122};
123
124#ifdef DEBUG
125QDebug operator<<(QDebug dbg, const TMatrix &matrix);
126QDebug operator<<(QDebug dbg, const SCandidate &candidate);
127#endif // DEBUG
128
129#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.