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


Ignore:
Timestamp:
Sep 2, 2009, 2:37:39 AM (15 years ago)
Author:
laleppa
Message:

+ Warning about possible non-optimal result.

  • Resulting path is now sorted, always starts from City 1 and has "City 1 -> City n -> ... -> City 1" format.
  • Translations updated.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/tspsolver.cpp

    r55 r60  
    3333{
    3434        route.clear();
     35        mayNotBeOptimal = false;
    3536}
    3637
     
    8889}
    8990
    90 bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
    91 {
    92         h = -1;
     91bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol)
     92{
    9393        nRow = -1;
    9494        nCol = -1;
    9595bool alts = false;
     96double h = -1;
    9697double sum;
    9798        for (int r = 0; r < nCities; r++)
     
    132133        cleanup();
    133134        nCities = numCities;
    134 double s;
    135135QProgressDialog pd(parent);
    136136QProgressBar *pb = new QProgressBar(&pd);
     
    147147sStep *step = new sStep();
    148148        step->matrix = task;
    149 
    150         s = align(step->matrix);
    151         step->price = s;
     149        step->price = align(step->matrix);
    152150        root = step;
    153151
    154152sStep *left, *right;
    155153int nRow, nCol;
    156         while (route.size() < nCities) {
     154bool firstStep = true;
     155double check;
     156        while (this->route.size() < nCities) {
    157157//              forbidden.clear();
    158                 step->alts = findCandidate(step->matrix,nRow,nCol,s);
     158                step->alts = findCandidate(step->matrix,nRow,nCol);
    159159                while (hasSubCycles(nRow,nCol)) {
    160160//                      forbidden[nRow] = nCol;
    161161                        step->matrix[nRow][nCol] = INFINITY;
    162162                        step->price += align(step->matrix);
    163                         step->alts = findCandidate(step->matrix,nRow,nCol,s);
     163                        step->alts = findCandidate(step->matrix,nRow,nCol);
    164164                }
    165165                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
     
    196196                        // Route with (nRow,nCol) path is cheaper
    197197                        step = right;
    198                         route[nRow] = nCol;
    199                         pd.setValue(route.size());
     198                        this->route[nRow] = nCol;
     199                        pd.setValue(this->route.size());
     200                        if (firstStep) {
     201                                check = left->price;
     202                                firstStep = false;
     203                        }
    200204                } else {
    201205                        // Route without (nRow,nCol) path is cheaper
    202206                        step = left;
    203207                        qApp->processEvents();
     208                        if (firstStep) {
     209                                check = right->price;
     210                                firstStep = false;
     211                        }
    204212                }
    205213        }
     
    212220        qApp->processEvents();
    213221
     222        if (root) {
     223                route = this->route;
     224                mayNotBeOptimal = (check < step->price);
     225        }
    214226        return root;
    215227}
     228
     229QString CTSPSolver::getSortedPath() const
     230{
     231        if (!root || route.isEmpty() || (route.size() != nCities))
     232                return QString();
     233
     234int i = 0; // We start from City 1
     235QString path = trUtf8("City %1").arg(1) + " -> ";
     236        while ((i = route[i]) != 0) {
     237                path += trUtf8("City %1").arg(i + 1) + " -> ";
     238        }
     239        // And finish in City 1, too
     240        path += trUtf8("City %1").arg(1);
     241
     242        return path;
     243}
     244
     245bool CTSPSolver::isOptimal() const
     246{
     247        return !mayNotBeOptimal;
     248}
Note: See TracChangeset for help on using the changeset viewer.