2_local_search_components.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
15 #ifndef PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP
16 #define PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP
17
19
20 namespace paal {
21 namespace local_search {
22
28 template <typename Element> struct Swap {
35  Swap(Element from, Element to) : m_from(from), m_to(to) {}
36
42  Element get_from() const { return m_from; }
43
49  Element get_to() const { return m_to; }
50
51  private:
52  Element m_from;
53  Element m_to;
54 };
55
59 struct make_swap {
68  template <typename Element>
69  Swap<Element> operator()(Element from, Element to) const {
70  return Swap<Element>(from, to);
71  }
72 };
73
79 template <typename Metric> class gain_two_opt {
80  public:
86  gain_two_opt(const Metric &m) : m_metric(m) {}
87
97  template <typename Solution, typename SolutionElement>
98  int operator()(const Solution &, const Swap<SolutionElement> &swap) {
99  auto from = swap.get_from();
100  auto to = swap.get_to();
101  return m_metric(from.first, from.second) +
102  m_metric(to.first, to.second) - m_metric(from.first, to.first) -
103  m_metric(from.second, to.second);
104  }
105
106  private:
107  const Metric &m_metric;
108 };
109
122  template <typename SolutionElement, typename Solution>
123  bool operator()(Solution &s, const Swap<SolutionElement> &swap) {
124  s.get_cycle().flip(swap.get_from().second, swap.get_to().first);
125  return true;
126  }
127 };
128
133
139  template <typename Solution> struct types_eval {
140  using SolutionIter = decltype(std::declval<Solution>().begin());
141  using Subset =
143  using Range = boost::iterator_range<Subset>;
144  };
145
146  public:
153  template <typename Solution>
155  Solution &solution) const->typename types_eval<Solution>::Range {
156  return data_structures::make_subsets_iterator_range<2>(
157  solution.begin(), solution.end(), make_swap{});
158  }
159 };
160
161 }
162 }
163
164 #endif // PAAL_2_LOCAL_SEARCH_COMPONENTS_HPP
Swap< Element > operator()(Element from, Element to) const
operator()
Swap(Element from, Element to)
constructor
Element get_to() const
getter for m_to
Iterator to all k-subsets of given collection.
int operator()(const Solution &, const Swap< SolutionElement > &swap)