Changeset 67 in tspsg-svn for trunk/src/tspsolver.cpp


Ignore:
Timestamp:
Oct 24, 2009, 3:37:48 PM (15 years ago)
Author:
laleppa
Message:
  • Finished documentation.
  • Sorted all functions in .cpp files according to order of their declaration in .h files.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/tspsolver.cpp

    r66 r67  
    3030}
    3131
    32 void CTSPSolver::cleanup()
    33 {
    34         route.clear();
    35         mayNotBeOptimal = false;
    36 }
    37 
    38 double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
    39 {
    40 double min = INFINITY;
    41         for (int k = 0; k < nCities; k++)
    42                 if (((k != exc)) && (min > matrix.at(nRow).at(k)))
    43                         min = matrix.at(nRow).at(k);
    44         return min == INFINITY ? 0 : min;
    45 }
    46 
    47 double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
    48 {
    49 double min = INFINITY;
    50         for (int k = 0; k < nCities; k++)
    51                 if ((k != exr) && (min > matrix.at(k).at(nCol)))
    52                         min = matrix.at(k).at(nCol);
    53         return min == INFINITY ? 0 : min;
    54 }
    55 
    56 void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
    57 {
    58         for (int k = 0; k < nCities; k++)
    59                 if (k != nRow)
    60                         matrix[nRow][k] -= val;
    61 }
    62 
    63 void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
    64 {
    65         for (int k = 0; k < nCities; k++)
    66                 if (k != nCol)
    67                         matrix[k][nCol] -= val;
    68 }
     32/*!
     33 * \brief Returns the sorted optimal path, starting from City 1.
     34 * \return A string, containing sorted optimal path.
     35 */
     36QString CTSPSolver::getSortedPath() const
     37{
     38        if (!root || route.isEmpty() || (route.size() != nCities))
     39                return QString();
     40
     41int i = 0; // We start from City 1
     42QString path = trUtf8("City %1").arg(1) + " -> ";
     43        while ((i = route[i]) != 0) {
     44                path += trUtf8("City %1").arg(i + 1) + " -> ";
     45        }
     46        // And finish in City 1, too
     47        path += trUtf8("City %1").arg(1);
     48
     49        return path;
     50}
     51
     52/*!
     53 * \brief Returns CTSPSolver's version ID.
     54 * \return A string: <b>\$Id$</b>.
     55 */
     56QString 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.
     66 *  In such cases this function returns \c false.
     67 */
     68bool CTSPSolver::isOptimal() const
     69{
     70        return !mayNotBeOptimal;
     71}
     72
     73/*!
     74 * \brief Solves the given task.
     75 * \param numCities Number of cities in the task.
     76 * \param task The matrix of city-to-city travel costs.
     77 * \param parent The parent widget for displaying messages and dialogs.
     78 * \return Pointer to the root of the solution tree.
     79 *
     80 * \todo TODO: Comment the algorithm.
     81 */
     82sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
     83{
     84        if (numCities <= 1)
     85                return NULL;
     86        cleanup();
     87        nCities = numCities;
     88QProgressDialog pd(parent);
     89QProgressBar *pb = new QProgressBar(&pd);
     90        pb->setAlignment(Qt::AlignCenter);
     91        pb->setFormat(trUtf8("%v of %m parts found"));
     92        pd.setBar(pb);
     93        pd.setMaximum(nCities);
     94        pd.setMinimumDuration(1000);
     95        pd.setLabelText(trUtf8("Calculating optimal route..."));
     96        pd.setWindowTitle(trUtf8("Solution Progress"));
     97        pd.setWindowModality(Qt::ApplicationModal);
     98        pd.setValue(0);
     99
     100sStep *step = new sStep();
     101        step->matrix = task;
     102        step->price = align(step->matrix);
     103        root = step;
     104
     105sStep *left, *right;
     106int nRow, nCol;
     107bool firstStep = true;
     108double check;
     109        while (this->route.size() < nCities) {
     110//              forbidden.clear();
     111                step->alts = findCandidate(step->matrix,nRow,nCol);
     112                while (hasSubCycles(nRow,nCol)) {
     113//                      forbidden[nRow] = nCol;
     114                        step->matrix[nRow][nCol] = INFINITY;
     115                        step->price += align(step->matrix);
     116                        step->alts = findCandidate(step->matrix,nRow,nCol);
     117                }
     118                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
     119                        root = NULL;
     120                        break;
     121                }
     122
     123                // Route with (nRow,nCol) path
     124                right = new sStep();
     125                right->matrix = step->matrix;
     126                for (int k = 0; k < nCities; k++) {
     127                        if (k != nCol)
     128                                right->matrix[nRow][k] = INFINITY;
     129                        if (k != nRow)
     130                                right->matrix[k][nCol] = INFINITY;
     131                }
     132                right->price = step->price + align(right->matrix);
     133                // Forbid selected route to exclude its reuse in next steps.
     134                right->matrix[nCol][nRow] = INFINITY;
     135                right->matrix[nRow][nCol] = INFINITY;
     136
     137                // Route without (nRow,nCol) path
     138                left = new sStep();
     139                left->matrix = step->matrix;
     140                left->matrix[nRow][nCol] = INFINITY;
     141                left->price = step->price + align(left->matrix);
     142
     143                step->candidate.nRow = nRow;
     144                step->candidate.nCol = nCol;
     145                step->plNode = left;
     146                step->prNode = right;
     147
     148                if (right->price <= left->price) {
     149                        // Route with (nRow,nCol) path is cheaper
     150                        step = right;
     151                        this->route[nRow] = nCol;
     152                        pd.setValue(this->route.size());
     153                        if (firstStep) {
     154                                check = left->price;
     155                                firstStep = false;
     156                        }
     157                } else {
     158                        // Route without (nRow,nCol) path is cheaper
     159                        step = left;
     160                        qApp->processEvents();
     161                        if (firstStep) {
     162                                check = right->price;
     163                                firstStep = false;
     164                        }
     165                }
     166        }
     167
     168        if (!root && !pd.wasCanceled()) {
     169                pd.reset();
     170                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
     171        }
     172
     173        qApp->processEvents();
     174
     175        if (root) {
     176                route = this->route;
     177                mayNotBeOptimal = (check < step->price);
     178        }
     179        return root;
     180}
     181
     182/* Privates **********************************************************/
    69183
    70184double CTSPSolver::align(tMatrix &matrix)
    … …  
    87201        }
    88202        return r;
     203}
     204
     205void CTSPSolver::cleanup()
     206{
     207        route.clear();
     208        mayNotBeOptimal = false;
    89209}
    90210
    … …  
    112232}
    113233
     234double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
     235{
     236double min = INFINITY;
     237        for (int k = 0; k < nCities; k++)
     238                if ((k != exr) && (min > matrix.at(k).at(nCol)))
     239                        min = matrix.at(k).at(nCol);
     240        return min == INFINITY ? 0 : min;
     241}
     242
     243double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
     244{
     245double min = INFINITY;
     246        for (int k = 0; k < nCities; k++)
     247                if (((k != exc)) && (min > matrix.at(nRow).at(k)))
     248                        min = matrix.at(nRow).at(k);
     249        return min == INFINITY ? 0 : min;
     250}
     251
    114252bool CTSPSolver::hasSubCycles(int nRow, int nCol)
    115253{
    … …  
    126264}
    127265
    128 /*!
    129  * \brief Solves the given task.
    130  * \param numCities Number of cities in the task.
    131  * \param task The matrix of city-to-city travel costs.
    132  * \param parent The parent widget for displaying messages and dialogs.
    133  * \return Pointer to the root of the solution tree.
    134  *
    135  * \todo TODO: Comment the algorithm.
    136  */
    137 sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
    138 {
    139         if (numCities <= 1)
    140                 return NULL;
    141         cleanup();
    142         nCities = numCities;
    143 QProgressDialog pd(parent);
    144 QProgressBar *pb = new QProgressBar(&pd);
    145         pb->setAlignment(Qt::AlignCenter);
    146         pb->setFormat(trUtf8("%v of %m parts found"));
    147         pd.setBar(pb);
    148         pd.setMaximum(nCities);
    149         pd.setMinimumDuration(1000);
    150         pd.setLabelText(trUtf8("Calculating optimal route..."));
    151         pd.setWindowTitle(trUtf8("Solution Progress"));
    152         pd.setWindowModality(Qt::ApplicationModal);
    153         pd.setValue(0);
    154 
    155 sStep *step = new sStep();
    156         step->matrix = task;
    157         step->price = align(step->matrix);
    158         root = step;
    159 
    160 sStep *left, *right;
    161 int nRow, nCol;
    162 bool firstStep = true;
    163 double check;
    164         while (this->route.size() < nCities) {
    165 //              forbidden.clear();
    166                 step->alts = findCandidate(step->matrix,nRow,nCol);
    167                 while (hasSubCycles(nRow,nCol)) {
    168 //                      forbidden[nRow] = nCol;
    169                         step->matrix[nRow][nCol] = INFINITY;
    170                         step->price += align(step->matrix);
    171                         step->alts = findCandidate(step->matrix,nRow,nCol);
    172                 }
    173                 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
    174                         root = NULL;
    175                         break;
    176                 }
    177 
    178                 // Route with (nRow,nCol) path
    179                 right = new sStep();
    180                 right->matrix = step->matrix;
    181                 for (int k = 0; k < nCities; k++) {
    182                         if (k != nCol)
    183                                 right->matrix[nRow][k] = INFINITY;
    184                         if (k != nRow)
    185                                 right->matrix[k][nCol] = INFINITY;
    186                 }
    187                 right->price = step->price + align(right->matrix);
    188                 // Forbid selected route to exclude its reuse in next steps.
    189                 right->matrix[nCol][nRow] = INFINITY;
    190                 right->matrix[nRow][nCol] = INFINITY;
    191 
    192                 // Route without (nRow,nCol) path
    193                 left = new sStep();
    194                 left->matrix = step->matrix;
    195                 left->matrix[nRow][nCol] = INFINITY;
    196                 left->price = step->price + align(left->matrix);
    197 
    198                 step->candidate.nRow = nRow;
    199                 step->candidate.nCol = nCol;
    200                 step->plNode = left;
    201                 step->prNode = right;
    202 
    203                 if (right->price <= left->price) {
    204                         // Route with (nRow,nCol) path is cheaper
    205                         step = right;
    206                         this->route[nRow] = nCol;
    207                         pd.setValue(this->route.size());
    208                         if (firstStep) {
    209                                 check = left->price;
    210                                 firstStep = false;
    211                         }
    212                 } else {
    213                         // Route without (nRow,nCol) path is cheaper
    214                         step = left;
    215                         qApp->processEvents();
    216                         if (firstStep) {
    217                                 check = right->price;
    218                                 firstStep = false;
    219                         }
    220                 }
    221         }
    222 
    223         if (!root && !pd.wasCanceled()) {
    224                 pd.reset();
    225                 QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec();
    226         }
    227 
    228         qApp->processEvents();
    229 
    230         if (root) {
    231                 route = this->route;
    232                 mayNotBeOptimal = (check < step->price);
    233         }
    234         return root;
    235 }
    236 
    237 /*!
    238  * \brief Returns the sorted optimal path, starting from City 1.
    239  * \return A string, containing sorted optimal path.
    240  */
    241 QString CTSPSolver::getSortedPath() const
    242 {
    243         if (!root || route.isEmpty() || (route.size() != nCities))
    244                 return QString();
    245 
    246 int i = 0; // We start from City 1
    247 QString path = trUtf8("City %1").arg(1) + " -> ";
    248         while ((i = route[i]) != 0) {
    249                 path += trUtf8("City %1").arg(i + 1) + " -> ";
    250         }
    251         // And finish in City 1, too
    252         path += trUtf8("City %1").arg(1);
    253 
    254         return path;
    255 }
    256 
    257 /*!
    258  * \brief Returns CTSPSolver's version ID.
    259  * \return A string: <b>\$Id$</b>.
    260  */
    261 QString CTSPSolver::getVersionId()
    262 {
    263         return QString("$Id$");
    264 }
    265 
    266 /*!
    267  * \brief Returns whether or not the solution is definitely optimal.
    268  * \return \c true if solution is definitely optimal, otherwise \c false.
    269  *
    270  *  The solution may need some further interations to determine whether it is optimal.
    271  *  In such cases this function returns \c false.
    272  */
    273 bool CTSPSolver::isOptimal() const
    274 {
    275         return !mayNotBeOptimal;
    276 }
     266void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
     267{
     268        for (int k = 0; k < nCities; k++)
     269                if (k != nCol)
     270                        matrix[k][nCol] -= val;
     271}
     272
     273void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
     274{
     275        for (int k = 0; k < nCities; k++)
     276                if (k != nRow)
     277                        matrix[nRow][k] -= val;
     278}
Note: See TracChangeset for help on using the changeset viewer.