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 *plNode;
00066 SStep *prNode;
00067
00069 SStep() {
00070 price = -1;
00071 plNode = prNode = NULL;
00072 }
00073 };
00074
00081 class CTSPSolver
00082 {
00083 Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
00084
00085 public:
00086 CTSPSolver();
00087 QString getSortedPath() const;
00088 static QString getVersionId();
00089 bool isOptimal() const;
00090 SStep *solve(int numCities, TMatrix task, QWidget *parent = 0);
00091 ~CTSPSolver();
00092
00093 private:
00094 bool mayNotBeOptimal;
00095 int nCities;
00096 SStep *root;
00097 QHash<int,int> route;
00098
00099
00100 double align(TMatrix &matrix);
00101 void cleanup();
00102 void deleteNode(SStep *&node);
00103 QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
00104 double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
00105 double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
00106 bool hasSubCycles(int nRow, int nCol) const;
00107 void subCol(TMatrix &matrix, int nCol, double val);
00108 void subRow(TMatrix &matrix, int nRow, double val);
00109 };
00110
00111 #endif // TSPSOLVER_H
