fork download
copy 
  1. //#define NDEBUG
  2.  
  3. #include <algorithm>
  4. #include <array>
  5. #include <bitset>
  6. #include <cassert>
  7. #include <chrono>
  8. #include <iostream>
  9. #include <vector>
  10. #include "boost/multi_array.hpp"
  11.  
  12. struct EndDistances;
  13. using CityId = unsigned;
  14. using DistanceType = unsigned;
  15. using StoredDistanceType = unsigned char;
  16. using CacheDistanceType = EndDistances;
  17. using DistanceArray = boost::multi_array<DistanceType, 2>;
  18.  
  19. template<std::size_t size>
  20. std::ostream& operator<<(std::ostream& out, const unsigned(& v)[size]) {
  21.         out << '{';
  22.     for(unsigned i=0; i<size; i++)
  23.         out << v[i]<<',';
  24.     return out << '}';
  25. }
  26. std::ostream& operator<<(std::ostream& out, const std::vector<unsigned>& v) {
  27.         out << '{';
  28.     for(unsigned i=0; i<v.size(); i++)
  29.         out << v[i]<<',';
  30.     return out << '}';
  31. }
  32. std::ostream& operator<<(std::ostream& out, const boost::detail::multi_array::sub_array<unsigned,1>& v) {
  33.         out << '{';
  34.     for(unsigned i=0; i<v.size(); i++)
  35.         out << v[i]<<',';
  36.     return out << '}';
  37. }
  38.  
  39. struct EndDistances {
  40.     StoredDistanceType dists[7];
  41. };
  42. class TspCache {
  43.     std::vector<CacheDistanceType> cache;
  44. public:
  45.     std::size_t size() {return cache.size();}
  46.     void assertEmpty(std::size_t idx) {assert(idx>=cache.size() || cache[idx].dists[0]==0);}
  47.     void put(std::size_t idx, CacheDistanceType distance) {if(cache.size()<=idx)cache.resize(idx+1); cache[idx] = distance;}
  48.     const CacheDistanceType& get(std::size_t idx) { assert(idx<cache.size()); return cache[idx];}
  49. };
  50.  
  51. class TspSolver {
  52.     using OrderIdx = unsigned;
  53.     using OrderedCityArray = boost::multi_array<CityId, 2>;
  54.  
  55.     unsigned city_count;
  56.     DistanceArray distances;
  57.     OrderedCityArray closest_cities;
  58.     TspCache end_cache;
  59.     DistanceType best_end_distance;
  60.  
  61.     std::vector<CityId> current_cities;
  62.     unsigned current_count;
  63.     unsigned visited;
  64.     DistanceType current_distance;
  65.     std::vector<CityId> best_cities;
  66.     DistanceType best_distance;
  67.  
  68.     void calculate_closest_cities() {
  69.         closest_cities.resize(boost::extents[city_count][city_count]);
  70.         for(CityId i=0; i<city_count; i++) {
  71.             for(CityId j=0; j<city_count; j++)
  72.                 closest_cities[i][j] = j;
  73.             auto comp = [&](CityId l, CityId r){
  74.                 if(l>0 && r>0) return distances[i][l] < distances[i][r];
  75.                 return l>0;
  76.             };
  77.             std::sort(closest_cities[i].begin(), closest_cities[i].end(), comp);
  78.         }
  79.     }
  80.     template<unsigned k>
  81.     static unsigned n_choose_k(unsigned n) {
  82.         if (k > n) return 0;
  83.         if (k == n) return 1;
  84.         unsigned long long result = 1;
  85.         for( unsigned i = 1; i <= k; ++i ) {
  86.             result *= (n-i+1);
  87.             result /= i;
  88.         }
  89.         return result;
  90.     }
  91.     DistanceType find_end_distance(CityId* cities, DistanceType abortDistance) {
  92.         //assert(std::cout << "find_end_distance "<< cities[0] << ',' << cities[1] << ',' << cities[2]  << ',' << cities[3]  << ',' << cities[4]  << ',' << cities[5] << " abortDistance="<<abortDistance<<std::flush);
  93.         assert(std::is_sorted(cities+1, cities+6));
  94.         DistanceType local_min = std::numeric_limits<DistanceType>::max();
  95.         std::array<CityId, 6> best;
  96.         do {
  97.             DistanceType dist = distances[cities[0]][cities[1]] 
  98.                 + distances[cities[1]][cities[2]]
  99.                 + distances[cities[2]][cities[3]] 
  100.                 + distances[cities[3]][cities[4]]
  101.                 + distances[cities[4]][cities[5]]
  102.                 + distances[cities[5]][0];
  103.             if (dist == abortDistance) {                
  104.                 //assert(std::cout << " found="<< cities[0] << ',' << cities[1] << ',' << cities[2]  << ',' << cities[3]  << ',' << cities[4]  << ',' << cities[5]<<'\n'<<std::flush);
  105.                 return abortDistance;
  106.             }
  107.             if (dist < local_min) {
  108.                 local_min = dist;
  109.                 std::copy(cities, cities+6, best.begin());
  110.             }
  111.         } while(std::next_permutation(cities+0, cities+6));
  112.         std::copy(best.begin(), best.end(), cities);
  113.         //assert(std::cout << " local_min="<<local_min<<'\n'<<std::flush);
  114.         return local_min;
  115.     }
  116.     void fill_cache() {
  117.         //assert(n_choose_k<7>(64) == 621216192);
  118.         best_end_distance = std::numeric_limits<DistanceType>::max();
  119.         unsigned count = 0;
  120.         for(CityId a=7; a<city_count; a++) {
  121.             unsigned ai = a-7;
  122.             unsigned am = n_choose_k<7>(a-1);
  123.             unsigned aa = 0+am;
  124.             for(CityId b=1; b<a; b++) {
  125.                 unsigned bi = b-6;
  126.                 unsigned bm = n_choose_k<6>(b-1);
  127.                 unsigned ba = aa+bm;
  128.                 for(CityId c=1; c<b; c++) {
  129.                     unsigned ci = c-1;
  130.                     unsigned cm = n_choose_k<5>(c-1);
  131.                     unsigned ca = ba+cm;
  132.                     for(CityId d=1; d<c; d++) {
  133.                         unsigned di = d-1;
  134.                         unsigned dm = n_choose_k<4>(d-1);
  135.                         unsigned da = ca+dm;
  136.                         for(CityId e=1; e<d; e++) {
  137.                             unsigned ei = e-1;
  138.                             unsigned em = n_choose_k<3>(e-1);
  139.                             unsigned ea = da+em;
  140.                             for(CityId f=1; f<e; f++) {
  141.                                 unsigned fi = f-1;
  142.                                 unsigned fm = n_choose_k<2>(f-1);
  143.                                 unsigned fa = ea+fm;
  144.                                 for(CityId g=1; g<f; g++) {
  145.                                     unsigned gi = g-1;
  146.                                     unsigned gm = gi; // n_choose_k<1>(g-1) is always g-1;
  147.                                     unsigned ga = fa+gm;
  148.                                     assert(std::cout << "fill_cache offsets=" <<ai<<'x'<<am << ',' <<bi<<'x'<<bm<< ',' <<ci<<'x'<<cm  << ',' <<di<<'x'<<dm  << ',' <<ei<<'x'<<em  << ',' <<fi<<'x'<<fm  << ',' <<gi<<'x'<<gm<<" ga="<<ga<<'\n' << std::flush);
  149.                                     std::array<CityId,6> cities = {{g, f, e, d, c, b}};
  150.                                     EndDistances ends;
  151.                                     ends.dists[0] = find_end_distance(cities.data(), 0);
  152.                                     ends.dists[0] += distances[a][cities[0]];
  153.                                     cities = {{g, f, e, d, c, a}};
  154.                                     ends.dists[1] = find_end_distance(cities.data(), 0);
  155.                                     ends.dists[1] += distances[b][cities[0]];
  156.                                     cities = {{g, f, e, d, b, a}};
  157.                                     ends.dists[2] = find_end_distance(cities.data(), 0);
  158.                                     ends.dists[2] += distances[c][cities[0]];
  159.                                     cities = {{g, f, e, c, b, a}};
  160.                                     ends.dists[3] = find_end_distance(cities.data(), 0);
  161.                                     ends.dists[3] += distances[d][cities[0]];
  162.                                     cities = {{g, f, d, c, b, a}};
  163.                                     ends.dists[4] = find_end_distance(cities.data(), 0);
  164.                                     ends.dists[4] += distances[d][cities[0]];
  165.                                     cities = {{g, e, d, c, b, a}};
  166.                                     ends.dists[5] = find_end_distance(cities.data(), 0);
  167.                                     ends.dists[5] += distances[f][cities[0]];
  168.                                     cities = {{f, e, d, c, b, a}};
  169.                                     ends.dists[6] = find_end_distance(cities.data(), 0);
  170.                                     ends.dists[6] += distances[g][cities[0]];
  171.                                     assert(std::cout << "fill_cache " << a << ',' << b << ',' << c  << ',' << d  << ',' << e  << ',' << f  << ',' << g << " idx=" << ga << '\n' << std::flush);
  172.                                     end_cache.assertEmpty(ga);
  173.                                     end_cache.put(ga, ends);
  174.                                     assert(end_cache.get(ga).dists[0]>0);
  175.                                     ++count;
  176.                                     DistanceType local_min = *std::min(ends.dists+0, ends.dists+7);
  177.                                     if (local_min<best_end_distance)
  178.                                         best_end_distance = local_min;
  179.                                 }
  180.                             }
  181.                         }
  182.                     }
  183.                 }
  184.             }
  185.         }
  186.         std::cout << "Using " << (count*sizeof(CacheDistanceType)) << " out of " << (end_cache.size()*sizeof(CacheDistanceType)) << " allocated bytes\n";// << std::flush; 
  187.         assert(std::cout << "fill_cache best_end_distance=" << best_end_distance << '\n' << std::flush);
  188.     }
  189.     void solve_end_fast() {
  190.         unsigned remain = visited;
  191.         CityId prev = current_cities[city_count-8];
  192.         assert(std::cout << "solve_end_fast  count=" << current_count << " current=" << current_cities << " dist=" << current_distance << " prev_city=" << prev << " prev_visited="<<std::bitset<32>(visited)<<std::flush);
  193.         CityId* remainingIds = current_cities.data()+city_count-7;
  194.         CityId& a = remainingIds[0];
  195.         CityId& b = remainingIds[1];
  196.         CityId& c = remainingIds[2];
  197.         CityId& d = remainingIds[3];
  198.         CityId& e = remainingIds[4];
  199.         CityId& f = remainingIds[5];
  200.         CityId& g = remainingIds[6];
  201.         a = 31-__builtin_clz(remain);
  202.         remain &= ~(1u<<a);
  203.         b = 31-__builtin_clz(remain);
  204.         remain &= ~(1u<<b);
  205.         c = 31-__builtin_clz(remain);
  206.         remain &= ~(1u<<c);
  207.         d = 31-__builtin_clz(remain);
  208.         remain &= ~(1u<<d);
  209.         e = 31-__builtin_clz(remain);
  210.         remain &= ~(1u<<e);
  211.         f = 31-__builtin_clz(remain);
  212.         remain &= ~(1u<<f);
  213.         g = 31-__builtin_clz(remain);
  214.         assert(std::cout << " remaining="<< a << ',' << b << ',' << c  << ',' << d  << ',' << e  << ',' << f  << ',' << g << std::flush);
  215.             unsigned ai = a-7;
  216.             unsigned am = n_choose_k<7>(a-1);
  217.             unsigned aa = 0+am;
  218.                 unsigned bi = b-6;
  219.                 unsigned bm = n_choose_k<6>(b-1);
  220.                 unsigned ba = aa+bm;
  221.                     unsigned ci = c-1;
  222.                     unsigned cm = n_choose_k<5>(c-1);
  223.                     unsigned ca = ba+cm;
  224.                         unsigned di = d-1;
  225.                         unsigned dm = n_choose_k<4>(d-1);
  226.                         unsigned da = ca+dm;
  227.                             unsigned ei = e-1;
  228.                             unsigned em = n_choose_k<3>(e-1);
  229.                             unsigned ea = da+em;
  230.                                 unsigned fi = f-1;
  231.                                 unsigned fm = n_choose_k<2>(f-1);
  232.                                 unsigned fa = ea+fm;
  233.                                     unsigned gi = g-1;
  234.                                     unsigned gm = gi; // n_choose_k<1>(g-1) is always g-1;
  235.                                     unsigned ga = fa+gm;
  236.         assert(std::cout << " offsets=" <<ai<<'x'<<am << ',' <<bi<<'x'<<bm<< ',' <<ci<<'x'<<cm  << ',' <<di<<'x'<<dm  << ',' <<ei<<'x'<<em  << ',' <<fi<<'x'<<fm  << ',' <<gi<<'x'<<gm<<" ga="<<ga << std::flush);
  237.         const EndDistances& end_dist_array = end_cache.get(ga);
  238.         assert(end_dist_array.dists[0]>0);
  239.         EndDistances new_dist_array = {{
  240.             static_cast<StoredDistanceType>(current_distance + distances[prev][a] + end_dist_array.dists[0]),
  241.             static_cast<StoredDistanceType>(current_distance + distances[prev][b] + end_dist_array.dists[1]),
  242.             static_cast<StoredDistanceType>(current_distance + distances[prev][c] + end_dist_array.dists[2]),
  243.             static_cast<StoredDistanceType>(current_distance + distances[prev][d] + end_dist_array.dists[3]),
  244.             static_cast<StoredDistanceType>(current_distance + distances[prev][e] + end_dist_array.dists[4]),
  245.             static_cast<StoredDistanceType>(current_distance + distances[prev][f] + end_dist_array.dists[5]),
  246.             static_cast<StoredDistanceType>(current_distance + distances[prev][g] + end_dist_array.dists[6]),
  247.         }};
  248.         assert(std::cout << " dists="<<+end_dist_array.dists[0]<<','<<+end_dist_array.dists[1]<<','<<+end_dist_array.dists[2]<<','<<+end_dist_array.dists[3]<<','<<+end_dist_array.dists[4]<<','<<+end_dist_array.dists[5]<<','<<+end_dist_array.dists[6] << std::flush);
  249.         unsigned best_idx = std::min_element(new_dist_array.dists+0, new_dist_array.dists+7)-new_dist_array.dists+0;
  250.         DistanceType end_dist = end_dist_array.dists[best_idx];
  251.         DistanceType new_dist = new_dist_array.dists[best_idx];
  252.         assert(std::cout << " best_idx="<< best_idx << " first="<<remainingIds[best_idx]<<" end_dist=" << end_dist << " new_dist=" << new_dist << std::flush);
  253.         if (new_dist >= best_distance) {
  254.             assert(std::cout << " - exit because " <<  new_dist << ">=" << best_distance << '\n' << std::flush);
  255.             return;
  256.         }
  257.         assert(std::cout << '\n'<<std::flush);
  258.         assert(std::cout << "solve_end_slow  beforeRotate=" << current_cities << '\n' << std::flush);
  259.         if (best_idx>0)
  260.             std::rotate(remainingIds+0, remainingIds+best_idx,remainingIds+best_idx+1);
  261.         std::reverse(remainingIds+1, remainingIds+7);
  262.         assert(std::cout << "solve_end_slow  afterRotate=" << current_cities << '\n' << std::flush);
  263.         find_end_distance(&current_cities[city_count-7], end_dist);
  264.         assert(std::cout << "solve_end_slow  " << current_cities << " new best because " << new_dist << "<" << best_distance << '\n' << std::flush);
  265.         best_cities = current_cities;
  266.         best_distance = new_dist;
  267.     }
  268.     void solve_recursive() {
  269.         unsigned prev_count = current_count;
  270.         DistanceType prev_distance = current_distance;
  271.         unsigned prev_visited = visited;
  272.         CityId prev_city = current_cities[current_count-1];
  273.         assert(std::cout << "solve_recursive count=" << prev_count << " current=" << current_cities << " dist=" << prev_distance << " prev_city=" << prev_city << " prev_visited="<<std::bitset<32>(prev_visited)<<" closest=" << closest_cities[prev_city] << '\n' << std::flush);
  274.         ++current_count;
  275.         for(OrderIdx i=0; i<city_count; i++) {
  276.             CityId c = closest_cities[prev_city][i];
  277.             if ((visited & (1u<<c)) == 0) continue;
  278.             current_cities[prev_count] = c;
  279.             current_distance = prev_distance + distances[prev_city][c];
  280.             if (current_distance + best_end_distance >= best_distance) {
  281.                 assert(std::cout << "solve_recursive     skip " << c << " because " <<  current_distance << " + " << best_end_distance << " >= " << best_distance << '\n' << std::flush);
  282.                 continue;
  283.             }
  284.             visited = prev_visited & ~(1u<<c);
  285.             if (current_count == city_count-7)
  286.                 solve_end_fast();
  287.             else
  288.                 solve_recursive();
  289.         }
  290.         current_count = prev_count;
  291.     }
  292. public:
  293.     TspSolver(DistanceArray distances_) 
  294.     : distances(std::move(distances_)) 
  295.     {
  296.         city_count = distances.size();
  297.         calculate_closest_cities();
  298.         fill_cache();
  299.     }
  300.  
  301.     std::vector<CityId> solve() {
  302.         current_cities.resize(city_count + 1, 0);
  303.         current_count = 1;
  304.         current_distance = 0;
  305.         visited = (1u<<city_count)-2u;
  306.         best_cities.resize(city_count + 1, 0);
  307.         best_distance = std::numeric_limits<DistanceType>::max();
  308.         solve_recursive();
  309.         return best_cities;
  310.     }
  311. };
  312.  
  313. DistanceArray get_distances() {
  314.     std::istream& in = std::cin;
  315.     unsigned city_count;
  316.     in >> city_count;
  317.     DistanceArray distances(boost::extents[city_count][city_count]);
  318.     for(CityId i=0; i<city_count-1; i++) {
  319.         distances[i][i] = std::numeric_limits<DistanceType>::max();
  320.         for(CityId j=i+1; j<city_count; j++) {
  321.             in >> distances[i][j];
  322.             distances[j][i] = distances[i][j];
  323.         }
  324.     }
  325.     assert(in);
  326.     return distances;
  327. }
  328.  
  329. int main() {
  330.     auto start = std::chrono::high_resolution_clock::now();
  331.     TspSolver solver(get_distances());
  332.     std::vector<unsigned> cities = solver.solve();
  333.     auto end = std::chrono::high_resolution_clock::now();
  334.     for(CityId i=0; i<cities.size(); i++)
  335.         std::cout << cities[i] << ',';
  336.     std::cout << ' ' << duration_cast<std::chrono::milliseconds>(end-start).count() << "ms\n";
  337. }
  338.  
  339. 10 6 7 2 2 7 3 4 8 2 2 6 4 5 5 5 3 6 6 5 6 5 4 2 6 2 8 4 3 6 2 6 3 3 7 3 3 6 8 5 6 9 3 6 6 11
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:336:25: error: ‘duration_cast’ was not declared in this scope
     std::cout << ' ' << duration_cast<std::chrono::milliseconds>(end-start).count() << "ms\n";
                         ^~~~~~~~~~~~~
