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

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:

• trunk/src/tspsolver.cpp (modified) (6 diffs)

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;
+}