Changeset e664262f7d in tspsg for src


Ignore:
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:
3 edited

Legend:

Unmodified
Added
Removed
  • src/mainwindow.cpp

    r67e53c96d7 re664262f7d  
    130130void MainWindow::Solve()
    131131{
     132        // TODO: Task solving goes here :-)
     133tMatrix matrix;
     134double *row;
     135bool ok;
     136        for (int x = 0; x < spinCities->value(); x++) {
     137                row = new double[spinCities->value()];
     138                for (int y = 0; y < spinCities->value(); y++) {
     139                        if (x == y)
     140                                row[y] = infinity;
     141                        else {
     142                                row[y] = tableTask->item(x,y)->text().toDouble(&ok);
     143                                if (!ok) {
     144                                        QMessageBox(QMessageBox::Critical,trUtf8("Ошибка в данных"),QString(trUtf8("Ошибка в ячейке [Строка %1; Колонка %2]: Неверный формат данных.")).arg(x + 1).arg(y + 1),QMessageBox::Ok,this).exec();
     145                                        return;
     146                                } else if (row[y] < 0) {
     147                                        QMessageBox(QMessageBox::Critical,trUtf8("Ошибка в данных"),QString(trUtf8("Ошибка в ячейке [Строка %1; Колонка %2]: Значение не может быть меньше нуля.")).arg(x + 1).arg(y + 1),QMessageBox::Ok,this).exec();
     148                                        return;
     149                                }
     150                        }
     151                }
     152                matrix.append(row);
     153        }
     154CTSPSolver solver;
     155sStep *root = solver.solve(spinCities->value(),matrix);
     156        if (!root)
     157                QMessageBox(QMessageBox::Critical,trUtf8("Ошибка при решении"),trUtf8("Во время решения задачи возникла ошибка"),QMessageBox::Ok,this).exec();
    132158        // tabWidget->setCurrentIndex(1);
    133 CTSPSolver solver;
    134         solver.solve(spinCities->value(),NULL);
    135         // TODO: Task solving goes here :-)
    136159}
    137160
  • src/tspsolver.cpp

    r67e53c96d7 re664262f7d  
    2424#include "tspsolver.h"
    2525
    26 // Temoporary matrix for testing algorithm
    27 double testmatrix[] = {
    28                 infinity, 6, 7, 3, 4,
    29                 9, infinity, 6, 9, 10,
    30                 6, 9, infinity, 5, 3,
    31                 3, 10, 4, infinity, 2,
    32                 5, 1, 1, 9, infinity
    33         };
    34 
    35 
    3626CTSPSolver::CTSPSolver()
    3727{
    3828}
    3929
    40 sStep *CTSPSolver::solve(int numCities, double *task)
     30double CTSPSolver::findMinInRow(int nRow, tMatrix matrix)
     31{
     32double min = infinity;
     33        for (int k = 0; k < nCities; k++)
     34                if (min > matrix[nRow][k])
     35                        min = matrix[nRow][k];
     36        return min == infinity ? 0 : min;
     37}
     38
     39double CTSPSolver::findMinInCol(int nCol, tMatrix matrix)
     40{
     41double min = infinity;
     42        for (int k = 0; k < nCities; k++)
     43                if (min > matrix[k][nCol])
     44                        min = matrix[k][nCol];
     45        return min == infinity ? 0 : min;
     46}
     47
     48sStep *CTSPSolver::solve(int numCities, tMatrix task)
    4149{
    4250        if (numCities <= 1)
    4351                return NULL;
    44 // Temporary debug code :-)
    45         task = &testmatrix[0];
    46         numCities = 5;
    47 //*/
    48 sStep step;
    49         step.matrix = new double(numCities * numCities);
    50         memcpy(step.matrix,task,sizeof(double) * numCities * numCities);
     52        nCities = numCities;
     53sStep *step = new sStep();
     54        step->matrix = task;
     55        root = step;
    5156
    52         return NULL;
     57        return step;
    5358}
    5459
  • src/tspsolver.h

    r67e53c96d7 re664262f7d  
    2929const double infinity = 1.7E+308;
    3030
     31typedef QList<double *> tMatrix;
     32
    3133// Structure represent one step of solving
    3234// The tree of such elements will represent the solving process
    3335struct sStep {
    34         double *matrix;
     36        tMatrix matrix;
    3537        double price;
    3638        struct {unsigned int x; unsigned int y;} pos;
    37         sStep *pLeft, *pRight;
    38         sStep() { matrix = NULL; price = pos.x = pos.y = 0; pLeft = pRight = NULL;}
     39        sStep *plNode, *prNode;
     40        sStep() { price = pos.x = pos.y = 0; plNode = prNode = NULL; }
    3941};
    4042
     
    4446public:
    4547        CTSPSolver();
    46         sStep *solve(int, double *);
     48        sStep *solve(int, tMatrix);
     49private:
     50        int nCities;
     51        sStep *root;
     52        double findMinInRow(int, tMatrix);
     53        double findMinInCol(int, tMatrix);
    4754};
    4855
Note: See TracChangeset for help on using the changeset viewer.