Changeset 430bd7f7e9 in tspsg for src/tspsolver.cpp

Timestamp:

Jul 31, 2009, 8:23:07 PM (15 years ago)

Author:

Oleksii Serdiuk

Branches:

0.1.3.145-beta1-symbian, 0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme

Children:

ec54b4490b

Parents:

b5c9bcb585

Message:

+ Finished solving algorithm (needs thorough testing).
+ Solution can be saved to HTML or OpenDocument? format.
+ Added VERSIONINFO resource for windows builds.

• Updated translations to have unified terminology everywhere.

NB: This will be the first public alpha build.

File:

• src/tspsolver.cpp (modified) (2 diffs)

src/tspsolver.cpp

@@ -1 +1 @@
 /*
- *  TSPSG - TSP Solver and Generator
+ *  TSPSG: TSP Solver and Generator
  *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
  *
@@ -26 +26 @@
 
 CTSPSolver::CTSPSolver()
-{
-}
-
-double CTSPSolver::findMinInRow(int nRow, tMatrix matrix)
+        : nCities(0)
+{
+}
+
+void CTSPSolver::cleanup()
+{
+        route.clear();
+}
+
+double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
 {
 double min = INFINITY;
         for (int k = 0; k < nCities; k++)
-                if (min > matrix[nRow][k])
+                if (((k != exc)) && (min > matrix[nRow][k]))
                         min = matrix[nRow][k];
         return min == INFINITY ? 0 : min;
 }
 
-double CTSPSolver::findMinInCol(int nCol, tMatrix matrix)
+double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
 {
 double min = INFINITY;
         for (int k = 0; k < nCities; k++)
-                if (min > matrix[k][nCol])
+                if ((k != exr) && (min > matrix[k][nCol]))
                         min = matrix[k][nCol];
         return min == INFINITY ? 0 : min;
 }
 
-sStep *CTSPSolver::solve(int numCities, tMatrix task)
+void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
+{
+        for (int k = 0; k < nCities; k++)
+                if (k != nRow)
+                        matrix[nRow][k] -= val;
+}
+
+void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
+{
+        for (int k = 0; k < nCities; k++)
+                if (k != nCol)
+                        matrix[k][nCol] -= val;
+}
+
+double CTSPSolver::align(tMatrix &matrix)
+{
+double r = 0;
+double min;
+        for (int k = 0; k < nCities; k++) {
+                min = findMinInRow(k,matrix);
+                if (min > 0) {
+                        r += min;
+                        subRow(matrix,k,min);
+                }
+        }
+        for (int k = 0; k < nCities; k++) {
+                min = findMinInCol(k,matrix);
+                if (min > 0) {
+                        r += min;
+                        subCol(matrix,k,min);
+                }
+        }
+        return r;
+}
+
+bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
+{
+        h = -1;
+        nRow = -1;
+        nCol = -1;
+bool alts = false;
+double sum;
+        for (int r = 0; r < nCities; r++)
+                for (int c = 0; c < nCities; c++)
+                        if ((matrix[r][c] == 0) && !forbidden.values(r).contains(c)) {
+                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
+                                if (sum > h) {
+                                        h = sum;
+                                        nRow = r;
+                                        nCol = c;
+                                        alts = false;
+                                } else if (sum == h)
+                                        alts = true;
+                        }
+        return alts;
+}
+
+bool CTSPSolver::hasSubCycles(int nRow, int nCol)
+{
+        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
+                return false;
+int i = nCol;
+        while (true) {
+                if ((i = route[i]) == nRow)
+                        return true;
+                if (!route.contains(i))
+                        return false;
+        }
+        return false;
+}
+
+// TODO: Comment the algorithm
+sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
 {
         if (numCities <= 1)
                 return NULL;
+        cleanup();
         nCities = numCities;
+double s;
+QProgressDialog pd(parent);
+QProgressBar *pb = new QProgressBar(&pd);
+        pb->setAlignment(Qt::AlignCenter);
+        pb->setFormat(trUtf8("%v of %m parts found"));
+        pd.setBar(pb);
+        pd.setMaximum(nCities);
+        pd.setMinimumDuration(1000);
+        pd.setLabelText(trUtf8("Calculating optimal route..."));
+        pd.setWindowTitle(trUtf8("Solution Progress"));
+        pd.setWindowModality(Qt::ApplicationModal);
+        pd.setValue(0);
+
 sStep *step = new sStep();
         step->matrix = task;
+
+        s = align(step->matrix);
+        step->price = s;
         root = step;
 
-        return step;
-}
+sStep *left, *right;
+int nRow, nCol;
+        while (route.size() < nCities) {
+                forbidden.clear();
+                step->alts = findCandidate(step->matrix,nRow,nCol,s);
+                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);
+                }
+                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
+                        root = NULL;
+                        break;
+                }
+
+                // Route with (nRow,nCol) path
+                right = new sStep();
+                right->matrix = step->matrix;
+                for (int k = 0; k < nCities; k++) {
+                        if (k != nCol)
+                                right->matrix[nRow][k] = INFINITY;
+                        if (k != nRow)
+                                right->matrix[k][nCol] = INFINITY;
+                }
+                right->price = step->price + align(right->matrix);
+                // Forbid selected route to exclude its reuse in next steps.
+                right->matrix[nCol][nRow] = INFINITY;
+                right->matrix[nRow][nCol] = INFINITY;
+
+                // Route without (nRow,nCol) path
+                left = new sStep();
+                left->matrix = step->matrix;
+                left->matrix[nRow][nCol] = INFINITY;
+                left->price = step->price + align(left->matrix);
+
+                step->candidate.nRow = nRow;
+                step->candidate.nCol = nCol;
+                step->plNode = left;
+                step->prNode = right;
+
+                if (right->price <= left->price) {
+                        // Route with (nRow,nCol) path is cheaper
+                        step = right;
+                        route[nRow] = nCol;
+                        pd.setValue(route.size());
+                } else {
+                        // Route without (nRow,nCol) path is cheaper
+                        step = left;
+                        qApp->processEvents();
+                }
+        }
+
+        pd.reset();
+        qApp->processEvents();
+
+        if (!root && !pd.wasCanceled()) {
+                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("This task has no solution."),QMessageBox::Ok,parent).exec();
+        }
+
+        return root;
+}