1 | /*! |
---|
2 | * \file tspsolver.h |
---|
3 | * \author Copyright © 2007-2010 Lёppa <contacts[at]oleksii[dot]name> |
---|
4 | * |
---|
5 | * $Id: tspsolver.h 98 2010-03-12 19:28:42Z 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. |
---|
36 | typedef QList<QList<double> > TMatrix; |
---|
37 | |
---|
38 | /*! |
---|
39 | * \brief A structure that represents a candidate for branching. |
---|
40 | */ |
---|
41 | struct 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 | */ |
---|
60 | struct 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 © 2007-2010 Lёppa <contacts[at]oleksii[dot]name> |
---|
79 | */ |
---|
80 | class CTSPSolver |
---|
81 | { |
---|
82 | Q_DECLARE_TR_FUNCTIONS(CTSPSolver) |
---|
83 | |
---|
84 | public: |
---|
85 | CTSPSolver(); |
---|
86 | QString getSortedPath() const; |
---|
87 | static QString getVersionId(); |
---|
88 | bool isOptimal() const; |
---|
89 | SStep *solve(int numCities, TMatrix task, QWidget *parent = 0); |
---|
90 | ~CTSPSolver(); |
---|
91 | |
---|
92 | private: |
---|
93 | bool mayNotBeOptimal; |
---|
94 | int nCities; |
---|
95 | SStep *root; |
---|
96 | QHash<int,int> route; |
---|
97 | // QHash<int,int> forbidden; |
---|
98 | |
---|
99 | double align(TMatrix &matrix); |
---|
100 | void cleanup(); |
---|
101 | void deleteTree(SStep *&root); |
---|
102 | QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const; |
---|
103 | double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const; |
---|
104 | double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const; |
---|
105 | bool hasSubCycles(int nRow, int nCol) const; |
---|
106 | void subCol(TMatrix &matrix, int nCol, double val); |
---|
107 | void subRow(TMatrix &matrix, int nRow, double val); |
---|
108 | }; |
---|
109 | |
---|
110 | #ifdef DEBUG |
---|
111 | QDebug operator<<(QDebug dbg, const TMatrix &matrix); |
---|
112 | #endif |
---|
113 | |
---|
114 | #endif // TSPSOLVER_H |
---|