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: public QObject
00081 {
00082 Q_OBJECT
00083
00084 public:
00085 static QString getVersionId();
00086
00087 CTSPSolver(QObject *parent = NULL);
00088 void cleanup(bool processEvents = false);
00089 QString getSortedPath() const;
00090 bool isOptimal() const;
00091 SStep *solve(int numCities, const TMatrix &task);
00092 bool wasCanceled() const;
00093 ~CTSPSolver();
00094
00095 public slots:
00096 void cancel();
00097
00098 signals:
00103 void routePartFound(int n);
00104
00105 private:
00106 bool mayNotBeOptimal, canceled;
00107 int nCities;
00108 SStep *root;
00109 QHash<int,int> route;
00110 mutable QMutex mutex;
00111
00112 double align(TMatrix &matrix);
00113 void deleteTree(SStep *&root, bool processEvents = false);
00114 void denormalize(TMatrix &matrix) const;
00115 QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
00116 double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
00117 double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
00118 bool hasSubCycles(int nRow, int nCol) const;
00119 void normalize(TMatrix &matrix) const;
00120 void subCol(TMatrix &matrix, int nCol, double val);
00121 void subRow(TMatrix &matrix, int nRow, double val);
00122 };
00123
00124 #ifdef DEBUG
00125 QDebug operator<<(QDebug dbg, const TMatrix &matrix);
00126 QDebug operator<<(QDebug dbg, const SCandidate &candidate);
00127 #endif // DEBUG
00128
00129 #endif // TSPSOLVER_H
