Changeset 60 in tspsg-svn for trunk/src


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.
Location:
trunk/src
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/mainwindow.cpp

    r59 r60  
    457457sStep *step = root;
    458458        n = 1;
    459 QString path = "";
    460459        while (n <= spinCities->value()) {
    461460                if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) {
     
    467466                                output.append("<p>&nbsp;</p>");
    468467                        }
    469                         path += QString(" (%1,%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1);
    470468                }
    471469                if (step->prNode->prNode != NULL)
     
    476474                        break;
    477475        }
    478         output.append("<p>" + trUtf8("Optimal path:") + "</p>");
    479         output.append("<p>&nbsp;&nbsp;" + path + "</p>");
     476        if (solver.isOptimal())
     477                output.append("<p>" + trUtf8("Optimal path:") + "</p>");
     478        else
     479                output.append("<p>" + trUtf8("Resulting path:") + "</p>");
     480        output.append("<p>&nbsp;&nbsp;" + solver.getSortedPath() + "</p>");
    480481        output.append("<p>" + trUtf8("The price is <b>%1</b> units.").arg(step->price) + "</p>");
     482        if (!solver.isOptimal()) {
     483                output.append("<p>&nbsp;</p>");
     484                output.append("<p>" + trUtf8("<b>WARNING!!!</b><br>This result is a record, but it may not be optimal.<br>Iterations need to be continued to check whether this result is optimal or get an optimal one.") + "</p>");
     485        }
    481486        solutionText->setHtml(output.join(""));
    482487        solutionText->setDocumentTitle(trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()));
  • 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}
  • trunk/src/tspsolver.h

    r59 r60  
    4747public:
    4848        CTSPSolver();
     49        QString getSortedPath() const;
     50        bool isOptimal() const;
    4951        sStep *solve(int, tMatrix, QWidget *parent = 0);
    5052
    5153private:
     54        bool mayNotBeOptimal;
    5255        int nCities;
    5356        sStep *root;
     
    5659        double align(tMatrix &);
    5760        void cleanup();
    58         bool findCandidate(tMatrix, int &, int &, double &);
     61        bool findCandidate(tMatrix, int &, int &);
    5962        double findMinInRow(int, tMatrix, int exc = -1);
    6063        double findMinInCol(int, tMatrix, int exr = -1);
Note: See TracChangeset for help on using the changeset viewer.