# Changeset 1204:dff32ce3db71 in lemon

Ignore:
Timestamp:
01/09/11 15:06:55 (12 years ago)
Branch:
default
Phase:
public
Message:

Make InsertionTsp? much faster and improve docs (#386)

Files:
6 edited

Unmodified
Removed
• ## doc/groups.dox

 r1202 - \ref Opt2Tsp 2-opt algorithm \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest solution methods. Furthermore, \ref InsertionTsp is usually quite effective. \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed approximation factor: 3/2. \ref Opt2Tsp usually provides the best results in practice, but it is the slowest method. It can also be used to improve given tours, for example, the results of other algorithms. \image html tsp.png \image latex tsp.eps "Traveling salesman problem" width=\textwidth
• ## lemon/christofides_tsp.h

 r1202 /// This a well-known approximation method for the TSP problem with /// metric cost function. /// It yields a tour whose total cost is at most 3/2 of the optimum, /// but it is usually much better. /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour /// whose total cost is at most 3/2 of the optimum), but it usually /// provides better solutions in practice. /// This implementation runs in O(n3log(n)) time. ///
• ## lemon/greedy_tsp.h

 r1202 /// not increase the degree of any node above two. /// /// This method runs in O(n2log(n)) time. /// It quickly finds a short tour for most TSP instances, but in special /// cases, it could yield a really bad (or even the worst) solution. /// This method runs in O(n2) time. /// It quickly finds a relatively short tour for most TSP instances, /// but it could also yield a really bad (or even the worst) solution /// in special cases. /// /// \tparam CM Type of the cost map.
• ## lemon/insertion_tsp.h

 r1202 #include #include #include #include /// symmetric \ref tsp "TSP". /// /// This is a basic TSP heuristic that has many variants. /// This is a fast and effective tour construction method that has /// many variants. /// It starts with a subtour containing a few nodes of the graph and it /// iteratively inserts the other nodes into this subtour according to a /// certain node selection rule. /// /// This implementation provides four different node selection rules, /// from which the most powerful one is used by default. /// This method is among the fastest TSP algorithms, and it typically /// provides quite good solutions (usually much better than /// \ref NearestNeighborTsp and \ref GreedyTsp). /// /// InsertionTsp implements four different node selection rules, /// from which the most effective one (\e farthest \e node \e selection) /// is used by default. /// With this choice, the algorithm runs in O(n2) time. /// For more information, see \ref SelectionRule. /// const CostMap &_cost; std::vector _notused; std::vector _path; std::vector _tour; Cost _sum; /// During the algorithm, nodes are selected for addition to the current /// subtour according to the applied rule. /// In general, the FARTHEST method yields the best tours, thus it is the /// default option. The RANDOM rule usually gives somewhat worse results, /// but it is much faster than the others and it is the most robust. /// The FARTHEST method is one of the fastest selection rules, and /// it is typically the most effective, thus it is the default /// option. The RANDOM rule usually gives slightly worse results, /// but it is more robust. /// /// The desired selection rule can be specified as a parameter of the /// An unvisited node having minimum distance from the current /// subtour is selected at each step. /// The algorithm runs in O(n3) time using this /// The algorithm runs in O(n2) time using this /// selection rule. NEAREST, /// An unvisited node having maximum distance from the current /// subtour is selected at each step. /// The algorithm runs in O(n3) time using this /// The algorithm runs in O(n2) time using this /// selection rule. FARTHEST, /// increase of the subtour's total cost is selected at each step. /// The algorithm runs in O(n3) time using this /// selection rule. /// selection rule, but in most cases, it is almost as fast as /// with other rules. CHEAPEST, /// \return The total cost of the found tour. Cost run(SelectionRule rule = FARTHEST) { _path.clear(); _tour.clear(); if (_gr.nodeNum() == 0) return _sum = 0; else if (_gr.nodeNum() == 1) { _path.push_back(_gr(0)); _tour.push_back(_gr(0)); return _sum = 0; } case NEAREST: init(true); start(); start >, DefaultInsertion>(); break; case FARTHEST: init(false); start(); start >, DefaultInsertion>(); break; case CHEAPEST: /// \pre run() must be called before using this function. const std::vector& tourNodes() const { return _path; return _tour; } template void tourNodes(Container &container) const { container.assign(_path.begin(), _path.end()); container.assign(_tour.begin(), _tour.end()); } void tour(Path &path) const { path.clear(); for (int i = 0; i < int(_path.size()) - 1; ++i) { path.addBack(_gr.arc(_path[i], _path[i+1])); } if (int(_path.size()) >= 2) { path.addBack(_gr.arc(_path.back(), _path.front())); for (int i = 0; i < int(_tour.size()) - 1; ++i) { path.addBack(_gr.arc(_tour[i], _tour[i+1])); } if (int(_tour.size()) >= 2) { path.addBack(_gr.arc(_tour.back(), _tour.front())); } } Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); _path.clear(); _path.push_back(_gr.u(min_edge)); _path.push_back(_gr.v(min_edge)); _tour.clear(); _tour.push_back(_gr.u(min_edge)); _tour.push_back(_gr.v(min_edge)); _notused.clear(); template void start() { SelectionFunctor selectNode(_gr, _cost, _path, _notused); InsertionFunctor insertNode(_gr, _cost, _path, _sum); SelectionFunctor selectNode(_gr, _cost, _tour, _notused); InsertionFunctor insertNode(_gr, _cost, _tour, _sum); for (int i=0; i<_gr.nodeNum()-2; ++i) { } _sum = _cost[_gr.edge(_path.back(), _path.front())]; for (int i = 0; i < int(_path.size())-1; ++i) { _sum += _cost[_gr.edge(_path[i], _path[i+1])]; } } // Implementation of the nearest selection rule class NearestSelection { _sum = _cost[_gr.edge(_tour.back(), _tour.front())]; for (int i = 0; i < int(_tour.size())-1; ++i) { _sum += _cost[_gr.edge(_tour[i], _tour[i+1])]; } } // Implementation of the nearest and farthest selection rule template class ComparingSelection { public: NearestSelection(const FullGraph &gr, const CostMap &cost, std::vector &path, std::vector ¬used) : _gr(gr), _cost(cost), _path(path), _notused(notused) {} Node select() const { Cost insert_val = 0; int insert_node = -1; ComparingSelection(const FullGraph &gr, const CostMap &cost, std::vector &tour, std::vector ¬used) : _gr(gr), _cost(cost), _tour(tour), _notused(notused), _dist(gr, 0), _compare() { // Compute initial distances for the unused nodes for (unsigned int i=0; i<_notused.size(); ++i) { Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; int min_node = 0; for (unsigned int j=1; j<_path.size(); ++j) { Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; if (min_val > curr) { min_val = curr; min_node = j; Node u = _notused[i]; Cost min_dist = _cost[_gr.edge(u, _tour[0])]; for (unsigned int j=1; j<_tour.size(); ++j) { Cost curr = _cost[_gr.edge(u, _tour[j])]; if (curr < min_dist) { min_dist = curr; } } if (insert_val > min_val || insert_node == -1) { insert_val = min_val; insert_node = i; } } Node n = _notused[insert_node]; _notused.erase(_notused.begin()+insert_node); return n; _dist[u] = min_dist; } } Node select() { // Select an used node with minimum distance Cost ins_dist = 0; int ins_node = -1; for (unsigned int i=0; i<_notused.size(); ++i) { Cost curr = _dist[_notused[i]]; if (_compare(curr, ins_dist) || ins_node == -1) { ins_dist = curr; ins_node = i; } } // Remove the selected node from the unused vector Node sn = _notused[ins_node]; _notused[ins_node] = _notused.back(); _notused.pop_back(); // Update the distances of the remaining nodes for (unsigned int i=0; i<_notused.size(); ++i) { Node u = _notused[i]; Cost nc = _cost[_gr.edge(sn, u)]; if (nc < _dist[u]) { _dist[u] = nc; } } return sn; } const FullGraph &_gr; const CostMap &_cost; std::vector &_path; std::vector &_tour; std::vector &_notused; FullGraph::NodeMap _dist; Comparator _compare; }; // Implementation of the farthest selection rule class FarthestSelection { public: FarthestSelection(const FullGraph &gr, const CostMap &cost, std::vector &path, std::vector ¬used) : _gr(gr), _cost(cost), _path(path), _notused(notused) {} Node select() const { Cost insert_val = 0; int insert_node = -1; for (unsigned int i=0; i<_notused.size(); ++i) { Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; int min_node = 0; for (unsigned int j=1; j<_path.size(); ++j) { Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; if (min_val > curr) { min_val = curr; min_node = j; } } if (insert_val < min_val || insert_node == -1) { insert_val = min_val; insert_node = i; } } Node n = _notused[insert_node]; _notused.erase(_notused.begin()+insert_node); return n; } private: const FullGraph &_gr; const CostMap &_cost; std::vector &_path; std::vector &_notused; }; // Implementation of the cheapest selection rule public: CheapestSelection(const FullGraph &gr, const CostMap &cost, std::vector &path, std::vector ¬used) : _gr(gr), _cost(cost), _path(path), _notused(notused) {} Cost select() const { int insert_notused = -1; int best_insert_index = -1; Cost insert_val = 0; std::vector &tour, std::vector ¬used) : _gr(gr), _cost(cost), _tour(tour), _notused(notused), _ins_cost(gr, 0), _ins_pos(gr, -1) { // Compute insertion cost and position for the unused nodes for (unsigned int i=0; i<_notused.size(); ++i) { int min = i; int best_insert_tmp = 0; Cost min_val = costDiff(_path.front(), _path.back(), _notused[i]); for (unsigned int j=1; j<_path.size(); ++j) { Cost tmp = costDiff(_path[j-1], _path[j], _notused[i]); if (min_val > tmp) { min = i; min_val = tmp; best_insert_tmp = j; Node u = _notused[i]; Cost min_cost = costDiff(_tour.back(), _tour.front(), u); int min_pos = 0; for (unsigned int j=1; j<_tour.size(); ++j) { Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); if (curr_cost < min_cost) { min_cost = curr_cost; min_pos = j; } } if (insert_val > min_val || insert_notused == -1) { insert_notused = min; insert_val = min_val; best_insert_index = best_insert_tmp; } } _path.insert(_path.begin()+best_insert_index, _notused[insert_notused]); _notused.erase(_notused.begin()+insert_notused); return insert_val; _ins_cost[u] = min_cost; _ins_pos[u] = min_pos; } } Cost select() { // Select an used node with minimum insertion cost Cost min_cost = 0; int min_node = -1; for (unsigned int i=0; i<_notused.size(); ++i) { Cost curr_cost = _ins_cost[_notused[i]]; if (curr_cost < min_cost || min_node == -1) { min_cost = curr_cost; min_node = i; } } // Remove the selected node from the unused vector Node sn = _notused[min_node]; _notused[min_node] = _notused.back(); _notused.pop_back(); // Insert the selected node into the tour const int ipos = _ins_pos[sn]; _tour.insert(_tour.begin() + ipos, sn); // Update the insertion cost and position of the remaining nodes for (unsigned int i=0; i<_notused.size(); ++i) { Node u = _notused[i]; Cost curr_cost = _ins_cost[u]; int curr_pos = _ins_pos[u]; int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); if (nc1 <= curr_cost || nc2 <= curr_cost) { // A new position is better than the old one if (nc1 <= nc2) { curr_cost = nc1; curr_pos = ipos; } else { curr_cost = nc2; curr_pos = ipos_next; } } else { if (curr_pos == ipos) { // The minimum should be found again curr_cost = costDiff(_tour.back(), _tour.front(), u); curr_pos = 0; for (unsigned int j=1; j<_tour.size(); ++j) { Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); if (tmp_cost < curr_cost) { curr_cost = tmp_cost; curr_pos = j; } } } else if (curr_pos > ipos) { ++curr_pos; } } _ins_cost[u] = curr_cost; _ins_pos[u] = curr_pos; } return min_cost; } const FullGraph &_gr; const CostMap &_cost; std::vector &_path; std::vector &_tour; std::vector &_notused; FullGraph::NodeMap _ins_cost; FullGraph::NodeMap _ins_pos; }; const int index = rnd[_notused.size()]; Node n = _notused[index]; _notused.erase(_notused.begin()+index); _notused[index] = _notused.back(); _notused.pop_back(); return n; } private: std::vector &_notused; public: DefaultInsertion(const FullGraph &gr, const CostMap &cost, std::vector &path, Cost &total_cost) : _gr(gr), _cost(cost), _path(path), _total(total_cost) {} std::vector &tour, Cost &total_cost) : _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {} void insert(Node n) const { int min = 0; Cost min_val = costDiff(_path.front(), _path.back(), n); for (unsigned int i=1; i<_path.size(); ++i) { Cost tmp = costDiff(_path[i-1], _path[i], n); costDiff(_tour.front(), _tour.back(), n); for (unsigned int i=1; i<_tour.size(); ++i) { Cost tmp = costDiff(_tour[i-1], _tour[i], n); if (tmp < min_val) { min = i; } _path.insert(_path.begin()+min, n); _tour.insert(_tour.begin()+min, n); _total += min_val; } const FullGraph &_gr; const CostMap &_cost; std::vector &_path; std::vector &_tour; Cost &_total; };
• ## lemon/nearest_neighbor_tsp.h

 r1202 /// /// This method runs in O(n2) time. /// It quickly finds a short tour for most TSP instances, but in special /// cases, it could yield a really bad (or even the worst) solution. /// It quickly finds a relatively short tour for most TSP instances, /// but it could also yield a really bad (or even the worst) solution /// in special cases. /// /// \tparam CM Type of the cost map.
• ## lemon/opt2_tsp.h

 r1202 /// Oherwise, it starts with the given tour. /// /// This is a relatively slow but powerful method. /// A typical usage of it is the improvement of a solution that is resulted /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm). /// This is a rather slow but effective method. /// Its typical usage is the improvement of the result of a fast tour /// construction heuristic (e.g. the InsertionTsp algorithm). /// /// \tparam CM Type of the cost map.
Note: See TracChangeset for help on using the changeset viewer.