- Main Page
- Classes
- Files

- File List

# OptFrame/Util/NSSeqTSPSwap.hpp

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

All Classes Functions