Changeset 60 in tspsg-svn for trunk/src

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:

• mainwindow.cpp (modified) (3 diffs)
• tspsolver.cpp (modified) (6 diffs)
• tspsolver.h (modified) (2 diffs)

trunk/src/mainwindow.cpp

@@ -457 +457 @@
 sStep *step = root;
         n = 1;
-QString path = "";
         while (n <= spinCities->value()) {
                 if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) {
@@ -467 +466 @@
                                 output.append("<p>&nbsp;</p>");
                         }
-                        path += QString(" (%1,%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1);
                 }
                 if (step->prNode->prNode != NULL)
@@ -476 +474 @@
                         break;
         }
-        output.append("<p>" + trUtf8("Optimal path:") + "</p>");
-        output.append("<p>&nbsp;&nbsp;" + path + "</p>");
+        if (solver.isOptimal())
+                output.append("<p>" + trUtf8("Optimal path:") + "</p>");
+        else
+                output.append("<p>" + trUtf8("Resulting path:") + "</p>");
+        output.append("<p>&nbsp;&nbsp;" + solver.getSortedPath() + "</p>");
         output.append("<p>" + trUtf8("The price is <b>%1</b> units.").arg(step->price) + "</p>");
+        if (!solver.isOptimal()) {
+                output.append("<p>&nbsp;</p>");
+                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>");
+        }
         solutionText->setHtml(output.join(""));
         solutionText->setDocumentTitle(trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()));

trunk/src/tspsolver.cpp

@@ -33 +33 @@
 {
         route.clear();
+        mayNotBeOptimal = false;
 }
 
@@ -88 +89 @@
 }
 
-bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
-{
-        h = -1;
+bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol)
+{
         nRow = -1;
         nCol = -1;
 bool alts = false;
+double h = -1;
 double sum;
         for (int r = 0; r < nCities; r++)
@@ -132 +133 @@
         cleanup();
         nCities = numCities;
-double s;
 QProgressDialog pd(parent);
 QProgressBar *pb = new QProgressBar(&pd);
@@ -147 +147 @@
 sStep *step = new sStep();
         step->matrix = task;
-
-        s = align(step->matrix);
-        step->price = s;
+        step->price = align(step->matrix);
         root = step;
 
 sStep *left, *right;
 int nRow, nCol;
-        while (route.size() < nCities) {
+bool firstStep = true;
+double check;
+        while (this->route.size() < nCities) {
 //              forbidden.clear();
-                step->alts = findCandidate(step->matrix,nRow,nCol,s);
+                step->alts = findCandidate(step->matrix,nRow,nCol);
                 while (hasSubCycles(nRow,nCol)) {
 //                      forbidden[nRow] = nCol;
                         step->matrix[nRow][nCol] = INFINITY;
                         step->price += align(step->matrix);
-                        step->alts = findCandidate(step->matrix,nRow,nCol,s);
+                        step->alts = findCandidate(step->matrix,nRow,nCol);
                 }
                 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
@@ -196 +196 @@
                         // Route with (nRow,nCol) path is cheaper
                         step = right;
-                        route[nRow] = nCol;
-                        pd.setValue(route.size());
+                        this->route[nRow] = nCol;
+                        pd.setValue(this->route.size());
+                        if (firstStep) {
+                                check = left->price;
+                                firstStep = false;
+                        }
                 } else {
                         // Route without (nRow,nCol) path is cheaper
                         step = left;
                         qApp->processEvents();
+                        if (firstStep) {
+                                check = right->price;
+                                firstStep = false;
+                        }
                 }
         }
@@ -212 +220 @@
         qApp->processEvents();
 
+        if (root) {
+                route = this->route;
+                mayNotBeOptimal = (check < step->price);
+        }
         return root;
 }
+
+QString CTSPSolver::getSortedPath() const
+{
+        if (!root || route.isEmpty() || (route.size() != nCities))
+                return QString();
+
+int i = 0; // We start from City 1
+QString path = trUtf8("City %1").arg(1) + " -> ";
+        while ((i = route[i]) != 0) {
+                path += trUtf8("City %1").arg(i + 1) + " -> ";
+        }
+        // And finish in City 1, too
+        path += trUtf8("City %1").arg(1);
+
+        return path;
+}
+
+bool CTSPSolver::isOptimal() const
+{
+        return !mayNotBeOptimal;
+}

trunk/src/tspsolver.h

@@ -47 +47 @@
 public:
         CTSPSolver();
+        QString getSortedPath() const;
+        bool isOptimal() const;
         sStep *solve(int, tMatrix, QWidget *parent = 0);
 
 private:
+        bool mayNotBeOptimal;
         int nCities;
         sStep *root;
@@ -56 +59 @@
         double align(tMatrix &);
         void cleanup();
-        bool findCandidate(tMatrix, int &, int &, double &);
+        bool findCandidate(tMatrix, int &, int &);
         double findMinInRow(int, tMatrix, int exc = -1);
         double findMinInCol(int, tMatrix, int exr = -1);