Changeset e664262f7d in tspsg

Timestamp:

Oct 21, 2007, 3:07:21 PM (17 years ago)

Author:

Oleksii Serdiuk

Branches:

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

Children:

2f915f19f2

Parents:

67e53c96d7

Message:

Writing solving algorithm...

Location:

src

Files:

• mainwindow.cpp (modified) (1 diff)
• tspsolver.cpp (modified) (1 diff)
• tspsolver.h (modified) (2 diffs)

src/mainwindow.cpp

@@ -130 +130 @@
 void MainWindow::Solve()
 {
+        // TODO: Task solving goes here :-)
+tMatrix matrix;
+double *row;
+bool ok;
+        for (int x = 0; x < spinCities->value(); x++) {
+                row = new double[spinCities->value()];
+                for (int y = 0; y < spinCities->value(); y++) {
+                        if (x == y)
+                                row[y] = infinity;
+                        else {
+                                row[y] = tableTask->item(x,y)->text().toDouble(&ok);
+                                if (!ok) {
+                                        QMessageBox(QMessageBox::Critical,trUtf8("Ошибка в данных"),QString(trUtf8("Ошибка в ячейке [Строка %1; Колонка %2]: Неверный формат данных.")).arg(x + 1).arg(y + 1),QMessageBox::Ok,this).exec();
+                                        return;
+                                } else if (row[y] < 0) {
+                                        QMessageBox(QMessageBox::Critical,trUtf8("Ошибка в данных"),QString(trUtf8("Ошибка в ячейке [Строка %1; Колонка %2]: Значение не может быть меньше нуля.")).arg(x + 1).arg(y + 1),QMessageBox::Ok,this).exec();
+                                        return;
+                                }
+                        }
+                }
+                matrix.append(row);
+        }
+CTSPSolver solver;
+sStep *root = solver.solve(spinCities->value(),matrix);
+        if (!root)
+                QMessageBox(QMessageBox::Critical,trUtf8("Ошибка при решении"),trUtf8("Во время решения задачи возникла ошибка"),QMessageBox::Ok,this).exec();
         // tabWidget->setCurrentIndex(1);
-CTSPSolver solver;
-        solver.solve(spinCities->value(),NULL);
-        // TODO: Task solving goes here :-)
 }
 

src/tspsolver.cpp

@@ -24 +24 @@
 #include "tspsolver.h"
 
-// Temoporary matrix for testing algorithm
-double testmatrix[] = {
-                infinity, 6, 7, 3, 4,
-                9, infinity, 6, 9, 10,
-                6, 9, infinity, 5, 3,
-                3, 10, 4, infinity, 2,
-                5, 1, 1, 9, infinity
-        };
-
-
 CTSPSolver::CTSPSolver()
 {
 }
 
-sStep *CTSPSolver::solve(int numCities, double *task)
+double CTSPSolver::findMinInRow(int nRow, tMatrix matrix)
+{
+double min = infinity;
+        for (int k = 0; k < nCities; k++)
+                if (min > matrix[nRow][k])
+                        min = matrix[nRow][k];
+        return min == infinity ? 0 : min;
+}
+
+double CTSPSolver::findMinInCol(int nCol, tMatrix matrix)
+{
+double min = infinity;
+        for (int k = 0; k < nCities; k++)
+                if (min > matrix[k][nCol])
+                        min = matrix[k][nCol];
+        return min == infinity ? 0 : min;
+}
+
+sStep *CTSPSolver::solve(int numCities, tMatrix task)
 {
         if (numCities <= 1)
                 return NULL;
-// Temporary debug code :-)
-        task = &testmatrix[0];
-        numCities = 5;
-//*/
-sStep step;
-        step.matrix = new double(numCities * numCities);
-        memcpy(step.matrix,task,sizeof(double) * numCities * numCities);
+        nCities = numCities;
+sStep *step = new sStep();
+        step->matrix = task;
+        root = step;
 
-        return NULL;
+        return step;
 }
 

src/tspsolver.h

@@ -29 +29 @@
 const double infinity = 1.7E+308;
 
+typedef QList<double *> tMatrix;
+
 // Structure represent one step of solving
 // The tree of such elements will represent the solving process
 struct sStep {
-        double *matrix;
+        tMatrix matrix;
         double price;
         struct {unsigned int x; unsigned int y;} pos;
-        sStep *pLeft, *pRight;
-        sStep() { matrix = NULL; price = pos.x = pos.y = 0; pLeft = pRight = NULL;}
+        sStep *plNode, *prNode;
+        sStep() { price = pos.x = pos.y = 0; plNode = prNode = NULL; }
 };
 
@@ -44 +46 @@
 public:
         CTSPSolver();
-        sStep *solve(int, double *);
+        sStep *solve(int, tMatrix);
+private:
+        int nCities;
+        sStep *root;
+        double findMinInRow(int, tMatrix);
+        double findMinInCol(int, tMatrix);
 };