- Main Page
- Classes
- Files

- File List

# OptFrame/Examples/EternityII/InitialSolutionGreedy.hpp

    00001 #ifndef EtII_INITIALSOLUTION_Greedy_HPP_
    00002 #define EtII_INITIALSOLUTION_Greedy_HPP_
    00003
    00004 #include "../../../OptFrame/InitialSolution.h"
    00005 #include "../../../OptFrame/Util/TestSolution.hpp"
    00006 #include "../../RandGen.hpp"
    00007
    00008 #include "ProblemInstance.hpp"
    00009
    00010 #include "Representation.h"
    00011 #include "Solution.h"
    00012
    00013 #include "Evaluator.hpp"
    00014
    00015 #include <list>
    00016
    00017 #include <algorithm>
    00018 #include <stdlib.h>
    00019
    00020 using namespace std;
    00021
    00022 class EtIIInitialSolutionGreedy: public InitialSolution<RepEtII>
    00023 {
    00024 private:
    00025         EtIIProblemInstance& pEtII;
    00026         RandGen& rg;
    00027
    00028 public:
    00029
    00030         EtIIInitialSolutionGreedy(EtIIProblemInstance& _pEtII,RandGen& _rg) : // If necessary, add more parameters
    00031                 pEtII(_pEtII), rg(_rg)
    00032         {
    00033         }
    00034
    00035         SolutionEtII& generateSolution()
    00036         {
    00037                 RepEtII* tab = new RepEtII(pEtII.height, pEtII.width);
    00038
    00039                 vector<Piece> corner_pieces;
    00040                 vector<Piece> side_pieces;
    00041                 vector<Piece> center_pieces;
    00042
    00043                 for (int i = 0; i < pEtII.pieces.size(); i++)
    00044                 {
    00045                         int zeros = 0;
    00046
    00047                         if (pEtII.pieces[i].down == 0)
    00048                                 zeros++;
    00049                         if (pEtII.pieces[i].left == 0)
    00050                                 zeros++;
    00051                         if (pEtII.pieces[i].up == 0)
    00052                                 zeros++;
    00053                         if (pEtII.pieces[i].right == 0)
    00054                                 zeros++;
    00055
    00056                         if (zeros == 2)
    00057                                 corner_pieces.push_back(pEtII.pieces[i]);
    00058                         if (zeros == 1)
    00059                                 side_pieces.push_back(pEtII.pieces[i]);
    00060                         if (zeros == 0)
    00061                                 center_pieces.push_back(pEtII.pieces[i]);
    00062                 }
    00063
    00064                 // shuffle elements
    00065                 rg.shuffle(corner_pieces);
    00066                 rg.shuffle(side_pieces);
    00067                 rg.shuffle(center_pieces);
    00068
    00069                 int x;
    00070                 Piece p;
    00071
    00072                 // random one piece for left-upper corner
    00073                 x = rg.rand(corner_pieces.size());
    00074                 p = corner_pieces[x];
    00075                 corner_pieces.erase(corner_pieces.begin() + x);
    00076
    00077                 while ((p.left != 0) || (p.up != 0))
    00078                         p.rotate();
    00079
    00080                 (*tab)(0, 0) = p;
    00081
    00082                 // random one piece for right-upper corner
    00083                 x = rg.rand(corner_pieces.size());
    00084                 p = corner_pieces[x];
    00085                 corner_pieces.erase(corner_pieces.begin() + x);
    00086
    00087                 while ((p.right != 0) || (p.up != 0))
    00088                         p.rotate();
    00089
    00090                 (*tab)(0, tab->getCols() - 1) = p;
    00091
    00092                 // random one piece for right-lower corner
    00093                 x = rg.rand(corner_pieces.size());
    00094                 p = corner_pieces[x];
    00095                 corner_pieces.erase(corner_pieces.begin() + x);
    00096
    00097                 while ((p.right != 0) || (p.down != 0))
    00098                         p.rotate();
    00099
    00100                 (*tab)(tab->getRows() - 1, tab->getCols() - 1) = p;
    00101
    00102                 // random one piece for left-lower corner
    00103                 x = rg.rand(corner_pieces.size());
    00104                 p = corner_pieces[x];
    00105                 corner_pieces.erase(corner_pieces.begin() + x);
    00106
    00107                 while ((p.left != 0) || (p.down != 0))
    00108                         p.rotate();
    00109
    00110                 (*tab)(tab->getRows() - 1, 0) = p;
    00111
    00112                 // choose the pieces for upper-bottom sides
    00113                 for (int i = 1; i < tab->getCols() - 1; i++)
    00114                 {
    00115                         // top
    00116                         int max = 0;
    00117                         int best = 0;
    00118                         for (int j = 0; j < side_pieces.size(); j++)
    00119                         {
    00120                                 p = side_pieces[j];
    00121
    00122                                 while (p.up != 0)
    00123                                         p.rotate();
    00124
    00125                                 int f = 0;
    00126                                 if (p.left == (*tab)(0, i - 1).right)
    00127                                 {
    00128                                         f++;
    00129                                         // best found!
    00130                                         max = f;
    00131                                         best = j;
    00132                                         break;
    00133                                 }
    00134                         }
    00135
    00136                         p = side_pieces[best];
    00137                         side_pieces.erase(side_pieces.begin() + best);
    00138
    00139                         while (p.up != 0)
    00140                                 p.rotate();
    00141                         (*tab)(0, i) = p;
    00142
    00143                         // bottom
    00144                         max = 0;
    00145                         best = 0;
    00146                         for (int j = 0; j < side_pieces.size(); j++)
    00147                         {
    00148                                 p = side_pieces[j];
    00149
    00150                                 while (p.down != 0)
    00151                                         p.rotate();
    00152
    00153                                 int f = 0;
    00154                                 if (p.left == (*tab)(tab->getRows() - 1, i - 1).right)
    00155                                 {
    00156                                         f++;
    00157                                         // best found!
    00158                                         max = f;
    00159                                         best = j;
    00160                                         break;
    00161                                 }
    00162                         }
    00163
    00164                         p = side_pieces[best];
    00165                         side_pieces.erase(side_pieces.begin() + best);
    00166
    00167                         while (p.down != 0)
    00168                                 p.rotate();
    00169                         (*tab)(tab->getRows() - 1, i) = p;
    00170                 }
    00171
    00172                 // random the pieces for left-right sides
    00173                 for (int i = 1; i < tab->getRows() - 1; i++)
    00174                 {
    00175                         // left
    00176                         int max = 0;
    00177                         int best = 0;
    00178                         for (int j = 0; j < side_pieces.size(); j++)
    00179                         {
    00180                                 p = side_pieces[j];
    00181
    00182                                 while (p.left != 0)
    00183                                         p.rotate();
    00184
    00185                                 int f = 0;
    00186                                 if (p.up == (*tab)(i - 1, 0).down)
    00187                                 {
    00188                                         f++;
    00189                                         // best found!
    00190                                         max = f;
    00191                                         best = j;
    00192                                         break;
    00193                                 }
    00194                         }
    00195
    00196                         p = side_pieces[best];
    00197                         side_pieces.erase(side_pieces.begin() + best);
    00198
    00199                         while (p.left != 0)
    00200                                 p.rotate();
    00201                         (*tab)(i, 0) = p;
    00202
    00203                         // right
    00204                         max = 0;
    00205                         best = 0;
    00206                         for (int j = 0; j < side_pieces.size(); j++)
    00207                         {
    00208                                 p = side_pieces[j];
    00209
    00210                                 while (p.right != 0)
    00211                                         p.rotate();
    00212
    00213                                 int f = 0;
    00214                                 if (p.up == (*tab)(i - 1, tab->getCols() - 1).down)
    00215                                 {
    00216                                         f++;
    00217                                         // best found!
    00218                                         max = f;
    00219                                         best = j;
    00220                                         break;
    00221                                 }
    00222                         }
    00223
    00224                         p = side_pieces[best];
    00225                         side_pieces.erase(side_pieces.begin() + best);
    00226
    00227                         while (p.right != 0)
    00228                                 p.rotate();
    00229                         (*tab)(i, tab->getCols() - 1) = p;
    00230                 }
    00231
    00232                 // choose the center pieces
    00233                 for (int i = 1; i < tab->getRows() - 1; i++)
    00234                         for (int j = 1; j < tab->getCols() - 1; j++)
    00235                         {
    00236                                 int max = -1;
    00237                                 int best_k = -1;
    00238                                 int best_r = -1;
    00239
    00240                                 for (int k = 0; k < center_pieces.size(); k++)
    00241                                 {
    00242                                         p = center_pieces[k];
    00243
    00244                                         for (int r = 0; r < 4; r++)
    00245                                         {
    00246                                                 int f = 0;
    00247                                                 if (p.left == (*tab)(i, j - 1).right)
    00248                                                         f++;
    00249                                                 if (p.up == (*tab)(i - 1, j).down)
    00250                                                         f++;
    00251
    00252                                                 if (f > max)
    00253                                                 {
    00254                                                         max = f;
    00255                                                         best_k = k;
    00256                                                         best_r = r;
    00257                                                 }
    00258
    00259                                                 p.rotate();
    00260                                         }
    00261
    00262                                         // last rotation
    00263                                         p.rotate();
    00264
    00265                                         if (max == 2) // best piece
    00266                                                 break;
    00267                                 }
    00268
    00269                                 p = center_pieces[best_k];
    00270                                 center_pieces.erase(center_pieces.begin() + best_k);
    00271
    00272                                 for (int r = 0; r < best_r; r++)
    00273                                         p.rotate();
    00274
    00275                                 (*tab)(i, j) = p;
    00276                         }
    00277
    00278                 if (corner_pieces.size() > 0 || side_pieces.size() > 0 || center_pieces.size() > 0)
    00279                 {
    00280                         cout << "Warning: construction problem!" << endl;
    00281                 }
    00282
    00283                 return *new TestSolution<RepEtII> (*tab);
    00284
    00285         }
    00286
    00287 };
    00288
    00289 #endif /*EtII_INITIALSOLUTION_Greedy_HPP_*/

All Classes Functions