- Main Page
- Classes
- Files

- File List

# OptFrame/Util/NSSeqTSP2Opt.hpp

    00001 #ifndef OPTFRAME_NSSEQTSP2OPT_HPP_
    00002 #define OPTFRAME_NSSEQTSP2OPT_HPP_
    00003 /*
    00004  Classical Problem: Traveling Salesman Problem
    00005
    00006  The Neighborhood Structure 2-opt has proposed by Cross (1958)
    00007  Croes G., A method for solving traveling salesman problems. Operations Research 6 (1958), pp. 791–812
    00008
    00009  2-Opt is aplied for any problem that representation is like a vector<T>, where T is the type of the vector.
    00010
    00011  e.g: vector<T> where type of T is int
    00012  s means Solution
    00013
    00014  initial s: 1 2 3 4 5 6 7 8
    00015
    00016  s' after apply MoveTSP2Opt(2,5) in s
    00017
    00018  s': 1 2 5 4 3 6 7 8
    00019
    00020  s" after apply MoveTSP2Opt(3,8) in s'
    00021
    00022  s": 1 2 5 8 7 6 3 4
    00023
    00024  */
    00025
    00026 // Framework includes
    00027 #include "../Move.hpp"
    00028 #include "../NSSeq.hpp"
    00029
    00030 using namespace std;
    00031
    00032 // Working structure: vector<T>
    00033
    00034 template<class T, class M = OPTFRAME_DEFAULT_MEMORY>
    00035 class MoveTSP2Opt: public Move<vector<T> , M>
    00036 {
    00037         typedef vector<T> Route;
    00038
    00039 protected:
    00040         int p1, p2; // position 1 and position 2, respectively
    00041
    00042 public:
    00043
    00044         MoveTSP2Opt(int _p1, int _p2) :
    00045                 p1(_p1), p2(_p2)
    00046         {
    00047         }
    00048
    00049         virtual ~MoveTSP2Opt()
    00050         {
    00051         }
    00052
    00053         int get_p1()
    00054         {
    00055                 return p1;
    00056         }
    00057
    00058         int get_p2()
    00059         {
    00060                 return p2;
    00061         }
    00062
    00063         bool canBeApplied(const Route& rep)
    00064         {
    00065                 bool all_positive = (p1 >= 0) && (p2 >= 0);
    00066                 return all_positive && (rep.size() >= 2);
    00067         }
    00068
    00069         Move<Route, M>& apply(Route& rep)
    00070         {
    00071
    00072                 reverse(rep.begin() + p1, rep.begin() + p2);
    00073
    00074                 // r1->r1, r2->r2, e1->i1, e2->i2, n1->n2, n2->n1, i1->e1, i2->e2
    00075                 return *new MoveTSP2Opt(p1, p2);
    00076         }
    00077
    00078         virtual bool operator==(const Move<Route, M>& _m) const
    00079         {
    00080                 const MoveTSP2Opt& m1 = (const MoveTSP2Opt&) _m;
    00081                 return ((m1.p1 == p1) && (m1.p2 == p2));
    00082         }
    00083
    00084         void print()
    00085         {
    00086                 cout << "MoveTSP2Opt( ";
    00087                 cout << " edge " << p1 << " <=>  edge " << p2 << " )";
    00088                 cout << endl;
    00089         }
    00090 };
    00091
    00092 template<class T, class M = OPTFRAME_DEFAULT_MEMORY, class MOVE = MoveTSP2Opt<T, M> >
    00093 class NSIteratorTSP2Opt: public NSIterator<vector<T> , M>
    00094 {
    00095         typedef vector<T> Route;
    00096
    00097 private:
    00098
    00099         MOVE* m;
    00100         int p1, p2; // position 1 and position 2, respectively
    00101         const Route& r;
    00102
    00103 public:
    00104
    00105         NSIteratorTSP2Opt(const Route& _r) :
    00106                 r(_r)
    00107         {
    00108                 m = NULL;
    00109         }
    00110
    00111         virtual ~NSIteratorTSP2Opt()
    00112         {
    00113         }
    00114
    00115         void first()
    00116         {
    00117                 if (r.size() >= 2)
    00118                 {
    00119                         p1 = 0;
    00120                         p2 = 2;
    00121                         m = new MoveTSP2Opt<T, M> (p1, p2);
    00122                 }
    00123                 else
    00124                         m = NULL;
    00125         }
    00126
    00127         void next()
    00128         {
    00129                 if (!((p1 == r.size() - 2) && (p2 == r.size())))
    00130                 {
    00131                         if (p2 != r.size())
    00132                         {
    00133                                 p2++;
    00134                         }
    00135                         else
    00136                         {
    00137                                 p1++;
    00138                                 p2 = p1 + 2;
    00139                         }
    00140
    00141                         m = new MoveTSP2Opt<T, M> (p1, p2);
    00142                 }
    00143                 else
    00144                         m = NULL;
    00145         }
    00146
    00147         bool isDone()
    00148         {
    00149                 return m == NULL;
    00150         }
    00151
    00152         Move<Route, M>& current()
    00153         {
    00154                 if (isDone())
    00155                 {
    00156                         cout << "There isnt any current element!" << endl;
    00157                         cout << "NSSeqRouteShift. Aborting." << endl;
    00158                         exit(1);
    00159                 }
    00160
    00161                 return *m;
    00162         }
    00163 };
    00164
    00165 template<class T, class M = OPTFRAME_DEFAULT_MEMORY, class MOVE = MoveTSP2Opt<T, M> >
    00166 class NSSeqTSP2Opt: public NSSeq<vector<T> , M>
    00167 {
    00168         typedef vector<T> Route;
    00169
    00170 private:
    00171
    00172 public:
    00173
    00174         NSSeqTSP2Opt()
    00175         {
    00176         }
    00177
    00178         virtual ~NSSeqTSP2Opt()
    00179         {
    00180         }
    00181
    00182         Move<Route, M>& move(const Route& rep)
    00183         {
    00184                 if (rep.size() < 2)
    00185                         return *new MOVE(-1, -1);
    00186
    00187                 int p1 = rand() % (rep.size() + 1);
    00188
    00189                 int p2;
    00190
    00191                 do
    00192                 {
    00193                         p2 = rand() % (rep.size() + 1);
    00194                 } while (abs(p1 - p2) < 2);
    00195
    00196                 // create 2-opt(p1,p2) move
    00197                 return *new MOVE(p1, p2);
    00198         }
    00199
    00200         virtual NSIterator<Route, M>& getIterator(const Route& r)
    00201         {
    00202                 return *new NSIteratorTSP2Opt<T, M, MOVE> (r);
    00203         }
    00204
    00205         virtual void print()
    00206         {
    00207                 cout << "NSSeqTSP2Opt" << endl;
    00208         }
    00209 };
    00210
    00211 #endif /*OPTFRAME_NSSEQTSP2OPT_HPP_*/

All Classes Functions