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

Last change on this file since 67 was 67, checked in by laleppa, 15 years ago
  • Finished documentation.
  • Sorted all functions in .cpp files according to order of their declaration in .h files.
  • Property svn:keywords set to Id URL
File size: 2.8 KB
Line 
1/*!
2 * \file tspsolver.h
3 * \author Copyright &copy; 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.h 67 2009-10-24 13:37:48Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
8 * \brief Defines #tMatrix typedef, sStep struct 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 This structure represents one step of solving.
40 *
41 *  A tree of such elements will represent the solving process.
42 */
43//! \todo TODO: List alternative candidates.
44struct sStep {
45        tMatrix matrix; //!< This step's matrix
46        double price; //!< The price of travel to this step
47        struct {
48                int nRow; //!< A zero-based row number of the candidate
49                int nCol; //!< A zero-based column number of the candidate
50        } candidate; //!< A candiadate for branching in the current matrix
51        bool alts; //!< Indicates whether or not matrix has alternative candidates
52        sStep *plNode; //!< Pointer to the left branch step
53        sStep *prNode; //!< Pointer to the right branch step
54
55        //! Assigns default values
56        sStep() {
57                price = candidate.nRow = candidate.nCol = -1;
58                alts = false;
59                plNode = prNode = NULL;
60        }
61};
62
63/*!
64 * \brief This class solves Travelling Salesman Problem task.
65 * \author Copyright &copy; 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
66 *
67 * \todo TODO: Deletion of solution tree on destroy and cleanup.
68 */
69class CTSPSolver
70{
71        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
72
73public:
74        CTSPSolver();
75        QString getSortedPath() const;
76        static QString getVersionId();
77        bool isOptimal() const;
78        sStep *solve(int, tMatrix, QWidget *parent = 0);
79
80private:
81        bool mayNotBeOptimal;
82        int nCities;
83        sStep *root;
84        QHash<int,int> route;
85//      QHash<int,int> forbidden;
86
87        double align(tMatrix &);
88        void cleanup();
89        bool findCandidate(tMatrix, int &, int &);
90        double findMinInCol(int, tMatrix, int exr = -1);
91        double findMinInRow(int, tMatrix, int exc = -1);
92        bool hasSubCycles(int, int);
93        void subCol(tMatrix &, int, double);
94        void subRow(tMatrix &, int, double);
95};
96
97#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.