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

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

+ Added Fractional accuracy (in decimail places) to settings.
+ Created defaults.h file. Moved all default defines there.

  • Replaced all double types with qreal.
  • Replaced all calls to trUtf8() with tr() as we use setCodecForTr() to set UTF-8 encoding as default and tr() is enough.
  • Replaced all 2009 with 2010 in copyrights.
  • Fixed an error when loading .zkt file with less than 5 cities.
  • Property svn:keywords set to Id URL
File size: 3.2 KB
RevLine 
[65]1/*!
[67]2 * \file tspsolver.h
[87]3 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
[12]4 *
5 *  $Id: tspsolver.h 87 2010-01-12 14:11:24Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
[76]8 * \brief Defines #TMatrix typedef, SCandidate and SStep structs and CTSPSolver class.
[67]9 *
[65]10 *  <b>TSPSG: TSP Solver and Generator</b>
11 *
[12]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]31#include "globals.h"
[12]32
[64]33#include "tspmodel.h"
34
[65]35//! A matrix of city-to-city travel costs.
[87]36typedef QList<QList<qreal> > TMatrix;
[13]37
[65]38/*!
[74]39 * \brief A structure that represents a candidate for branching.
40 */
[76]41struct SCandidate {
[74]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
[76]46        SCandidate() {
[74]47                nCol = nRow = -1;
48        }
49        //! An operator == implementation
[76]50        bool operator ==(const SCandidate &cand) const {
[74]51                return ((cand.nRow == nRow) && (cand.nCol == nCol));
52        }
53};
54
55/*!
[65]56 * \brief This structure represents one step of solving.
57 *
58 *  A tree of such elements will represent the solving process.
59 */
[74]60struct SStep {
61        TMatrix matrix; //!< This step's matrix
[87]62        qreal price; //!< The price of travel to this step
[76]63        SCandidate candidate; //!< A candiadate for branching in the current matrix
64        QList<SCandidate> alts; //!< A list of alternative branching candidates
[74]65        SStep *plNode; //!< Pointer to the left branch step
66        SStep *prNode; //!< Pointer to the right branch step
[65]67
68        //! Assigns default values
[74]69        SStep() {
70                price = -1;
[65]71                plNode = prNode = NULL;
72        }
[12]73};
74
[67]75/*!
76 * \brief This class solves Travelling Salesman Problem task.
[87]77 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
[67]78 *
79 * \todo TODO: Deletion of solution tree on destroy and cleanup.
80 */
[12]81class CTSPSolver
82{
[42]83        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
84
[12]85public:
86        CTSPSolver();
[60]87        QString getSortedPath() const;
[67]88        static QString getVersionId();
[60]89        bool isOptimal() const;
[74]90        SStep *solve(int numCities, TMatrix task, QWidget *parent = 0);
91        ~CTSPSolver();
[42]92
[13]93private:
[60]94        bool mayNotBeOptimal;
[13]95        int nCities;
[74]96        SStep *root;
[42]97        QHash<int,int> route;
[50]98//      QHash<int,int> forbidden;
[67]99
[87]100        qreal align(TMatrix &matrix);
[42]101        void cleanup();
[77]102        void deleteNode(SStep *&node);
[76]103        QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
[87]104        qreal findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
105        qreal findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
[71]106        bool hasSubCycles(int nRow, int nCol) const;
[87]107        void subCol(TMatrix &matrix, int nCol, qreal val);
108        void subRow(TMatrix &matrix, int nRow, qreal val);
[12]109};
110
111#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.