source: tspsg/src/tspsolver.h @ 21c03af787

appveyorimgbotreadme
Last change on this file since 21c03af787 was 21c03af787, checked in by Oleksii Serdiuk, 11 years ago

Updated copyright endyear from 2012 to 2013.

  • Property mode set to 100644
File size: 4.9 KB
Line 
1/*!
2 * \file tspsolver.h
3 * \author Copyright &copy; 2007-2013 Oleksii Serdiuk <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: $Format:%h %ai %an$ $
6 *  $URL: http://tspsg.info/ $
7 *
8 * \brief Defines TSPSolver namespace and everything needed for solving TSP tasks.
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 <limits>
32
33#include <QHash>
34#include <QMutex>
35#include <QObject>
36#include <QStringList>
37
38/*!
39 * \def INFINITY
40 * \brief This value means infinity :-)
41 *
42 *  Define \c INFINITY if it's not already defined.
43 */
44#ifndef INFINITY
45#   define INFINITY std::numeric_limits<double>::infinity()
46#endif
47
48/*!
49 * \brief A TSP Solver namespace.
50 *
51 *  This namespace contains all the stuff required for solving TSP tasks.
52 */
53namespace TSPSolver {
54
55//! A matrix of city-to-city travel costs
56typedef QList<QList<double> > TMatrix;
57
58/*!
59 * \brief This structure represents one step of solving.
60 *
61 *  A tree of such elements will represent the solving process.
62 */
63struct SStep {
64    //! A structure that represents a candidate for branching
65    struct SCandidate {
66        int nRow; //!< A zero-based row number of the candidate
67        int nCol; //!< A zero-based column number of the candidate
68
69        //! Assigns default values
70        SCandidate() {
71            nCol = nRow = -1;
72        }
73        //! An operator == implementation
74        bool operator ==(const SCandidate &cand) const {
75            return ((cand.nRow == nRow) && (cand.nCol == nCol));
76        }
77    };
78
79    //! An enum that describes possible selection of the next step
80    enum NextStep {
81        NoNextStep, //!< No next step (end of solution)
82        LeftBranch, //!< Left branch was selected for the next step
83        RightBranch //!< Right branch was selected for the next step
84    };
85
86    TMatrix matrix; //!< This step's matrix
87    double price; //!< The price of travel to this step
88
89    SCandidate candidate; //!< A candiadate for branching in the current step
90    QList<SCandidate> alts; //!< A list of alternative branching candidates
91    SStep *pNode; //!< Pointer to the parent step
92    SStep *plNode; //!< Pointer to the left branch step
93    SStep *prNode; //!< Pointer to the right branch step
94    NextStep next; //!< Indicates what branch was selected for the next step
95
96    //! Assigns default values
97    SStep() {
98        price = -1;
99        pNode = plNode = prNode = NULL;
100        next = NoNextStep;
101    }
102};
103
104/*!
105 * \brief This class solves Travelling Salesman Problem task.
106 * \author Copyright &copy; 2007-2013 Oleksii Serdiuk <contacts[at]oleksii[dot]name>
107 */
108class CTSPSolver: public QObject
109{
110    Q_OBJECT
111
112public:
113    static QString getVersionId();
114
115    CTSPSolver(QObject *parent = NULL);
116    void cleanup(bool processEvents = false);
117    QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;
118    int getTotalSteps() const;
119    bool isOptimal() const;
120    void setCleanupOnCancel(bool enable = true);
121    SStep *solve(int numCities, const TMatrix &task);
122    bool wasCanceled() const;
123    ~CTSPSolver();
124
125public slots:
126    void cancel();
127
128signals:
129    /*!
130     * \brief This signal is emitted once every time a part of the route is found.
131     * \param n Indicates the number of the route parts found.
132     */
133    void routePartFound(int n);
134
135private:
136    bool mayNotBeOptimal, canceled, cc;
137    int nCities, total;
138    SStep *root;
139    QHash<int,int> route;
140    mutable QMutex mutex;
141
142    double align(TMatrix &matrix);
143    void deleteTree(SStep *&root, bool processEvents = false);
144    void denormalize(TMatrix &matrix) const;
145    QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
146    double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
147    double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
148    void finishRoute();
149    bool hasSubCycles(int nRow, int nCol) const;
150    void normalize(TMatrix &matrix) const;
151    void subCol(TMatrix &matrix, int nCol, double val);
152    void subRow(TMatrix &matrix, int nRow, double val);
153};
154
155}
156
157#ifdef DEBUG
158QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
159QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
160#endif // DEBUG
161
162#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.