src/tspsolver.h
Go to the documentation of this file.
00001 00028 #ifndef TSPSOLVER_H 00029 #define TSPSOLVER_H 00030 00031 #include <QtCore> 00032 #include <limits> 00033 00041 #ifdef INFINITY 00042 #undef INFINITY 00043 #endif 00044 #define INFINITY std::numeric_limits<double>::infinity() 00045 00051 namespace TSPSolver { 00052 00054 typedef QList<QList<double> > TMatrix; 00055 00061 struct SStep { 00063 struct SCandidate { 00064 int nRow; 00065 int nCol; 00066 00068 SCandidate() { 00069 nCol = nRow = -1; 00070 } 00072 bool operator ==(const SCandidate &cand) const { 00073 return ((cand.nRow == nRow) && (cand.nCol == nCol)); 00074 } 00075 }; 00076 00078 enum NextStep { 00079 NoNextStep, 00080 LeftBranch, 00081 RightBranch 00082 }; 00083 00084 TMatrix matrix; 00085 double price; 00086 00087 SCandidate candidate; 00088 QList<SCandidate> alts; 00089 SStep *pNode; 00090 SStep *plNode; 00091 SStep *prNode; 00092 NextStep next; 00093 00095 SStep() { 00096 price = -1; 00097 pNode = plNode = prNode = NULL; 00098 next = NoNextStep; 00099 } 00100 }; 00101 00106 class CTSPSolver: public QObject 00107 { 00108 Q_OBJECT 00109 00110 public: 00111 static QString getVersionId(); 00112 00113 CTSPSolver(QObject *parent = NULL); 00114 void cleanup(bool processEvents = false); 00115 QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const; 00116 int getTotalSteps() const; 00117 bool isOptimal() const; 00118 void setCleanupOnCancel(bool enable = true); 00119 SStep *solve(int numCities, const TMatrix &task); 00120 bool wasCanceled() const; 00121 ~CTSPSolver(); 00122 00123 public slots: 00124 void cancel(); 00125 00126 signals: 00131 void routePartFound(int n); 00132 00133 private: 00134 bool mayNotBeOptimal, canceled, cc; 00135 int nCities, total; 00136 SStep *root; 00137 QHash<int,int> route; 00138 mutable QMutex mutex; 00139 00140 double align(TMatrix &matrix); 00141 void deleteTree(SStep *&root, bool processEvents = false); 00142 void denormalize(TMatrix &matrix) const; 00143 QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const; 00144 double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const; 00145 double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const; 00146 void finishRoute(); 00147 bool hasSubCycles(int nRow, int nCol) const; 00148 void normalize(TMatrix &matrix) const; 00149 void subCol(TMatrix &matrix, int nCol, double val); 00150 void subRow(TMatrix &matrix, int nRow, double val); 00151 }; 00152 00153 } 00154 00155 #ifdef DEBUG 00156 QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix); 00157 QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate); 00158 #endif // DEBUG 00159 00160 #endif // TSPSOLVER_H
