00001
00028 #ifndef TSPSOLVER_H
00029 #define TSPSOLVER_H
00030
00031 #include "globals.h"
00032
00033 #include "tspmodel.h"
00034
00036 typedef QList<QList<double> > tMatrix;
00037
00043
00044 struct sStep {
00045 tMatrix matrix;
00046 double price;
00047 struct {
00048 int nRow;
00049 int nCol;
00050 } candidate;
00051 bool alts;
00052 sStep *plNode;
00053 sStep *prNode;
00054
00056 sStep() {
00057 price = candidate.nRow = candidate.nCol = -1;
00058 alts = false;
00059 plNode = prNode = NULL;
00060 }
00061 };
00062
00069 class CTSPSolver
00070 {
00071 Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
00072
00073 public:
00074 CTSPSolver();
00075 QString getSortedPath() const;
00076 static QString getVersionId();
00077 bool isOptimal() const;
00078 sStep *solve(int, tMatrix, QWidget *parent = 0);
00079
00080 private:
00081 bool mayNotBeOptimal;
00082 int nCities;
00083 sStep *root;
00084 QHash<int,int> route;
00085
00086
00087 double align(tMatrix &);
00088 void cleanup();
00089 bool findCandidate(tMatrix, int &, int &);
00090 double findMinInCol(int, tMatrix, int exr = -1);
00091 double findMinInRow(int, tMatrix, int exc = -1);
00092 bool hasSubCycles(int, int);
00093 void subCol(tMatrix &, int, double);
00094 void subRow(tMatrix &, int, double);
00095 };
00096
00097 #endif // TSPSOLVER_H
