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

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

+ Implemented File/Save? action.
+ Added "Save Solution" and "Back to Task" buttons to Solution tab for better usability.

  • Increased maximum number of cities to 20. Solving for 18-20 cities is already takes much time, so I thought it doesn't make sense to increase more.
  • Columns and rows are now resized to contents on all platforms.
  • Property svn:keywords set to Id URL
File size: 2.0 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.h 50 2009-08-03 15:15:46Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
8 *  This file is part of TSPSG.
9 *
10 *  TSPSG is free software: you can redistribute it and/or modify
11 *  it under the terms of the GNU General Public License as published by
12 *  the Free Software Foundation, either version 3 of the License, or
13 *  (at your option) any later version.
14 *
15 *  TSPSG is distributed in the hope that it will be useful,
16 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 *  GNU General Public License for more details.
19 *
20 *  You should have received a copy of the GNU General Public License
21 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#ifndef TSPSOLVER_H
25#define TSPSOLVER_H
26
27#include "globals.h"
28
29typedef QList<QList<double> > tMatrix;
30
31// This structure represents one step of solving
32// The tree of such elements will represent the solving process
33struct sStep {
34        tMatrix matrix; // Steps's matrix
35        double price; // Price of travel to this step
36        struct {unsigned int nRow; unsigned int nCol;} candidate; // Candiadate for branching in current matrix
37        bool alts; // This matrix has alternative candidates
38        sStep *plNode, *prNode; // Pointers to left and right branch steps
39        sStep() { price = candidate.nRow = candidate.nCol = -1; alts = false; plNode = prNode = NULL; } // Default values
40};
41
42// TSP Solver class
43class CTSPSolver
44{
45        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
46
47public:
48        CTSPSolver();
49        sStep *solve(int, tMatrix, QWidget *parent = 0);
50
51private:
52        int nCities;
53        sStep *root;
54        QHash<int,int> route;
55//      QHash<int,int> forbidden;
56        double align(tMatrix &);
57        void cleanup();
58        bool findCandidate(tMatrix, int &, int &, double &);
59        double findMinInRow(int, tMatrix, int exc = -1);
60        double findMinInCol(int, tMatrix, int exr = -1);
61        bool hasSubCycles(int, int);
62        void subCol(tMatrix &, int, double);
63        void subRow(tMatrix &, int, double);
64};
65
66#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.