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 = " -> ") const;
00116 int getTotalSteps() const;
00117 bool isOptimal() const;
00118 SStep *solve(int numCities, const TMatrix &task);
00119 bool wasCanceled() const;
00120 ~CTSPSolver();
00121
00122 public slots:
00123 void cancel();
00124
00125 signals:
00130 void routePartFound(int n);
00131
00132 private:
00133 bool mayNotBeOptimal, canceled;
00134 int nCities, total;
00135 SStep *root;
00136 QHash<int,int> route;
00137 mutable QMutex mutex;
00138
00139 double align(TMatrix &matrix);
00140 void deleteTree(SStep *&root, bool processEvents = false);
00141 void denormalize(TMatrix &matrix) const;
00142 QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
00143 double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
00144 double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
00145 void finishRoute();
00146 bool hasSubCycles(int nRow, int nCol) const;
00147 void normalize(TMatrix &matrix) const;
00148 void subCol(TMatrix &matrix, int nCol, double val);
00149 void subRow(TMatrix &matrix, int nRow, double val);
00150 };
00151
00152 }
00153
00154 #ifdef DEBUG
00155 QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
00156 QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
00157 #endif // DEBUG
00158
00159 #endif // TSPSOLVER_H
