Changeset 394216e468 in tspsg for src/tspsolver.cpp


Ignore:
Timestamp:
Mar 22, 2010, 9:45:16 PM (14 years ago)
Author:
Oleksii Serdiuk
Branches:
0.1.3.145-beta1-symbian, 0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme
Children:
1babbd6ba3
Parents:
e2abfd326f
Message:
  • Fixed a bug when a solution couldn't be found for some tasks while the task had at least one solution (mostly, tasks with a lot of restrictions).
  • Fixed a bug when Save As dialog always appeared (even for non-Untitled files) when selecting Save in Unsaved Changes dialog.
  • Improved the solution algorithm.
  • Moved progress dialog from CTSPSolver to MainWindow?. CTSPSolver doesn't contain any GUI related code now.

+ Added routePartFound() signal to CTSPSolver which is emitted once every time a part of the route is found.
+ Added cancel() slot and wasCanceled() public function to CTSPSolver to be able to cancel a solution process and to know whether it was canceled.
+ Progress is now shown when generating a solution output.
+ Check for updates functionality (only in Windows version at this moment).

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/tspsolver.cpp

    re2abfd326f r394216e468  
    2424#include "tspsolver.h"
    2525
    26 //! Class constructor
    27 CTSPSolver::CTSPSolver()
    28         : nCities(0), root(NULL)
    29 {
     26//! \internal \brief A short for maximum double, used internally in the solution algorithm.
     27#define MAX_DOUBLE std::numeric_limits<double>::max()
     28
     29/*!
     30 * \brief Returns CTSPSolver's version ID.
     31 * \return A string: <b>\$Id$</b>.
     32 */
     33QString CTSPSolver::getVersionId()
     34{
     35        return QString("$Id$");
     36}
     37
     38/*!
     39 * \brief Constructs CTSPSolver object.
     40 * \param parent A parent object.
     41 */
     42CTSPSolver::CTSPSolver(QObject *parent)
     43        : QObject(parent), nCities(0), root(NULL) {}
     44
     45/*!
     46 * \brief Cleans up the object and frees up memory used by the solution tree.
     47 * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
     48 * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
     49 * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
     50 *
     51 * \sa solve()
     52 */
     53void CTSPSolver::cleanup(bool processEvents)
     54{
     55        if (!processEvents)
     56                QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
     57        route.clear();
     58        mayNotBeOptimal = false;
     59        if (root != NULL)
     60                deleteTree(root, processEvents);
     61        if (!processEvents)
     62                QApplication::restoreOverrideCursor();
    3063}
    3164
    … …  
    5184
    5285/*!
    53  * \brief Returns CTSPSolver's version ID.
    54  * \return A string: <b>\$Id$</b>.
    55  */
    56 QString CTSPSolver::getVersionId()
    57 {
    58         return QString("$Id$");
    59 }
    60 
    61 /*!
    62  * \brief Returns whether or not the solution is definitely optimal.
    63  * \return \c true if solution is definitely optimal, otherwise \c false.
    64  *
    65  *  The solution may need some further interations to determine whether it is optimal.
     86 * \brief Indicates whether or not the solution is definitely optimal.
     87 * \return \c true if the solution is definitely optimal, otherwise \c false.
     88 *
     89 *  The solution may need some further iterations to determine whether or not it is optimal.
    6690 *  In such cases this function returns \c false.
    6791 */
    … …  
    7599 * \param numCities Number of cities in the task.
    76100 * \param task The matrix of city-to-city travel costs.
    77  * \param parent The parent widget for displaying messages and dialogs.
    78101 * \return Pointer to the root of the solution tree.
    79102 *
    80103 * \todo TODO: Comment the algorithm.
    81104 */
    82 SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
     105SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
    83106{
    84107        if (numCities <= 1)
    85108                return NULL;
     109
     110QMutexLocker locker(&mutex);
    86111        cleanup();
     112        canceled = false;
     113        locker.unlock();
     114
    87115        nCities = numCities;
    88 QProgressDialog pd(parent);
    89 QProgressBar *pb = new QProgressBar(&pd);
    90         pb->setAlignment(Qt::AlignCenter);
    91         pb->setFormat(tr("%v of %m parts found"));
    92         pd.setBar(pb);
    93         pd.setMaximum(nCities);
    94         pd.setMinimumDuration(1000);
    95         pd.setLabelText(tr("Calculating optimal route..."));
    96         pd.setWindowTitle(tr("Solution Progress"));
    97         pd.setWindowModality(Qt::ApplicationModal);
    98         pd.setValue(0);
    99116
    100117SStep *step = new SStep();
    101118        step->matrix = task;
     119        // We need to distinguish the values forbidden by the user
     120        // from the values forbidden by the algorithm.
     121        // So we replace user's infinities by the maximum available double value.
     122        normalize(step->matrix);
     123#ifdef DEBUG
     124        qDebug() << step->matrix;
     125#endif // DEBUG
    102126        step->price = align(step->matrix);
    103127        root = step;
    … …  
    108132double check = INFINITY;
    109133        while (this->route.size() < nCities) {
    110 //              forbidden.clear();
    111134                step->alts = findCandidate(step->matrix,nRow,nCol);
     135
    112136                while (hasSubCycles(nRow,nCol)) {
    113 //                      forbidden[nRow] = nCol;
     137#ifdef DEBUG
     138                        qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
     139#endif // DEBUG
    114140                        step->matrix[nRow][nCol] = INFINITY;
    115141                        step->price += align(step->matrix);
    116142                        step->alts = findCandidate(step->matrix,nRow,nCol);
    117143                }
    118                 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
     144
     145#ifdef DEBUG
     146                qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
     147                qDebug() << "Alternate:" << step->alts;
     148                qDebug() << "Step price:" << step->price << endl;
     149#endif // DEBUG
     150
     151                locker.relock();
     152                if ((nRow == -1) || (nCol == -1) || canceled) {
    119153                        cleanup();
    120                         break;
    121                 }
     154                        return NULL;
     155                }
     156                locker.unlock();
    122157
    123158                // Route with (nRow,nCol) path
    … …  
    132167                }
    133168                right->price = step->price + align(right->matrix);
    134                 // Forbid selected route to exclude its reuse in next steps.
     169                // Forbid the selected route to exclude its reuse in next steps.
    135170                right->matrix[nCol][nRow] = INFINITY;
    136171                right->matrix[nRow][nCol] = INFINITY;
    … …  
    148183                step->prNode = right;
    149184
     185                // This matrix is not used anymore. Restoring infinities back.
     186                denormalize(step->matrix);
     187
    150188                if (right->price <= left->price) {
    151189                        // Route with (nRow,nCol) path is cheaper
    152190                        step = right;
    153191                        this->route[nRow] = nCol;
    154                         pd.setValue(this->route.size());
     192                        emit routePartFound(this->route.size());
    155193                        if (firstStep) {
    156194                                check = left->price;
    … …  
    168206        }
    169207
    170         if (!root && !pd.wasCanceled()) {
    171                 pd.reset();
    172                 QMessageBox(QMessageBox::Warning,tr("Solution Result"),tr("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
    173         }
    174 
    175         qApp->processEvents();
    176 
    177         if (root) {
    178                 route = this->route;
    179                 mayNotBeOptimal = (check < step->price);
    180         }
     208        route = this->route;
     209        mayNotBeOptimal = (check < step->price);
     210
    181211        return root;
     212}
     213
     214/*!
     215 * \brief Indicates whether or not the solution process was canceled.
     216 * \return \c true if the solution process was canceled, otherwise \c false.
     217 */
     218bool CTSPSolver::wasCanceled() const
     219{
     220QMutexLocker locker(&mutex);
     221        return canceled;
     222}
     223
     224/*!
     225 * \brief Cancels the solution process.
     226 */
     227void CTSPSolver::cancel()
     228{
     229QMutexLocker locker(&mutex);
     230        canceled = true;
    182231}
    183232
    … …  
    198247                if (min > 0) {
    199248                        r += min;
    200                         subRow(matrix,k,min);
     249                        if (min < MAX_DOUBLE)
     250                                subRow(matrix,k,min);
    201251                }
    202252        }
    … …  
    205255                if (min > 0) {
    206256                        r += min;
    207                         subCol(matrix,k,min);
     257                        if (min < MAX_DOUBLE)
     258                                subCol(matrix,k,min);
    208259                }
    209260        }
    … …  
    211262}
    212263
    213 void CTSPSolver::cleanup()
    214 {
    215         QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
    216         route.clear();
    217         mayNotBeOptimal = false;
    218         if (root != NULL)
    219                 deleteTree(root);
    220         QApplication::restoreOverrideCursor();
    221 }
    222 
    223 void CTSPSolver::deleteTree(SStep *&root)
     264void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
    224265{
    225266        if (root == NULL)
    … …  
    228269SStep *parent;
    229270        forever {
     271                if (processEvents)
     272                        QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
    230273                if (step->plNode != NULL) {
    231274                        // We have left child node - going inside it
    … …  
    252295                }
    253296        }
     297}
     298
     299void CTSPSolver::denormalize(TMatrix &matrix) const
     300{
     301        for (int r = 0; r < nCities; r++)
     302                for (int c = 0; c < nCities; c++)
     303                        if ((r != c) && (matrix.at(r).at(c) == MAX_DOUBLE))
     304                                matrix[r][c] = INFINITY;
    254305}
    255306
    … …  
    287338                if ((k != exr) && (min > matrix.at(k).at(nCol)))
    288339                        min = matrix.at(k).at(nCol);
    289         return min == INFINITY ? 0 : min;
     340        return (min == INFINITY) ? 0 : min;
    290341}
    291342
    … …  
    293344{
    294345double min = INFINITY;
    295         for (int k = 0; k < nCities; k++)
     346        for (int k = 0; k < nCities; k++) {
    296347                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
    297348                        min = matrix.at(nRow).at(k);
    298         return min == INFINITY ? 0 : min;
     349        }
     350        return (min == INFINITY) ? 0 : min;
    299351}
    300352
    … …  
    313365}
    314366
     367void CTSPSolver::normalize(TMatrix &matrix) const
     368{
     369        for (int r = 0; r < nCities; r++)
     370                for (int c = 0; c < nCities; c++)
     371                        if ((r != c) && (matrix.at(r).at(c) == INFINITY))
     372                                matrix[r][c] = MAX_DOUBLE;
     373}
     374
    315375void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
    316376{
    … …  
    327387}
    328388
     389#ifdef DEBUG
    329390QDebug operator<<(QDebug dbg, const TMatrix &matrix)
    330391{
    331392        for (int r = 0; r < matrix.count(); r++) {
    332393                for (int c = 0; c < matrix.at(r).count(); c++)
    333                         dbg.space() << matrix.at(r).at(c);
     394                        dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
    334395                dbg << endl;
    335396        }
    336397        return dbg;
    337398}
     399
     400QDebug operator<<(QDebug dbg, const SCandidate &cand)
     401{
     402        dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
     403        return dbg;
     404}
     405#endif // DEBUG
Note: See TracChangeset for help on using the changeset viewer.