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


Ignore:
Timestamp:
Jul 31, 2009, 8:23:07 PM (15 years ago)
Author:
laleppa
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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/tspsolver.cpp

    r17 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
     
    2626
    2727CTSPSolver::CTSPSolver()
    28 {
    29 }
    30 
    31 double CTSPSolver::findMinInRow(int nRow, tMatrix matrix)
     28        : nCities(0)
     29{
     30}
     31
     32void CTSPSolver::cleanup()
     33{
     34        route.clear();
     35}
     36
     37double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
    3238{
    3339double min = INFINITY;
    3440        for (int k = 0; k < nCities; k++)
    35                 if (min > matrix[nRow][k])
     41                if (((k != exc)) && (min > matrix[nRow][k]))
    3642                        min = matrix[nRow][k];
    3743        return min == INFINITY ? 0 : min;
    3844}
    3945
    40 double CTSPSolver::findMinInCol(int nCol, tMatrix matrix)
     46double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
    4147{
    4248double min = INFINITY;
    4349        for (int k = 0; k < nCities; k++)
    44                 if (min > matrix[k][nCol])
     50                if ((k != exr) && (min > matrix[k][nCol]))
    4551                        min = matrix[k][nCol];
    4652        return min == INFINITY ? 0 : min;
    4753}
    4854
    49 sStep *CTSPSolver::solve(int numCities, tMatrix task)
     55void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
     56{
     57        for (int k = 0; k < nCities; k++)
     58                if (k != nRow)
     59                        matrix[nRow][k] -= val;
     60}
     61
     62void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
     63{
     64        for (int k = 0; k < nCities; k++)
     65                if (k != nCol)
     66                        matrix[k][nCol] -= val;
     67}
     68
     69double CTSPSolver::align(tMatrix &matrix)
     70{
     71double r = 0;
     72double min;
     73        for (int k = 0; k < nCities; k++) {
     74                min = findMinInRow(k,matrix);
     75                if (min > 0) {
     76                        r += min;
     77                        subRow(matrix,k,min);
     78                }
     79        }
     80        for (int k = 0; k < nCities; k++) {
     81                min = findMinInCol(k,matrix);
     82                if (min > 0) {
     83                        r += min;
     84                        subCol(matrix,k,min);
     85                }
     86        }
     87        return r;
     88}
     89
     90bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
     91{
     92        h = -1;
     93        nRow = -1;
     94        nCol = -1;
     95bool alts = false;
     96double sum;
     97        for (int r = 0; r < nCities; r++)
     98                for (int c = 0; c < nCities; c++)
     99                        if ((matrix[r][c] == 0) && !forbidden.values(r).contains(c)) {
     100                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
     101                                if (sum > h) {
     102                                        h = sum;
     103                                        nRow = r;
     104                                        nCol = c;
     105                                        alts = false;
     106                                } else if (sum == h)
     107                                        alts = true;
     108                        }
     109        return alts;
     110}
     111
     112bool CTSPSolver::hasSubCycles(int nRow, int nCol)
     113{
     114        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
     115                return false;
     116int i = nCol;
     117        while (true) {
     118                if ((i = route[i]) == nRow)
     119                        return true;
     120                if (!route.contains(i))
     121                        return false;
     122        }
     123        return false;
     124}
     125
     126// TODO: Comment the algorithm
     127sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
    50128{
    51129        if (numCities <= 1)
    52130                return NULL;
     131        cleanup();
    53132        nCities = numCities;
     133double s;
     134QProgressDialog pd(parent);
     135QProgressBar *pb = new QProgressBar(&pd);
     136        pb->setAlignment(Qt::AlignCenter);
     137        pb->setFormat(trUtf8("%v of %m parts found"));
     138        pd.setBar(pb);
     139        pd.setMaximum(nCities);
     140        pd.setMinimumDuration(1000);
     141        pd.setLabelText(trUtf8("Calculating optimal route..."));
     142        pd.setWindowTitle(trUtf8("Solution Progress"));
     143        pd.setWindowModality(Qt::ApplicationModal);
     144        pd.setValue(0);
     145
    54146sStep *step = new sStep();
    55147        step->matrix = task;
     148
     149        s = align(step->matrix);
     150        step->price = s;
    56151        root = step;
    57152
    58         return step;
    59 }
     153sStep *left, *right;
     154int nRow, nCol;
     155        while (route.size() < nCities) {
     156                forbidden.clear();
     157                step->alts = findCandidate(step->matrix,nRow,nCol,s);
     158                while (hasSubCycles(nRow,nCol)) {
     159                        forbidden[nRow] = nCol;
     160                        step->matrix[nRow][nCol] = INFINITY;
     161                        step->price += align(step->matrix);
     162                        step->alts = findCandidate(step->matrix,nRow,nCol,s);
     163                }
     164                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
     165                        root = NULL;
     166                        break;
     167                }
     168
     169                // Route with (nRow,nCol) path
     170                right = new sStep();
     171                right->matrix = step->matrix;
     172                for (int k = 0; k < nCities; k++) {
     173                        if (k != nCol)
     174                                right->matrix[nRow][k] = INFINITY;
     175                        if (k != nRow)
     176                                right->matrix[k][nCol] = INFINITY;
     177                }
     178                right->price = step->price + align(right->matrix);
     179                // Forbid selected route to exclude its reuse in next steps.
     180                right->matrix[nCol][nRow] = INFINITY;
     181                right->matrix[nRow][nCol] = INFINITY;
     182
     183                // Route without (nRow,nCol) path
     184                left = new sStep();
     185                left->matrix = step->matrix;
     186                left->matrix[nRow][nCol] = INFINITY;
     187                left->price = step->price + align(left->matrix);
     188
     189                step->candidate.nRow = nRow;
     190                step->candidate.nCol = nCol;
     191                step->plNode = left;
     192                step->prNode = right;
     193
     194                if (right->price <= left->price) {
     195                        // Route with (nRow,nCol) path is cheaper
     196                        step = right;
     197                        route[nRow] = nCol;
     198                        pd.setValue(route.size());
     199                } else {
     200                        // Route without (nRow,nCol) path is cheaper
     201                        step = left;
     202                        qApp->processEvents();
     203                }
     204        }
     205
     206        pd.reset();
     207        qApp->processEvents();
     208
     209        if (!root && !pd.wasCanceled()) {
     210                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("This task has no solution."),QMessageBox::Ok,parent).exec();
     211        }
     212
     213        return root;
     214}
Note: See TracChangeset for help on using the changeset viewer.