prog.cpp:336:25: note: suggested alternative:
In file included from prog.cpp:7:
/usr/include/c++/8/chrono:193:7: note:   ‘std::chrono::duration_cast’
       duration_cast(const duration<_Rep, _Period>& __d)
       ^~~~~~~~~~~~~
prog.cpp:336:64: error: expected primary-expression before ‘>’ token
     std::cout << ' ' << duration_cast<std::chrono::milliseconds>(end-start).count() << "ms\n";
                                                                ^
prog.cpp:336:85: error: invalid operands of types ‘std::chrono::duration<long int, std::ratio<1, 1000000000> >::rep’ {aka ‘long int’} and ‘const char [4]’ to binary ‘operator<<’
     std::cout << ' ' << duration_cast<std::chrono::milliseconds>(end-start).count() << "ms\n";
                                                                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
prog.cpp: At global scope:
prog.cpp:339:1: error: expected unqualified-id before numeric constant
 10 6 7 2 2 7 3 4 8 2 2 6 4 5 5 5 3 6 6 5 6 5 4 2 6 2 8 4 3 6 2 6 3 3 7 3 3 6 8 5 6 9 3 6 6 11
 ^~
stdout
copy 
Standard output is empty
https://ideone.com/2jnfRE
language:
C++14 (gcc 8.3)
created:
163 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!