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
00041 struct SCandidate {
00042 int nRow;
00043 int nCol;
00044
00046 SCandidate() {
00047 nCol = nRow = -1;
00048 }
00050 bool operator ==(const SCandidate &cand) const {
00051 return ((cand.nRow == nRow) && (cand.nCol == nCol));
00052 }
00053 };
00054
00060 struct SStep {
00061 TMatrix matrix;
00062 double price;
00063 SCandidate candidate;
00064 QList<SCandidate> alts;
00065 SStep *pNode;
00066 SStep *plNode;
00067 SStep *prNode;
00068
00070 SStep() {
00071 price = -1;
00072 pNode = plNode = prNode = NULL;
00073 }
00074 };
00075
00080 class CTSPSolver
00081 {
00082 Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
00083
00084 public:
00085 CTSPSolver();
00086 QString getSortedPath() const;
00087 static QString getVersionId();
00088 bool isOptimal() const;
00089 SStep *solve(int numCities, TMatrix task, QWidget *parent = 0);
00090 ~CTSPSolver();
00091
00092 private:
00093 bool mayNotBeOptimal;
00094 int nCities;
00095 SStep *root;
00096 QHash<int,int> route;
00097
00098
00099 double align(TMatrix &matrix);
00100 void cleanup();
00101 void deleteTree(SStep *&root);
00102 QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
00103 double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
00104 double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
00105 bool hasSubCycles(int nRow, int nCol) const;
00106 void subCol(TMatrix &matrix, int nCol, double val);
00107 void subRow(TMatrix &matrix, int nRow, double val);
00108 };
00109
00110 #endif // TSPSOLVER_H
