COIN-OR::LEMON - Graph Library

source: lemon/lemon/insertion_tsp.h @ 1199:ae0b056593a7

Last change on this file since 1199:ae0b056593a7 was 1199:ae0b056593a7, checked in by Gabor Varga <f4c3@…>, 9 years ago

Heuristic algorithms for symmetric TSP (#386)

File size: 10.9 KB
Line 
1#ifndef LEMON_INSERTION_TSP_H
2#define LEMON_INSERTION_TSP_H
3
4#include <lemon/full_graph.h>
5#include <lemon/path.h>
6#include <lemon/maps.h>
7#include <lemon/random.h>
8#include <vector>
9
10namespace lemon {
11
12  namespace insertion_tsp_helper {
13 
14    template <class L>
15    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
16      return L(_path.begin(), _path.end());
17    };
18 
19    template <>
20    std::vector<FullGraph::Node> vectorConvert(
21        const std::vector<FullGraph::Node> &_path) {
22      return _path;
23    };
24   
25  };
26
27  template <typename CM>
28  class InsertionTsp {
29    private:
30      GRAPH_TYPEDEFS(FullGraph);
31
32    public:     
33      typedef CM CostMap;
34      typedef typename CM::Value Cost;
35     
36      InsertionTsp(const FullGraph &gr, const CostMap &cost) :
37            _gr(gr), _cost(cost) {}
38     
39      enum InsertionMethod {
40        INSERT_NEAREST,
41        INSERT_FARTHEST,
42        INSERT_CHEAPEST,
43        INSERT_RANDOM
44      };     
45     
46      Cost run(InsertionMethod method = INSERT_FARTHEST) {
47        switch (method) {
48          case INSERT_NEAREST:
49            start<InitTour<true>, NearestSelection, DefaultInsert>();
50            break;
51          case INSERT_FARTHEST:
52            start<InitTour<false>, FarthestSelection, DefaultInsert>();
53            break;
54          case INSERT_CHEAPEST:
55            start<InitTour<true>, CheapestSelection, CheapestInsert>();
56            break;
57          case INSERT_RANDOM:
58            start<InitTour<true>, RandomSelection, DefaultInsert>();
59            break;
60        }
61        return sum;
62      }
63
64      template <typename L>
65      void tourNodes(L &container) {
66        container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
67      }
68     
69      template <template <typename> class L>
70      L<Node> tourNodes() {
71        return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
72      }
73     
74      const std::vector<Node>& tourNodes() {
75        return nodesPath;
76      }
77     
78      Path<FullGraph> tour() {
79        Path<FullGraph> p;
80        if (nodesPath.size()<2)
81          return p;
82       
83        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
84          p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
85       
86        p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
87        return p;
88      }
89     
90      Cost tourCost() {
91        return sum;
92      }
93
94
95    private:
96
97      template <bool MIN>
98      class InitTour {
99        public:
100          InitTour(const FullGraph &gr, const CostMap &cost,
101                   std::vector<Node> &used, std::vector<Node> &notused,
102                   Cost &fullcost) :
103              _gr(gr), _cost(cost), _used(used), _notused(notused),
104              _fullcost(fullcost) {}
105
106          std::vector<Node> init() const {
107            Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
108            std::vector<Node> path;
109            path.push_back(_gr.u(min));
110            path.push_back(_gr.v(min));
111           
112            _used.clear();
113            _notused.clear();
114            for (NodeIt n(_gr); n!=INVALID; ++n) {
115              if (n != _gr.u(min) && n != _gr.v(min)) {
116                _notused.push_back(n);
117              }
118            }
119            _used.push_back(_gr.u(min));
120            _used.push_back(_gr.v(min));
121           
122            _fullcost = _cost[min]*2;
123            return path;
124          }
125
126        private:
127          const FullGraph &_gr;
128          const CostMap &_cost;
129          std::vector<Node> &_used;
130          std::vector<Node> &_notused;
131          Cost &_fullcost;
132      };
133
134      class NearestSelection {
135        public:
136          NearestSelection(const FullGraph &gr, const CostMap &cost,
137                           std::vector<Node> &used, std::vector<Node> &notused) :
138              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
139     
140          Node select() const {
141
142            Cost insert_val =
143              std::numeric_limits<Cost>::max();
144            int insert_node = -1;
145           
146            for (unsigned int i=0; i<_notused.size(); ++i) {
147              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
148              int min_node = 0;
149           
150              for (unsigned int j=1; j<_used.size(); ++j) {
151                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
152                    min_val = _cost[_gr.edge(_notused[i], _used[j])];
153                    min_node = j;
154                }
155              }
156             
157              if (insert_val > min_val) {
158                insert_val = min_val;
159                insert_node = i;
160              }
161            }
162           
163            Node n = _notused[insert_node];
164            _notused.erase(_notused.begin()+insert_node);
165           
166            return n;
167          }
168         
169        private:
170          const FullGraph &_gr;
171          const CostMap &_cost;
172          std::vector<Node> &_used;
173          std::vector<Node> &_notused;
174      };
175
176      class FarthestSelection {
177        public:
178          FarthestSelection(const FullGraph &gr, const CostMap &cost,
179                            std::vector<Node> &used, std::vector<Node> &notused) :
180              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
181     
182          Node select() const {
183
184            Cost insert_val =
185              std::numeric_limits<Cost>::min();
186            int insert_node = -1;
187           
188            for (unsigned int i=0; i<_notused.size(); ++i) {
189              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
190              int min_node = 0;
191             
192              for (unsigned int j=1; j<_used.size(); ++j) {
193                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
194                  min_val = _cost[_gr.edge(_notused[i], _used[j])];
195                  min_node = j;
196                }
197              }
198             
199              if (insert_val < min_val || insert_node == -1) {
200                insert_val = min_val;
201                insert_node = i;
202              }
203            }
204           
205            Node n = _notused[insert_node];
206            _notused.erase(_notused.begin()+insert_node);
207           
208            return n;
209          }
210         
211        private:
212          const FullGraph &_gr;
213          const CostMap &_cost;
214          std::vector<Node> &_used;
215          std::vector<Node> &_notused;
216      };
217
218
219      class CheapestSelection {
220        private:
221          Cost costDiff(Node u, Node v, Node w) const {
222            return
223              _cost[_gr.edge(u, w)] +
224              _cost[_gr.edge(v, w)] -
225              _cost[_gr.edge(u, v)];
226          }
227
228        public:
229          CheapestSelection(const FullGraph &gr, const CostMap &cost,
230                            std::vector<Node> &used, std::vector<Node> &notused) :
231              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
232       
233          Cost select() const {
234            int insert_notused = -1;
235            int best_insert_index = -1;
236            Cost insert_val =
237              std::numeric_limits<Cost>::max();
238           
239            for (unsigned int i=0; i<_notused.size(); ++i) {
240              int min = i;
241              int best_insert_tmp = 0;
242              Cost min_val =
243                costDiff(_used.front(), _used.back(), _notused[i]);
244             
245              for (unsigned int j=1; j<_used.size(); ++j) {
246                Cost tmp =
247                  costDiff(_used[j-1], _used[j], _notused[i]);
248
249                if (min_val > tmp) {
250                  min = i;
251                  min_val = tmp;
252                  best_insert_tmp = j;
253                }
254              }
255
256              if (insert_val > min_val) {
257                insert_notused = min;
258                insert_val = min_val;
259                best_insert_index = best_insert_tmp;
260              }
261            }
262
263            _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
264            _notused.erase(_notused.begin()+insert_notused);
265
266            return insert_val;
267          }
268         
269        private:
270          const FullGraph &_gr;
271          const CostMap &_cost;
272          std::vector<Node> &_used;
273          std::vector<Node> &_notused;
274      };
275
276      class RandomSelection {
277        public:
278          RandomSelection(const FullGraph &, const CostMap &,
279                            std::vector<Node> &, std::vector<Node> &notused) :
280                           _notused(notused) {
281            rnd.seedFromTime();
282          }
283         
284          Node select() const {
285            const int index = rnd[_notused.size()];
286            Node n = _notused[index];
287            _notused.erase(_notused.begin()+index);
288            return n;
289          }
290        private:
291          std::vector<Node> &_notused;
292      };
293
294
295      class DefaultInsert {
296        private:
297          Cost costDiff(Node u, Node v, Node w) const {
298            return
299              _cost[_gr.edge(u, w)] +
300              _cost[_gr.edge(v, w)] -
301              _cost[_gr.edge(u, v)];
302          }
303 
304        public:
305          DefaultInsert(const FullGraph &gr, const CostMap &cost,
306                        std::vector<Node> &path, Cost &fullcost) :
307            _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
308         
309          void insert(Node n) const {
310            int min = 0;
311            Cost min_val =
312              costDiff(_path.front(), _path.back(), n);
313           
314            for (unsigned int i=1; i<_path.size(); ++i) {
315              Cost tmp = costDiff(_path[i-1], _path[i], n);
316              if (tmp < min_val) {
317                min = i;
318                min_val = tmp;
319              }
320            }
321           
322            _path.insert(_path.begin()+min, n);
323            _fullcost += min_val;
324          }
325       
326        private:
327          const FullGraph &_gr;
328          const CostMap &_cost;
329          std::vector<Node> &_path;
330          Cost &_fullcost;
331      };
332 
333      class CheapestInsert {
334        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
335        public:
336          CheapestInsert(const FullGraph &, const CostMap &,
337                         std::vector<Node> &, Cost &fullcost) :
338            _fullcost(fullcost) {}
339         
340          void insert(Cost diff) const {
341            _fullcost += diff;
342          }
343
344        private:
345          Cost &_fullcost;
346      }; 
347     
348     
349      template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
350      void start() {
351        InitFunctor init(_gr, _cost, nodesPath, notused, sum);
352        SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
353        InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
354       
355        nodesPath = init.init();
356       
357        for (int i=0; i<_gr.nodeNum()-2; ++i) {
358          insertNode.insert(selectNode.select());
359        }
360       
361        sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
362        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
363          sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
364      }
365   
366      const FullGraph &_gr;
367      const CostMap &_cost;
368      std::vector<Node> notused;
369      std::vector<Node> nodesPath;
370      Cost sum;
371  };
372 
373}; // namespace lemon
374
375#endif
Note: See TracBrowser for help on using the repository browser.