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 numCities, tMatrix task, 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 &matrix);
00088 void cleanup();
00089 bool findCandidate(const tMatrix &matrix, int &nRow, int &nCol) const;
00090 double findMinInCol(int nCol, const tMatrix &matrix, int exr = -1) const;
00091 double findMinInRow(int nRow, const tMatrix &matrix, int exc = -1) const;
00092 bool hasSubCycles(int nRow, int nCol) const;
00093 void subCol(tMatrix &matrix, int nCol, double val);
00094 void subRow(tMatrix &matrix, int nRow, double val);
00095 };
00096
00097 #endif // TSPSOLVER_H
