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

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

More code documentation.

  • Property svn:keywords set to Id URL
File size: 2.6 KB
Line 
1/*!
2 * \class CTSPSolver
3 * \author Copyright &copy; 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 * \brief This class solves Travelling Salesman Problem task.
5 *
6 *  $Id: tspsolver.h 65 2009-10-20 19:38:01Z laleppa $
7 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
8 *
9 *  <b>TSPSG: TSP Solver and Generator</b>
10 *
11 *  This file is part of TSPSG.
12 *
13 *  TSPSG is free software: you can redistribute it and/or modify
14 *  it under the terms of the GNU General Public License as published by
15 *  the Free Software Foundation, either version 3 of the License, or
16 *  (at your option) any later version.
17 *
18 *  TSPSG is distributed in the hope that it will be useful,
19 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
20 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21 *  GNU General Public License for more details.
22 *
23 *  You should have received a copy of the GNU General Public License
24 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
25 *
26 * \todo TODO: Deletion of solution tree on destroy and cleanup.
27 */
28
29#ifndef TSPSOLVER_H
30#define TSPSOLVER_H
31
32#include "globals.h"
33
34#include "tspmodel.h"
35
36//! A matrix of city-to-city travel costs.
37typedef QList<QList<double> > tMatrix;
38
39/*!
40 * \brief This structure represents one step of solving.
41 *
42 *  A tree of such elements will represent the solving process.
43 */
44//! \todo TODO: List alternative candidates.
45struct sStep {
46        tMatrix matrix; //!< This step's matrix
47        double price; //!< The price of travel to this step
48        struct {
49                int nRow; //!< A zero-based row number of the candidate
50                int nCol; //!< A zero-based column number of the candidate
51        } candidate; //!< A candiadate for branching in the current matrix
52        bool alts; //!< Indicates whether or not matrix has alternative candidates
53        sStep *plNode; //!< Pointer to the left branch step
54        sStep *prNode; //!< Pointer to the right branch step
55
56        //! Assigns default values
57        sStep() {
58                price = candidate.nRow = candidate.nCol = -1;
59                alts = false;
60                plNode = prNode = NULL;
61        }
62};
63
64class CTSPSolver
65{
66        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
67
68public:
69        CTSPSolver();
70        QString getSortedPath() const;
71        bool isOptimal() const;
72        sStep *solve(int, tMatrix, QWidget *parent = 0);
73        static QString getVersionId();
74
75private:
76        bool mayNotBeOptimal;
77        int nCities;
78        sStep *root;
79        QHash<int,int> route;
80//      QHash<int,int> forbidden;
81        double align(tMatrix &);
82        void cleanup();
83        bool findCandidate(tMatrix, int &, int &);
84        double findMinInRow(int, tMatrix, int exc = -1);
85        double findMinInCol(int, tMatrix, int exr = -1);
86        bool hasSubCycles(int, int);
87        void subCol(tMatrix &, int, double);
88        void subRow(tMatrix &, int, double);
89};
90
91#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.