Last active
July 21, 2025 11:59
-
-
Save Hermann-SW/1218d13dc7fb95aa90687ad8baa06787 to your computer and use it in GitHub Desktop.
TSP Ruin and Recreate greedy implementation with random+sequential+radial ruins
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // Developemnt of this gist is stopped, no further updates. | |
| // | |
| // This is the equivalent of this gist in new RR repo: | |
| // https://github.com/Hermann-SW/RR/blob/main/tsp/greedy.cpp | |
| // | |
| // Code is split up, and a loader was added allowing for differnt problems. | |
| // In addition that repo has 111 TSP problems with 108 corresponding | |
| // optimal tours. | |
| /* | |
| hermann@7950x:~/RR/tsp$ make clean | |
| rm -f load_test greedy | |
| hermann@7950x:~/RR/tsp$ make greedy | |
| g++ -O3 -std=c++20 -Wall -Wextra -pedantic greedy.cpp -o greedy -lstdc++ -lm | |
| hermann@7950x:~/RR/tsp$ | |
| hermann@7950x:~/RR/tsp$ perf stat -e cycles,task-clock ./greedy 205 ../data/tsp/pcb442 | |
| 50933 local minimum found (after 100,000 greedy mutations) | |
| 5854 ms (only recreate) | |
| 50778 global minimum | |
| Performance counter stats for './greedy 205 ../data/tsp/pcb442': | |
| 37,708,902,114 cycles # 5.493 GHz | |
| 6,864.89 msec task-clock # 1.000 CPUs utilized | |
| 6.865929950 seconds time elapsed | |
| 6.864255000 seconds user | |
| 0.001000000 seconds sys | |
| hermann@7950x:~/RR/tsp$ | |
| */ | |
| /* | |
| TSP Ruin and Recreate greedy implementation with random+sequential+radial ruins: | |
| https://www.semanticscholar.org/paper/Record-Breaking-Optimization-Results-Using-the-Ruin-Schrimpf-Schneider/4f80e70e51e368858c3df0787f05c3aa2b9650b4 | |
| c++ -O3 -std=c++17 -Wall -Wextra -pedantic pcb442.cpp -o pcb442 -lstdc++ -lm | |
| (tested with g++ and clang++) | |
| for tour display | |
| - append compiler flags "-Dezxdisp -lezx -lX11" | |
| - after "make install" of ezxdisp repo first: | |
| https://github.com/Hermann-SW/ezxdisp?tab=readme-ov-file#support-for-c--use-in-ide | |
| (left mouse click continues to next accepted mutation and updates display; repeat) | |
| cpplint --filter=-legal/copyright,-runtime/references pcb442.cpp | |
| cppcheck --enable=all --suppress=missingIncludeSystem pcb442.cpp | |
| */ | |
| #include <sys/time.h> | |
| auto _sum = 0; | |
| struct timeval _tv0; | |
| #define _tim gettimeofday(&_tv0, NULL) | |
| #define _start (_tim, _sum -= (1000000*_tv0.tv_sec + _tv0.tv_usec)); | |
| #define _stop (_tim, _sum += (1000000*_tv0.tv_sec + _tv0.tv_usec)); | |
| #ifdef ezxdisp | |
| #include <unistd.h> | |
| #include <ezxdisp.h> | |
| #endif | |
| #include <sstream> | |
| #include <algorithm> | |
| #include <iostream> | |
| #include <cmath> | |
| #include <cassert> | |
| #include <vector> | |
| #include <list> | |
| std::string i2s(int x) { std::stringstream s2; s2 << x; return s2.str(); } | |
| template <typename C> | |
| [[maybe_unused]] void print(const C& L) { | |
| std::for_each(L.begin(), L.end(), [](const typename C::value_type i) { | |
| std::cout << i << " "; | |
| }); | |
| std::cout << '\n'; | |
| } | |
| template <typename urn> | |
| typename urn::value_type edraw(urn& U) { | |
| auto r = random() % U.size(); | |
| typename urn::value_type ret = U[r]; | |
| U[r] = U.back(); | |
| U.pop_back(); | |
| return ret; | |
| } | |
| template <typename val, int N> | |
| class random_access_list { | |
| std::list<val> L; | |
| public: | |
| typedef typename std::list<val>::iterator iterator; | |
| iterator A[N]; | |
| void init() { | |
| L.clear(); | |
| for (int i = 0; i < N; ++i) A[i] = L.end(); | |
| } | |
| iterator& operator[](std::size_t i) { return A[i]; } | |
| void sort() { L.sort(); } | |
| void push_back(val& v ) { L.push_back(v); A[v] = --L.end(); } | |
| iterator insert(iterator it, val& v ) { return A[v] = L.insert(it, v); } | |
| iterator erase(iterator it) { A[*it] = L.end(); return L.erase(it); } | |
| iterator erase(int i) { | |
| iterator it = A[i]; A[i] = L.end(); return L.erase(it); | |
| } | |
| iterator begin() { return L.begin(); } | |
| iterator end() { return L.end(); } | |
| bool empty() { return L.empty(); } | |
| val& back() { return L.back(); } | |
| size_t size() { return L.size(); } | |
| }; | |
| template <typename config, typename urn> | |
| class pcb442 { | |
| public: | |
| static const int N = 442; // config::N; | |
| const double siz, ran, seq, rad; | |
| std::string last; | |
| pcb442(double _siz, double _ran, double _seq, double _rad) : | |
| siz(_siz), ran(_ran), seq(_seq), rad(_rad) { | |
| assert(siz >= 0.0 && siz <= 1.0); | |
| assert(ran+seq+rad == 1.0); | |
| assert(ran >= 0.0 && seq >= 0.0 && rad >= 0.0); | |
| init_dist(); | |
| } | |
| int cost(config& C) { | |
| int cost = 0; | |
| int prev = C.empty() ? -1 : C.back(); | |
| std::for_each(C.begin(), C.end(), [this, &cost, &prev](const int c) { | |
| cost += D[prev][c]; prev = c; | |
| }); | |
| return cost; | |
| } | |
| void init(config &C, std::pair<urn, urn> &Us) { | |
| C.init(); | |
| Us.first.clear(); | |
| Us.second.clear(); | |
| for (int i = 0; i < N; ++i) Us.first.push_back(i); | |
| } | |
| void RR_all(config &C, std::pair<urn, urn> &Us) { | |
| init(C, Us); | |
| recreate(C, Us); | |
| } | |
| int draw_rad(config& C, int size, std::pair<urn, urn>& Us) { | |
| auto center = random() % C.size(); | |
| last = "rad(" + i2s(center) + "," + i2s(size) + ")"; | |
| Us.first.clear(); | |
| std::for_each_n(rad_nxt[center].begin(), size, [&C, &Us](auto& c) { | |
| C.erase(c); | |
| Us.first.push_back(c); | |
| }); | |
| return center; | |
| } | |
| int draw_seq(config& C, int size, std::pair<urn, urn>& Us) { | |
| auto start = random() % C.size(); | |
| last = "seq(" + i2s(start) + "," + i2s(size) + ")"; | |
| typename config::iterator it = C[start]; | |
| int ret = *it; | |
| while (size-- > 0 && it != C.end()) { | |
| int c = *it; | |
| it = C.erase(it); | |
| Us.first.push_back(c); | |
| } | |
| it = C.begin(); | |
| while (size-- > 0) { | |
| int c = *it; | |
| it = C.erase(it); | |
| Us.first.push_back(c); | |
| } | |
| return -1-ret; | |
| } | |
| int draw_ran(config& C, int size, | |
| std::pair<urn, urn>& Us) { | |
| assert(Us.first.size() == 0); | |
| assert(Us.second.size() == N); | |
| last = "ran(" + i2s(size) + ")"; | |
| for (; size > 0; --size) { | |
| int r = edraw(Us.second); | |
| Us.first.push_back(r); | |
| C.erase(r); | |
| } | |
| std::for_each(Us.first.begin(), Us.first.end(), [&Us](int c) { | |
| Us.second.push_back(c); | |
| }); | |
| return std::numeric_limits<int>::max(); | |
| } | |
| int draw(config& C, int size, | |
| std::pair<urn, urn>& Us) { | |
| double d = drand48(); | |
| if (d < ran) return draw_ran(C, size, Us); | |
| else if (d < ran+seq) return draw_seq(C, size, Us); | |
| else return draw_rad(C, size, Us); | |
| } | |
| /* | |
| returns | |
| - std::numeric_limits<int>::max() for ran | |
| - center city for rad | |
| - -(1+start) city for seq | |
| */ | |
| int ruin(config& C, std::pair<urn, urn>& Us) { | |
| return draw(C, ceil(drand48() * (siz * N)), Us); | |
| } | |
| void recreate(config& C, std::pair<urn, urn>& Us) { | |
| while (!Us.first.empty()) { | |
| int c = edraw(Us.first); | |
| assert(C[c] == C.end()); | |
| _start | |
| int mincost = std::numeric_limits<int>::max(); | |
| int prev = C.empty() ? -1 : C.back(); | |
| typename config::iterator best = C.end(); | |
| for (typename config::iterator it = C.begin(); it != C.end(); ++it) { | |
| int cur = *it; | |
| int ncost = D[prev][c] + D[c][cur] - D[prev][cur]; | |
| if (ncost < mincost) { | |
| best = it; | |
| mincost = ncost; | |
| } | |
| prev = cur; | |
| } | |
| _stop | |
| C.insert(best, c); | |
| } | |
| } | |
| int D[N][N]; // distance matrix | |
| struct { | |
| int* vi; | |
| bool operator()(int a, int b) { | |
| return vi[a] < vi[b]; | |
| } | |
| } Dless; | |
| std::vector<int> rad_nxt[N]; // radial next | |
| void init_dist() { | |
| for (int from = 0; from < N; ++from) { | |
| rad_nxt[from].clear(); | |
| for (int to = 0; to < N; ++to) { | |
| D[from][to] = dist(from, to); | |
| rad_nxt[from].push_back(to); | |
| } | |
| } | |
| for (int from = 0; from < N; ++from) { | |
| Dless.vi = D[from]; | |
| std::sort(rad_nxt[from].begin(), rad_nxt[from].end(), Dless); | |
| } | |
| } | |
| inline int nint(double d) { return static_cast<int>(0.5 + d); } | |
| // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf#page=6 | |
| // $ grep EDGE_WEIGHT_TYPE pcb442.tsp | |
| // EDGE_WEIGHT_TYPE : EUC_2D | |
| // $ | |
| int dist(int from, int to) { | |
| double xd = C[from][0] - C[to][0]; | |
| double yd = C[from][1] - C[to][1]; | |
| return nint(sqrt(xd*xd + yd*yd)); | |
| } | |
| // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/pcb442.tsp.gz | |
| const double C[N][2]={ | |
| {2.00000e+02, 4.00000e+02}, | |
| {2.00000e+02, 5.00000e+02}, | |
| {2.00000e+02, 6.00000e+02}, | |
| {2.00000e+02, 7.00000e+02}, | |
| {2.00000e+02, 8.00000e+02}, | |
| {2.00000e+02, 9.00000e+02}, | |
| {2.00000e+02, 1.00000e+03}, | |
| {2.00000e+02, 1.10000e+03}, | |
| {2.00000e+02, 1.20000e+03}, | |
| {2.00000e+02, 1.30000e+03}, | |
| {2.00000e+02, 1.40000e+03}, | |
| {2.00000e+02, 1.50000e+03}, | |
| {2.00000e+02, 1.60000e+03}, | |
| {2.00000e+02, 1.70000e+03}, | |
| {2.00000e+02, 1.80000e+03}, | |
| {2.00000e+02, 1.90000e+03}, | |
| {2.00000e+02, 2.00000e+03}, | |
| {2.00000e+02, 2.10000e+03}, | |
| {2.00000e+02, 2.20000e+03}, | |
| {2.00000e+02, 2.30000e+03}, | |
| {2.00000e+02, 2.40000e+03}, | |
| {2.00000e+02, 2.50000e+03}, | |
| {2.00000e+02, 2.60000e+03}, | |
| {2.00000e+02, 2.70000e+03}, | |
| {2.00000e+02, 2.80000e+03}, | |
| {2.00000e+02, 2.90000e+03}, | |
| {2.00000e+02, 3.00000e+03}, | |
| {2.00000e+02, 3.10000e+03}, | |
| {2.00000e+02, 3.20000e+03}, | |
| {2.00000e+02, 3.30000e+03}, | |
| {2.00000e+02, 3.40000e+03}, | |
| {2.00000e+02, 3.50000e+03}, | |
| {2.00000e+02, 3.60000e+03}, | |
| {3.00000e+02, 4.00000e+02}, | |
| {3.00000e+02, 5.00000e+02}, | |
| {3.00000e+02, 6.00000e+02}, | |
| {3.00000e+02, 7.00000e+02}, | |
| {3.00000e+02, 8.00000e+02}, | |
| {3.00000e+02, 9.00000e+02}, | |
| {3.00000e+02, 1.00000e+03}, | |
| {3.00000e+02, 1.10000e+03}, | |
| {3.00000e+02, 1.20000e+03}, | |
| {3.00000e+02, 1.30000e+03}, | |
| {3.00000e+02, 1.40000e+03}, | |
| {3.00000e+02, 1.50000e+03}, | |
| {3.00000e+02, 1.60000e+03}, | |
| {3.00000e+02, 1.70000e+03}, | |
| {3.00000e+02, 1.80000e+03}, | |
| {3.00000e+02, 1.90000e+03}, | |
| {3.00000e+02, 2.00000e+03}, | |
| {3.00000e+02, 2.10000e+03}, | |
| {3.00000e+02, 2.20000e+03}, | |
| {3.00000e+02, 2.30000e+03}, | |
| {3.00000e+02, 2.40000e+03}, | |
| {3.00000e+02, 2.50000e+03}, | |
| {3.00000e+02, 2.60000e+03}, | |
| {3.00000e+02, 2.70000e+03}, | |
| {3.00000e+02, 2.80000e+03}, | |
| {3.00000e+02, 2.90000e+03}, | |
| {3.00000e+02, 3.00000e+03}, | |
| {3.00000e+02, 3.10000e+03}, | |
| {3.00000e+02, 3.20000e+03}, | |
| {3.00000e+02, 3.30000e+03}, | |
| {3.00000e+02, 3.40000e+03}, | |
| {3.00000e+02, 3.50000e+03}, | |
| {4.00000e+02, 4.00000e+02}, | |
| {4.00000e+02, 5.00000e+02}, | |
| {4.00000e+02, 6.00000e+02}, | |
| {4.00000e+02, 7.00000e+02}, | |
| {4.00000e+02, 8.00000e+02}, | |
| {4.00000e+02, 9.00000e+02}, | |
| {4.00000e+02, 1.00000e+03}, | |
| {4.00000e+02, 1.10000e+03}, | |
| {4.00000e+02, 1.20000e+03}, | |
| {4.00000e+02, 1.30000e+03}, | |
| {4.00000e+02, 1.40000e+03}, | |
| {4.00000e+02, 1.50000e+03}, | |
| {4.00000e+02, 1.60000e+03}, | |
| {4.00000e+02, 1.70000e+03}, | |
| {4.00000e+02, 1.80000e+03}, | |
| {4.00000e+02, 1.90000e+03}, | |
| {4.00000e+02, 2.00000e+03}, | |
| {4.00000e+02, 2.10000e+03}, | |
| {4.00000e+02, 2.20000e+03}, | |
| {4.00000e+02, 2.30000e+03}, | |
| {4.00000e+02, 2.40000e+03}, | |
| {4.00000e+02, 2.50000e+03}, | |
| {4.00000e+02, 2.60000e+03}, | |
| {4.00000e+02, 2.70000e+03}, | |
| {4.00000e+02, 2.80000e+03}, | |
| {4.00000e+02, 2.90000e+03}, | |
| {4.00000e+02, 3.00000e+03}, | |
| {4.00000e+02, 3.10000e+03}, | |
| {4.00000e+02, 3.20000e+03}, | |
| {4.00000e+02, 3.30000e+03}, | |
| {4.00000e+02, 3.40000e+03}, | |
| {4.00000e+02, 3.50000e+03}, | |
| {4.00000e+02, 3.60000e+03}, | |
| {5.00000e+02, 1.50000e+03}, | |
| {5.00000e+02, 1.82900e+03}, | |
| {5.00000e+02, 3.10000e+03}, | |
| {6.00000e+02, 4.00000e+02}, | |
| {7.00000e+02, 3.00000e+02}, | |
| {7.00000e+02, 6.00000e+02}, | |
| {7.00000e+02, 1.50000e+03}, | |
| {7.00000e+02, 1.60000e+03}, | |
| {7.00000e+02, 1.80000e+03}, | |
| {7.00000e+02, 2.10000e+03}, | |
| {7.00000e+02, 2.40000e+03}, | |
| {7.00000e+02, 2.70000e+03}, | |
| {7.00000e+02, 3.00000e+03}, | |
| {7.00000e+02, 3.30000e+03}, | |
| {7.00000e+02, 3.60000e+03}, | |
| {8.00000e+02, 3.00000e+02}, | |
| {8.00000e+02, 6.00000e+02}, | |
| {8.00000e+02, 1.03000e+03}, | |
| {8.00000e+02, 1.50000e+03}, | |
| {8.00000e+02, 1.80000e+03}, | |
| {8.00000e+02, 2.10000e+03}, | |
| {8.00000e+02, 2.40000e+03}, | |
| {8.00000e+02, 2.60000e+03}, | |
| {8.00000e+02, 2.70000e+03}, | |
| {8.00000e+02, 3.00000e+03}, | |
| {8.00000e+02, 3.30000e+03}, | |
| {8.00000e+02, 3.60000e+03}, | |
| {9.00000e+02, 3.00000e+02}, | |
| {9.00000e+02, 6.00000e+02}, | |
| {9.00000e+02, 1.50000e+03}, | |
| {9.00000e+02, 1.80000e+03}, | |
| {9.00000e+02, 2.10000e+03}, | |
| {9.00000e+02, 2.40000e+03}, | |
| {9.00000e+02, 2.70000e+03}, | |
| {9.00000e+02, 3.00000e+03}, | |
| {9.00000e+02, 3.30000e+03}, | |
| {9.00000e+02, 3.60000e+03}, | |
| {1.00000e+03, 3.00000e+02}, | |
| {1.00000e+03, 6.00000e+02}, | |
| {1.00000e+03, 1.10000e+03}, | |
| {1.00000e+03, 1.50000e+03}, | |
| {1.00000e+03, 1.62900e+03}, | |
| {1.00000e+03, 1.80000e+03}, | |
| {1.00000e+03, 2.10000e+03}, | |
| {1.00000e+03, 2.40000e+03}, | |
| {1.00000e+03, 2.60000e+03}, | |
| {1.00000e+03, 2.70000e+03}, | |
| {1.00000e+03, 3.00000e+03}, | |
| {1.00000e+03, 3.30000e+03}, | |
| {1.00000e+03, 3.60000e+03}, | |
| {1.10000e+03, 3.00000e+02}, | |
| {1.10000e+03, 6.00000e+02}, | |
| {1.10000e+03, 7.00000e+02}, | |
| {1.10000e+03, 9.00000e+02}, | |
| {1.10000e+03, 1.50000e+03}, | |
| {1.10000e+03, 1.80000e+03}, | |
| {1.10000e+03, 2.10000e+03}, | |
| {1.10000e+03, 2.40000e+03}, | |
| {1.10000e+03, 2.70000e+03}, | |
| {1.10000e+03, 3.00000e+03}, | |
| {1.10000e+03, 3.30000e+03}, | |
| {1.10000e+03, 3.60000e+03}, | |
| {1.20000e+03, 3.00000e+02}, | |
| {1.20000e+03, 6.00000e+02}, | |
| {1.20000e+03, 1.50000e+03}, | |
| {1.20000e+03, 1.70000e+03}, | |
| {1.20000e+03, 1.80000e+03}, | |
| {1.20000e+03, 2.10000e+03}, | |
| {1.20000e+03, 2.40000e+03}, | |
| {1.20000e+03, 2.70000e+03}, | |
| {1.20000e+03, 3.00000e+03}, | |
| {1.20000e+03, 3.30000e+03}, | |
| {1.20000e+03, 3.60000e+03}, | |
| {1.30000e+03, 3.00000e+02}, | |
| {1.30000e+03, 6.00000e+02}, | |
| {1.30000e+03, 7.00000e+02}, | |
| {1.30000e+03, 1.13000e+03}, | |
| {1.30000e+03, 1.50000e+03}, | |
| {1.30000e+03, 1.80000e+03}, | |
| {1.30000e+03, 2.10000e+03}, | |
| {1.30000e+03, 2.20000e+03}, | |
| {1.30000e+03, 2.40000e+03}, | |
| {1.30000e+03, 2.70000e+03}, | |
| {1.30000e+03, 3.00000e+03}, | |
| {1.30000e+03, 3.30000e+03}, | |
| {1.30000e+03, 3.60000e+03}, | |
| {1.40000e+03, 3.00000e+02}, | |
| {1.40000e+03, 6.00000e+02}, | |
| {1.40000e+03, 9.30000e+02}, | |
| {1.40000e+03, 1.50000e+03}, | |
| {1.40000e+03, 1.80000e+03}, | |
| {1.40000e+03, 2.00000e+03}, | |
| {1.40000e+03, 2.10000e+03}, | |
| {1.40000e+03, 2.40000e+03}, | |
| {1.40000e+03, 2.50000e+03}, | |
| {1.40000e+03, 2.70000e+03}, | |
| {1.40000e+03, 2.82000e+03}, | |
| {1.40000e+03, 2.90000e+03}, | |
| {1.40000e+03, 3.00000e+03}, | |
| {1.40000e+03, 3.30000e+03}, | |
| {1.40000e+03, 3.60000e+03}, | |
| {1.50000e+03, 1.50000e+03}, | |
| {1.50000e+03, 1.80000e+03}, | |
| {1.50000e+03, 1.90000e+03}, | |
| {1.50000e+03, 2.10000e+03}, | |
| {1.50000e+03, 2.40000e+03}, | |
| {1.50000e+03, 2.70000e+03}, | |
| {1.50000e+03, 2.80000e+03}, | |
| {1.50000e+03, 2.86000e+03}, | |
| {1.50000e+03, 3.00000e+03}, | |
| {1.50000e+03, 3.30000e+03}, | |
| {1.50000e+03, 3.60000e+03}, | |
| {1.60000e+03, 1.10000e+03}, | |
| {1.60000e+03, 1.30000e+03}, | |
| {1.60000e+03, 1.50000e+03}, | |
| {1.60000e+03, 1.80000e+03}, | |
| {1.60000e+03, 2.10000e+03}, | |
| {1.60000e+03, 2.40000e+03}, | |
| {1.60000e+03, 2.70000e+03}, | |
| {1.60000e+03, 3.00000e+03}, | |
| {1.60000e+03, 3.30000e+03}, | |
| {1.60000e+03, 3.60000e+03}, | |
| {1.70000e+03, 1.20000e+03}, | |
| {1.70000e+03, 1.50000e+03}, | |
| {1.70000e+03, 1.80000e+03}, | |
| {1.70000e+03, 2.10000e+03}, | |
| {1.70000e+03, 2.40000e+03}, | |
| {1.70000e+03, 3.60000e+03}, | |
| {1.80000e+03, 3.00000e+02}, | |
| {1.80000e+03, 6.00000e+02}, | |
| {1.80000e+03, 1.23000e+03}, | |
| {1.80000e+03, 1.50000e+03}, | |
| {1.80000e+03, 1.80000e+03}, | |
| {1.80000e+03, 2.10000e+03}, | |
| {1.80000e+03, 2.40000e+03}, | |
| {1.90000e+03, 3.00000e+02}, | |
| {1.90000e+03, 6.00000e+02}, | |
| {1.90000e+03, 3.00000e+03}, | |
| {1.90000e+03, 3.52000e+03}, | |
| {2.00000e+03, 3.00000e+02}, | |
| {2.00000e+03, 3.70000e+02}, | |
| {2.00000e+03, 6.00000e+02}, | |
| {2.00000e+03, 8.00000e+02}, | |
| {2.00000e+03, 9.00000e+02}, | |
| {2.00000e+03, 1.00000e+03}, | |
| {2.00000e+03, 1.10000e+03}, | |
| {2.00000e+03, 1.20000e+03}, | |
| {2.00000e+03, 1.30000e+03}, | |
| {2.00000e+03, 1.40000e+03}, | |
| {2.00000e+03, 1.50000e+03}, | |
| {2.00000e+03, 1.60000e+03}, | |
| {2.00000e+03, 1.70000e+03}, | |
| {2.00000e+03, 1.80000e+03}, | |
| {2.00000e+03, 1.90000e+03}, | |
| {2.00000e+03, 2.00000e+03}, | |
| {2.00000e+03, 2.10000e+03}, | |
| {2.00000e+03, 2.20000e+03}, | |
| {2.00000e+03, 2.30000e+03}, | |
| {2.00000e+03, 2.40000e+03}, | |
| {2.00000e+03, 2.50000e+03}, | |
| {2.00000e+03, 2.60000e+03}, | |
| {2.00000e+03, 2.70000e+03}, | |
| {2.00000e+03, 2.80000e+03}, | |
| {2.00000e+03, 2.90000e+03}, | |
| {2.00000e+03, 3.00000e+03}, | |
| {2.00000e+03, 3.10000e+03}, | |
| {2.00000e+03, 3.50000e+03}, | |
| {2.10000e+03, 3.00000e+02}, | |
| {2.10000e+03, 6.00000e+02}, | |
| {2.10000e+03, 3.20000e+03}, | |
| {2.20000e+03, 3.00000e+02}, | |
| {2.20000e+03, 4.69000e+02}, | |
| {2.20000e+03, 6.00000e+02}, | |
| {2.20000e+03, 3.20000e+03}, | |
| {2.30000e+03, 3.00000e+02}, | |
| {2.30000e+03, 6.00000e+02}, | |
| {2.30000e+03, 3.40000e+03}, | |
| {2.40000e+03, 3.00000e+02}, | |
| {2.40000e+03, 6.00000e+02}, | |
| {2.40000e+03, 2.10000e+03}, | |
| {2.50000e+03, 3.00000e+02}, | |
| {2.50000e+03, 8.00000e+02}, | |
| {2.60000e+03, 4.00000e+02}, | |
| {2.60000e+03, 5.00000e+02}, | |
| {2.60000e+03, 8.00000e+02}, | |
| {2.60000e+03, 9.00000e+02}, | |
| {2.60000e+03, 1.00000e+03}, | |
| {2.60000e+03, 1.10000e+03}, | |
| {2.60000e+03, 1.20000e+03}, | |
| {2.60000e+03, 1.30000e+03}, | |
| {2.60000e+03, 1.40000e+03}, | |
| {2.60000e+03, 1.50000e+03}, | |
| {2.60000e+03, 1.60000e+03}, | |
| {2.60000e+03, 1.70000e+03}, | |
| {2.60000e+03, 1.80000e+03}, | |
| {2.60000e+03, 1.90000e+03}, | |
| {2.60000e+03, 2.00000e+03}, | |
| {2.60000e+03, 2.10000e+03}, | |
| {2.60000e+03, 2.20000e+03}, | |
| {2.60000e+03, 2.30000e+03}, | |
| {2.60000e+03, 2.40000e+03}, | |
| {2.60000e+03, 2.50000e+03}, | |
| {2.60000e+03, 2.60000e+03}, | |
| {2.60000e+03, 2.70000e+03}, | |
| {2.60000e+03, 2.80000e+03}, | |
| {2.60000e+03, 2.90000e+03}, | |
| {2.60000e+03, 3.00000e+03}, | |
| {2.60000e+03, 3.10000e+03}, | |
| {2.60000e+03, 3.40000e+03}, | |
| {2.70000e+03, 7.00000e+02}, | |
| {2.70000e+03, 8.00000e+02}, | |
| {2.70000e+03, 9.00000e+02}, | |
| {2.70000e+03, 1.00000e+03}, | |
| {2.70000e+03, 1.10000e+03}, | |
| {2.70000e+03, 1.20000e+03}, | |
| {2.70000e+03, 1.30000e+03}, | |
| {2.70000e+03, 1.40000e+03}, | |
| {2.70000e+03, 1.50000e+03}, | |
| {2.70000e+03, 1.60000e+03}, | |
| {2.70000e+03, 1.70000e+03}, | |
| {2.70000e+03, 1.80000e+03}, | |
| {2.70000e+03, 1.90000e+03}, | |
| {2.70000e+03, 2.00000e+03}, | |
| {2.70000e+03, 2.10000e+03}, | |
| {2.70000e+03, 2.20000e+03}, | |
| {2.70000e+03, 2.30000e+03}, | |
| {2.70000e+03, 2.50000e+03}, | |
| {2.70000e+03, 2.60000e+03}, | |
| {2.70000e+03, 2.70000e+03}, | |
| {2.70000e+03, 2.80000e+03}, | |
| {2.70000e+03, 2.90000e+03}, | |
| {2.70000e+03, 3.00000e+03}, | |
| {2.70000e+03, 3.10000e+03}, | |
| {2.70000e+03, 3.20000e+03}, | |
| {2.70000e+03, 3.30000e+03}, | |
| {2.70000e+03, 3.40000e+03}, | |
| {2.70000e+03, 3.50000e+03}, | |
| {2.70000e+03, 3.60000e+03}, | |
| {2.70000e+03, 3.70000e+03}, | |
| {2.70000e+03, 3.80000e+03}, | |
| {2.80000e+03, 9.00000e+02}, | |
| {2.80000e+03, 1.13000e+03}, | |
| {2.90000e+03, 4.00000e+02}, | |
| {2.90000e+03, 5.00000e+02}, | |
| {2.90000e+03, 1.40000e+03}, | |
| {2.90000e+03, 2.40000e+03}, | |
| {2.90000e+03, 3.00000e+03}, | |
| {3.00000e+03, 7.00000e+02}, | |
| {3.00000e+03, 8.00000e+02}, | |
| {3.00000e+03, 9.00000e+02}, | |
| {3.00000e+03, 1.00000e+03}, | |
| {3.00000e+03, 1.10000e+03}, | |
| {3.00000e+03, 1.20000e+03}, | |
| {3.00000e+03, 1.30000e+03}, | |
| {3.00000e+03, 1.50000e+03}, | |
| {3.00000e+03, 1.60000e+03}, | |
| {3.00000e+03, 1.70000e+03}, | |
| {3.00000e+03, 1.80000e+03}, | |
| {3.00000e+03, 1.90000e+03}, | |
| {3.00000e+03, 2.00000e+03}, | |
| {3.00000e+03, 2.10000e+03}, | |
| {3.00000e+03, 2.20000e+03}, | |
| {3.00000e+03, 2.30000e+03}, | |
| {3.00000e+03, 2.50000e+03}, | |
| {3.00000e+03, 2.60000e+03}, | |
| {3.00000e+03, 2.70000e+03}, | |
| {3.00000e+03, 2.80000e+03}, | |
| {3.00000e+03, 2.90000e+03}, | |
| {3.00000e+03, 3.00000e+03}, | |
| {3.00000e+03, 3.10000e+03}, | |
| {3.00000e+03, 3.20000e+03}, | |
| {3.00000e+03, 3.30000e+03}, | |
| {3.00000e+03, 3.40000e+03}, | |
| {3.00000e+03, 3.50000e+03}, | |
| {3.00000e+03, 3.60000e+03}, | |
| {3.00000e+03, 3.70000e+03}, | |
| {3.00000e+03, 3.80000e+03}, | |
| {1.50000e+02, 3.50000e+03}, | |
| {1.50000e+02, 3.55000e+03}, | |
| {4.69000e+02, 2.55000e+03}, | |
| {4.69000e+02, 3.35000e+03}, | |
| {4.69000e+02, 3.45000e+03}, | |
| {5.40000e+02, 2.33000e+03}, | |
| {5.40000e+02, 2.43000e+03}, | |
| {6.20000e+02, 3.65000e+03}, | |
| {6.20000e+02, 3.70900e+03}, | |
| {7.50000e+02, 2.55000e+03}, | |
| {8.50000e+02, 5.20000e+02}, | |
| {8.50000e+02, 7.00000e+02}, | |
| {8.50000e+02, 2.28000e+03}, | |
| {9.39000e+02, 7.40000e+02}, | |
| {9.50000e+02, 2.22000e+03}, | |
| {9.10000e+02, 2.60000e+03}, | |
| {1.05000e+03, 1.05000e+03}, | |
| {1.15000e+03, 1.35000e+03}, | |
| {1.17000e+03, 2.28000e+03}, | |
| {1.22000e+03, 2.21000e+03}, | |
| {1.35000e+03, 7.50000e+02}, | |
| {1.35000e+03, 1.70000e+03}, | |
| {1.35000e+03, 2.14000e+03}, | |
| {1.45000e+03, 7.70000e+02}, | |
| {1.55000e+03, 3.00000e+02}, | |
| {1.55000e+03, 5.00000e+02}, | |
| {1.55000e+03, 1.85000e+03}, | |
| {1.65000e+03, 1.05000e+03}, | |
| {1.69000e+03, 2.68000e+03}, | |
| {1.71000e+03, 3.10000e+02}, | |
| {1.71000e+03, 5.10000e+02}, | |
| {1.75000e+03, 7.50000e+02}, | |
| {1.79000e+03, 2.58000e+03}, | |
| {1.72000e+03, 2.61000e+03}, | |
| {1.79000e+03, 3.33000e+03}, | |
| {1.72000e+03, 3.40900e+03}, | |
| {1.82900e+03, 2.70000e+03}, | |
| {1.82900e+03, 2.80000e+03}, | |
| {1.82900e+03, 3.45000e+03}, | |
| {2.06000e+03, 1.65000e+03}, | |
| {2.05000e+03, 3.15000e+03}, | |
| {2.17000e+03, 1.90000e+03}, | |
| {2.11000e+03, 2.00000e+03}, | |
| {2.12000e+03, 2.75000e+03}, | |
| {2.15000e+03, 3.25000e+03}, | |
| {2.29000e+03, 1.40000e+03}, | |
| {2.22000e+03, 2.82000e+03}, | |
| {2.28000e+03, 3.25000e+03}, | |
| {2.39000e+03, 1.30000e+03}, | |
| {2.32000e+03, 1.50000e+03}, | |
| {2.45000e+03, 7.10000e+02}, | |
| {2.62000e+03, 3.65000e+03}, | |
| {2.75000e+03, 5.20000e+02}, | |
| {2.76000e+03, 2.36000e+03}, | |
| {2.85000e+03, 2.20000e+03}, | |
| {2.85000e+03, 2.70000e+03}, | |
| {2.85000e+03, 3.35000e+03}, | |
| {2.93000e+03, 9.50000e+02}, | |
| {2.95000e+03, 1.75000e+03}, | |
| {2.95000e+03, 2.05000e+03}, | |
| {5.20000e+02, 3.20000e+03}, | |
| {2.30000e+03, 3.50000e+03}, | |
| {2.32000e+03, 3.15000e+03}, | |
| {5.30000e+02, 2.10000e+03}, | |
| {2.55000e+03, 7.10000e+02}, | |
| {7.50000e+02, 4.90000e+02}, | |
| {0.00000e+00, 0.00000e+00} | |
| }; | |
| // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/pcb442.opt.tour.gz | |
| // (optimal tour, 1-based) | |
| const int Opt[N]={ | |
| 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 53, | |
| 52, 51, 83, 84, 85, 381, 382, 86, 54, 21, 22, 55, 87, 378, 88, 56, 23, 24, | |
| 25, 26, 27, 28, 29, 30, 31, 32, 376, 377, 33, 65, 64, 63, 62, 61, 60, 59, | |
| 58, 57, 89, 90, 91, 92, 93, 101, 111, 123, 133, 146, 158, 169, 182, 197, | |
| 196, 195, 194, 181, 168, 157, 145, 144, 391, 132, 122, 110, 121, 385, 109, | |
| 120, 388, 131, 143, 156, 167, 180, 193, 192, 204, 216, 225, 233, 408, 409, | |
| 412, 413, 404, 217, 205, 206, 207, 208, 218, 219, 209, 198, 183, 170, 159, | |
| 147, 134, 124, 112, 436, 94, 95, 379, 96, 380, 97, 98, 384, 383, 113, 125, | |
| 135, 148, 160, 171, 184, 199, 210, 220, 226, 411, 410, 414, 237, 265, 437, | |
| 275, 423, 438, 272, 420, 268, 416, 264, 236, 263, 262, 261, 422, 419, 260, | |
| 259, 258, 257, 256, 255, 254, 253, 418, 417, 252, 251, 250, 415, 249, 248, | |
| 247, 246, 245, 244, 243, 242, 241, 407, 228, 235, 240, 267, 271, 270, 274, | |
| 277, 426, 280, 440, 308, 309, 283, 284, 310, 339, 311, 285, 286, 312, 340, | |
| 313, 287, 288, 314, 315, 316, 290, 289, 424, 421, 425, 291, 317, 318, 292, | |
| 293, 319, 320, 294, 295, 321, 322, 296, 278, 297, 323, 430, 429, 324, 298, | |
| 299, 300, 325, 326, 301, 302, 327, 328, 303, 304, 329, 330, 305, 306, 331, | |
| 332, 333, 432, 334, 307, 335, 336, 427, 337, 338, 375, 374, 373, 372, 371, | |
| 370, 369, 368, 345, 367, 366, 365, 431, 364, 363, 362, 344, 361, 360, 359, | |
| 435, 358, 357, 356, 434, 355, 354, 353, 343, 352, 351, 350, 349, 433, 348, | |
| 347, 346, 342, 341, 428, 282, 281, 279, 276, 273, 269, 266, 239, 238, 234, | |
| 227, 405, 406, 401, 400, 185, 172, 161, 149, 136, 126, 114, 103, 102, 441, | |
| 104, 115, 386, 127, 387, 389, 116, 138, 392, 152, 151, 137, 150, 162, 173, | |
| 186, 174, 396, 399, 187, 175, 211, 403, 221, 229, 212, 230, 222, 213, 200, | |
| 188, 176, 163, 393, 153, 139, 140, 128, 117, 105, 106, 107, 118, 129, 141, | |
| 154, 165, 164, 397, 177, 189, 201, 202, 402, 214, 223, 231, 232, 224, 215, | |
| 203, 190, 191, 398, 178, 179, 395, 394, 166, 155, 142, 390, 130, 119, 108, | |
| 439, 82, 50, 49, 81, 100, 80, 48, 47, 79, 78, 46, 45, 77, 99, 76, 44, 43, | |
| 75, 74, 42, 41, 73, 72, 40, 39, 71, 70, 38, 37, 69, 68, 36, 35, 67, 66, 34, | |
| 442 | |
| }; | |
| }; // class pcb442 | |
| void errlog(int i, int v, const std::string& trailer = "") { | |
| if (i >= 0) std::cerr << i << ": "; | |
| std::cerr << v << " " << trailer << "\r"; | |
| if (i < 0) std::cerr << "\n"; | |
| } | |
| #ifdef ezxdisp | |
| const int mar = 8; | |
| const int wid = 3000; | |
| const int hei = 3800; | |
| const int Div = 5; | |
| void mp(int x, int y, int s, std::pair<int, int>& a) { | |
| a = std::pair<int, int>(mar+x/Div+s*(2*mar+wid/Div), mar+(hei-y)/Div); | |
| } | |
| void city(const std::pair<int, int>& c, ezx_t *e) { | |
| ezx_fillrect_2d(e, c.first-2, c.second-2, c.first+2, c.second+2, &ezx_black); | |
| } | |
| void city2(const std::pair<int, int>& c, ezx_t *e) { | |
| ezx_fillrect_2d(e, c.first-4, c.second-4, c.first+4, c.second+4, &ezx_orange); | |
| } | |
| void city2a(const std::pair<int, int>& c, ezx_t *e) { | |
| ezx_fillrect_2d(e, c.first-6, c.second-6, c.first+6, c.second+6, &ezx_orange); | |
| } | |
| template <typename config, typename urn> | |
| void ezx_tours(pcb442<config, urn>& P, config& T, config& R, urn& U, config& N, | |
| int ret, int mut, ezx_t*& e) { | |
| bool initial = (ret == std::numeric_limits<int>::min()); | |
| ezx_wipe(e); | |
| ezx_line_2d(e, wid/Div+2*mar, hei/Div+2*mar, wid/Div+2*mar, 0, &ezx_black, 1); | |
| ezx_line_2d(e, 2*(wid/Div+2*mar), hei/Div+2*mar, 2*(wid/Div+2*mar), 0, | |
| &ezx_black, 1); | |
| ezx_str_2d(e, 5, 10, const_cast<char *>(reinterpret_cast<const char*> | |
| (initial ? (mut == 0 ? "RR_all" : "minimum found") | |
| : "previous")), &ezx_black); | |
| std::stringstream s2; | |
| s2 << P.cost(T); | |
| ezx_str_2d(e, 50, hei/Div+mar, | |
| const_cast<char *>(reinterpret_cast<const char*> | |
| (s2.str().c_str())), &ezx_black); | |
| if (ret != std::numeric_limits<int>::min()) { | |
| s2 = std::stringstream(); | |
| s2 << mut << ": "; | |
| if (ret == std::numeric_limits<int>::max()) | |
| s2 << "ran"; | |
| else | |
| s2 << (ret >= 0 ? "rad" : "seq"); | |
| s2 << "(" << U.size() << ") "; | |
| s2 << P.cost(R); | |
| ezx_str_2d(e, 50+wid/Div+2*mar, hei/Div+mar, | |
| const_cast<char*>(reinterpret_cast<const char *> | |
| (s2.str().c_str())), &ezx_black); | |
| s2 = std::stringstream(); | |
| s2 << P.cost(N) << " (" << P.cost(N) - P.cost(T) << ")"; | |
| ezx_str_2d(e, 50+2*(wid/Div+2*mar), hei/Div+mar, | |
| const_cast<char*>(reinterpret_cast<const char *> | |
| (s2.str().c_str())), &ezx_black); | |
| ezx_str_2d(e, 5+wid/Div+2*mar, 10, | |
| const_cast<char*>(reinterpret_cast<const char*>("ruined")), | |
| &ezx_black); | |
| ezx_str_2d(e, 5+2*(wid/Div+2*mar), 10, | |
| const_cast<char*>(reinterpret_cast<const char*>("recreated")), | |
| &ezx_black); | |
| } else if (mut != 0) { | |
| ezx_str_2d(e, 5+wid/Div+2*mar, 10, | |
| const_cast<char*>(reinterpret_cast<const char*> | |
| ("global minimum")), &ezx_black); | |
| s2 = std::stringstream(); | |
| s2 << P.cost(R); | |
| ezx_str_2d(e, 50+wid/Div+2*mar, hei/Div+mar, | |
| const_cast<char*>(reinterpret_cast<const char *> | |
| (s2.str().c_str())), &ezx_black); | |
| } | |
| if (ret != std::numeric_limits<int>::max() && ret >= 0) { | |
| std::pair<int, int> c; | |
| mp(P.C[ret][0], P.C[ret][1], 0, c); | |
| int r = P.D[ret][P.rad_nxt[ret][U.size()-1]]; | |
| ezx_circle_2d(e, c.first, c.second, r/Div, &ezx_orange, 2); | |
| ezx_circle_2d(e, c.first+2*(wid/Div+2*mar), c.second, r/Div, | |
| &ezx_orange, 2); | |
| } | |
| int prev = T.back(); | |
| std::pair<int, int> p; | |
| mp(P.C[prev][0], P.C[prev][1], 0, p); | |
| std::for_each(T.begin(), T.end(), [&p, &e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 0, c); | |
| ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1); | |
| p = c; | |
| }); | |
| int hig = (ret < 0) ? -(1 + ret) | |
| : (ret != std::numeric_limits<int>::max()) ? ret : -1; | |
| std::for_each(U.begin(), U.end(), [hig, &e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 1, c); | |
| if (i == hig) { city2a(c, e); } else { city2(c, e); } | |
| }); | |
| prev = R.back(); | |
| mp(P.C[prev][0], P.C[prev][1], 1, p); | |
| std::for_each(R.begin(), R.end(), [&p, &e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 1, c); | |
| ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1); | |
| p = c; | |
| }); | |
| prev = N.back(); | |
| mp(P.C[prev][0], P.C[prev][1], 2, p); | |
| std::for_each(N.begin(), N.end(), [&p, &e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 2, c); | |
| ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1); | |
| p = c; | |
| }); | |
| std::for_each(T.begin(), T.end(), [ret, &e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 0, c); | |
| city(c, e); | |
| if (ret != std::numeric_limits<int>::min()) { | |
| mp(P.C[i][0], P.C[i][1], 2, c); | |
| city(c, e); | |
| } | |
| }); | |
| std::for_each(R.begin(), R.end(), [&e, &P](int i) { | |
| std::pair<int, int> c; | |
| mp(P.C[i][0], P.C[i][1], 1, c); | |
| city(c, e); | |
| }); | |
| // ezx_window_name(e, "57123 -> 53207 -> 51219"); | |
| ezx_redraw(e); | |
| usleep(10000); | |
| } | |
| #endif | |
| template <typename config, typename urn> | |
| void RR() { | |
| std::pair<urn, urn> Us; | |
| config T; | |
| pcb442<config, urn> P(0.3, 1.0/3, 1.0/3, 1.0/3); | |
| #ifdef ezxdisp | |
| ezx_t *e = ezx_init(3*(wid/Div+2*mar), hei/Div+2*mar, | |
| const_cast<char*>(reinterpret_cast<const char*> | |
| ("TSP greedy Ruin and Recreate"))); | |
| #endif | |
| P.RR_all(T, Us); | |
| errlog(0, P.cost(T), "RR_all() [" + i2s(_sum) + "us]"); | |
| _sum = 0; | |
| #ifdef ezxdisp | |
| config RC; | |
| urn UC; | |
| std::cerr << "\n"; | |
| ezx_tours(P, T, RC, Us.first, RC, std::numeric_limits<int>::min(), 0, e); | |
| (void) ezx_pushbutton(e, NULL, NULL); | |
| #endif | |
| for (int i = 1; i <= 100000; ++i) { | |
| config R = T; | |
| std::pair<urn, urn> UsR; | |
| for (typename config::iterator it = R.begin(); it != R.end(); ++it) { | |
| R[*it] = it; | |
| UsR.second.push_back(*it); | |
| } | |
| #ifdef ezxdisp | |
| int ret = P.ruin(R, UsR); | |
| RC = R; | |
| UC = UsR.first; | |
| #else | |
| (void) P.ruin(R, UsR); | |
| #endif | |
| auto oldsum = _sum; | |
| P.recreate(R, UsR); | |
| if (P.cost(R) < P.cost(T)) { | |
| P.last += " (" + i2s(_sum - oldsum) + "us) "; | |
| errlog(i, P.cost(R), P.last); | |
| #ifdef ezxdisp | |
| std::cerr << "\n"; | |
| ezx_tours(P, T, RC, UC, R, ret, i, e); | |
| while (1 != ezx_pushbutton(e, NULL, NULL)) { usleep(10000); } | |
| #endif | |
| T = R; | |
| UsR.second.clear(); | |
| for (typename config::iterator it = T.begin(); it != T.end(); ++it) { | |
| T[*it] = it; | |
| UsR.second.push_back(*it); | |
| } | |
| } | |
| } | |
| errlog(-1, P.cost(T), "local minimum found (after 100,000 greedy mutations)"); | |
| errlog(-1, (_sum+500)/1000, "ms (only recreate)"); | |
| // print(T); | |
| /* | |
| std::cout << "["; | |
| bool first = true; | |
| std::for_each(T.begin(), T.end(), [&first, P](int i) { | |
| if (!first) std::cout << ","; else first = false; | |
| std::cout << "[" << P.C[i][0] << "," << P.C[i][1] << "]"; | |
| }); | |
| std::cout << "]\n"; | |
| */ | |
| config O; // P.Opt is 1-based | |
| for (int i = 0; i < P.N; ++i) { int c = P.Opt[i] - 1; O.push_back(c); } | |
| errlog(-1, P.cost(O), "global minimum"); | |
| config S = T; | |
| S.sort(); | |
| urn V(S.begin(), S.end()); | |
| for (int i = 0; i < P.N; ++i) assert(V[i] == i); | |
| #ifdef ezxdisp | |
| config dummy; | |
| ezx_tours(P, T, O, Us.first, dummy, std::numeric_limits<int>::min(), -1, e); | |
| while (3 != ezx_pushbutton(e, NULL, NULL)) { usleep(10000); } | |
| #endif | |
| } | |
| int main(int argc, char *argv[]) { | |
| srandom(argc > 1 ? atoi(argv[1]) : time(0)); | |
| RR<random_access_list<int, 442>, std::vector<int>>(); | |
| return 0; | |
| } |
- adds optional tour display output if compiling with "-Dezxdisp" option
Screenshot of a radial ruin that got accepted with cost reduction of 219:
- left: previous config, with circle indicating the cities being removed in ruin mutation
- middle: ruined config (removed cities displayed orange and bigger)
- right: recreated config; circle allows to easily compare the changes done
(click two times on screenshot to see it in original size)
- improvements in tour display
- radial ruin center city is highlighted
- sequential ruin start city is highlighted
- left click continues optimization (only when compiled with
-Dezxdisp) - on last display with found and global minimum, right click ends
If you want to see without compiling, here is interactive online demo:
https://stamm-wilbrandt.de/RR/greedy/TSP/pcb442
- now added enhanced console output discussed in this previous comment
- in addition append the microseconds used between
_startand_stopfor just the reported mutation
As discussed in previous comment, running with nohup has advantages, see below.
For 442 cities TSP problem the time between _start and _stop is in range 12..865 microseconds on AMD 7950X CPU. The 865us time happened for a recreate of 60 cities:
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | head -3
12
15
19
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | tail -3
206
213
865
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep 865us
112: 54281 ran(60) (865us)
pi@raspberrypi5:~/tsp $
pi@raspberrypi5:~/tsp $ rm nohup.out
pi@raspberrypi5:~/tsp $ nohup time ./pcb442 1001
nohup: ignoring input and appending output to 'nohup.out'
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out
0: 58634 RR_all()
2: 58603 ran(6) (13us)
3: 58292 ran(49) (90us)
4: 58210 seq(279,13) (22us)
8: 58133 ran(74) (134us)
10: 57882 ran(34) (62us)
14: 57857 seq(217,118) (181us)
15: 57528 rad(129,11) (20us)
16: 57028 ran(131) (226us)
21: 56906 ran(100) (161us)
22: 56788 ran(83) (147us)
23: 56730 rad(148,82) (144us)
25: 56420 ran(68) (121us)
34: 56418 ran(36) (65us)
41: 56411 ran(24) (43us)
42: 56249 rad(351,114) (173us)
45: 56233 ran(17) (33us)
50: 56014 rad(174,39) (68us)
54: 55589 rad(236,60) (101us)
62: 55445 rad(306,49) (81us)
71: 55444 seq(197,45) (75us)
72: 55288 rad(188,94) (148us)
74: 55135 rad(316,13) (22us)
75: 55119 ran(24) (40us)
76: 55094 ran(56) (98us)
80: 55023 ran(32) (60us)
81: 54891 seq(320,30) (52us)
83: 54875 ran(103) (171us)
90: 54703 ran(24) (47us)
94: 54595 rad(141,44) (81us)
104: 54530 seq(215,55) (91us)
109: 54394 seq(19,28) (51us)
112: 54281 ran(60) (106us)
113: 54199 ran(27) (50us)
116: 54191 seq(261,56) (95us)
118: 54139 ran(52) (92us)
122: 54137 ran(115) (188us)
126: 54133 ran(115) (189us)
133: 54056 ran(97) (167us)
137: 53979 ran(114) (189us)
140: 53968 ran(9) (18us)
150: 53926 ran(49) (87us)
151: 53885 ran(113) (182us)
163: 53863 ran(9) (18us)
165: 53740 ran(47) (81us)
183: 53718 ran(128) (203us)
188: 53624 ran(117) (192us)
195: 53579 rad(122,32) (54us)
204: 53540 ran(99) (165us)
211: 53464 rad(343,29) (50us)
234: 53368 ran(90) (155us)
235: 53296 ran(58) (101us)
236: 53214 ran(17) (32us)
252: 53175 rad(377,48) (82us)
268: 53106 ran(59) (106us)
269: 53035 seq(286,19) (34us)
280: 53018 ran(43) (77us)
313: 53005 ran(64) (112us)
319: 53002 rad(35,55) (93us)
320: 52955 rad(77,62) (98us)
327: 52906 ran(36) (66us)
328: 52873 ran(66) (117us)
329: 52761 ran(15) (29us)
332: 52759 seq(21,17) (29us)
351: 52628 ran(59) (106us)
361: 52613 ran(105) (171us)
372: 52466 rad(103,71) (117us)
378: 52463 rad(222,27) (45us)
389: 52352 rad(224,49) (79us)
393: 52300 ran(87) (153us)
409: 52289 ran(125) (204us)
419: 52225 ran(100) (171us)
433: 52158 ran(100) (168us)
451: 52143 ran(98) (168us)
525: 52074 seq(27,42) (71us)
561: 52011 ran(59) (105us)
568: 51969 ran(102) (168us)
583: 51932 ran(83) (141us)
587: 51877 ran(32) (84us)
650: 51866 ran(51) (92us)
651: 51845 ran(78) (135us)
664: 51795 ran(7) (12us)
728: 51772 ran(108) (174us)
756: 51769 ran(16) (26us)
983: 51736 rad(35,38) (60us)
2422: 51714 ran(94) (156us)
2473: 51693 ran(61) (108us)
2549: 51667 ran(63) (111us)
2733: 51645 ran(94) (158us)
2796: 51618 ran(27) (51us)
2972: 51615 ran(104) (174us)
4422: 51587 seq(43,14) (26us)
4434: 51562 rad(395,24) (42us)
4435: 51547 ran(42) (78us)
4450: 51511 ran(119) (193us)
4470: 51499 ran(38) (65us)
4482: 51461 seq(208,37) (67us)
4514: 51440 ran(62) (105us)
4520: 51430 ran(40) (72us)
4967: 51418 ran(79) (132us)
14228: 51375 rad(199,26) (44us)
14280: 51236 ran(87) (145us)
14508: 51233 ran(70) (121us)
56088: 51217 seq(126,22) (38us)
56141: 51204 ran(35) (62us)
56416: 51099 rad(195,23) (37us)
62316: 51085 rad(194,23) (39us)
51085 local minimum found (after 100,000 greedy mutations)
10824 ms (only recreate)
50778 global minimum
14.44user 0.00system 0:14.45elapsed 99%CPU (0avgtext+0avgdata 4752maxresident)k
0inputs+64outputs (1major+205minor)pagefaults 0swaps
pi@raspberrypi5:~/tsp $
I created a copy for usa13509 problem and
- adjusted N to 13509
- used 13509 coordinates from that problem
- had to create the distance matrix in a loop executed 13509 times doing
D[from] = new int[N]; - did only 500 mutations instead of 100,000 because so slow
This time for 13509 cities TSP problem the time between _start and _stop is in range 1818..436904 microseconds on AMD 7950X CPU. The 437ms time ( AMD 7950X CPU runs single thread with 5.5GHz boost clock) happened for a recreate of 3,992 of the 13,509 cities (29.6%, RR is configured for ruins of sizes up to 30%) — time to parallelize the recreate step to 60 CUs or even 3,840 cores of a Vega20 type GPU ...
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | head -3
1818
9618
9764
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | tail -3
367500
413481
436904
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep 436904us
16: 22289370 ran(3992) (436904us)
hermann@7950x:~/tsp$
Cost of 22,769,244 after initial RR_all(), global optimum is 19,982,859. Reduction of more than a million after only 283 mutations:
hermann@7950x:~/tsp$ rm nohup.out
hermann@7950x:~/tsp$ nohup time ./usa13509 1001
nohup: ignoring input and appending output to 'nohup.out'
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out
0: 22769244 RR_all()
2: 22765777 ran(169) (18435us)
3: 22710358 ran(1478) (154853us)
6: 22702144 rad(2358,946) (101035us)
8: 22569463 ran(2254) (242485us)
9: 22456757 ran(3109) (330930us)
10: 22427246 ran(1023) (119492us)
13: 22321845 ran(3285) (367500us)
16: 22289370 ran(3992) (436904us)
18: 22278027 ran(409) (52408us)
21: 22225775 ran(3051) (353126us)
22: 22188101 ran(2531) (300199us)
25: 22151904 ran(2065) (249684us)
33: 22130237 ran(1355) (168983us)
34: 22112424 ran(1096) (138036us)
41: 22100784 ran(718) (91791us)
45: 22092895 ran(515) (66138us)
53: 22076233 ran(1897) (232294us)
65: 22054523 ran(1945) (237061us)
68: 22029934 ran(3643) (413481us)
75: 22025914 ran(708) (90857us)
76: 22000413 ran(1699) (208322us)
79: 21985921 ran(1215) (152274us)
80: 21974989 ran(968) (122176us)
83: 21962460 ran(3137) (365057us)
90: 21954339 ran(715) (91891us)
91: 21947134 ran(470) (60755us)
99: 21938819 ran(1112) (140036us)
101: 21926642 ran(2555) (303714us)
106: 21919494 ran(736) (93581us)
107: 21918693 ran(95) (12411us)
112: 21908416 ran(1823) (222600us)
113: 21899485 ran(814) (103152us)
114: 21896743 ran(203) (26330us)
118: 21891733 ran(1589) (195413us)
119: 21887518 ran(1158) (144560us)
124: 21882051 ran(526) (67645us)
129: 21879981 ran(310) (40219us)
130: 21879708 seq(2691,14) (1818us)
133: 21874860 ran(2946) (345715us)
134: 21858133 ran(1035) (130577us)
140: 21854653 ran(256) (33407us)
141: 21849446 ran(772) (98776us)
147: 21840523 ran(1241) (155529us)
150: 21829999 ran(1494) (185652us)
157: 21828723 ran(119) (15685us)
158: 21828668 ran(75) (9764us)
159: 21821311 ran(627) (80444us)
163: 21814301 ran(267) (34749us)
174: 21811846 ran(400) (51587us)
200: 21811431 ran(532) (68092us)
213: 21809716 ran(219) (28603us)
215: 21808489 ran(465) (60223us)
233: 21808218 ran(129) (16899us)
235: 21804165 ran(1759) (216274us)
236: 21803798 ran(504) (65137us)
239: 21798560 ran(602) (77141us)
243: 21794699 ran(1337) (167115us)
257: 21794546 ran(78) (10459us)
265: 21791608 ran(878) (111211us)
268: 21785236 ran(1799) (219712us)
273: 21783947 ran(185) (24456us)
280: 21776516 ran(1285) (159687us)
283: 21764905 ran(1340) (166724us)
287: 21763982 ran(417) (53700us)
288: 21762024 ran(937) (118219us)
290: 21761845 ran(440) (56808us)
295: 21760941 rad(2532,146) (17893us)
316: 21760360 ran(210) (27203us)
327: 21751934 ran(1086) (137088us)
329: 21750825 ran(444) (57319us)
358: 21750289 ran(87) (11473us)
365: 21746224 ran(1183) (149084us)
370: 21743695 rad(12903,178) (22473us)
375: 21741929 ran(148) (19338us)
400: 21736507 ran(1152) (144793us)
422: 21731731 ran(965) (121790us)
443: 21729399 ran(1539) (190556us)
453: 21729023 ran(640) (82394us)
458: 21727568 ran(291) (37828us)
469: 21723650 ran(1903) (232104us)
486: 21722996 ran(1421) (177341us)
500: 21722657 ran(73) (9618us)
...
Revision 8:
On the path to parallelization of Recreate step. New class template <typename val, int N> class random_access_list was needed so that a GPU CU or core can do computation wrt its id. The [] operator of config returns the iterator in internal list with *C[c] == c.
Use of std::find() as well as std::advance() completely eliminated.
Part of the improvements was an unavoidable change in the way the random cities get created for radial ruin. Therefore same seed produces different result. With new code random seed of 205 even results in cost less than 51,000. Below will be used as something to compare against and detect unwanted changes in the future:
pi@raspberrypi5:~/tsp $ make
g++ -O3 -std=c++17 -Wall -Wextra -pedantic pcb442.cpp -o pcb442 -lstdc++ -lm
pi@raspberrypi5:~/tsp $ rm nohup.out
pi@raspberrypi5:~/tsp $ nohup time ./pcb442 205
nohup: ignoring input and appending output to 'nohup.out'
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out
0: 58473 RR_all() [474us]
3: 58347 ran(49) (97us)
4: 58282 seq(363,13) (25us)
8: 58094 ran(74) (127us)
9: 57833 ran(102) (171us)
13: 57568 ran(108) (184us)
16: 57308 ran(131) (209us)
21: 57113 ran(100) (167us)
22: 56541 ran(83) (144us)
28: 56521 seq(370,70) (131us)
30: 56321 rad(272,23) (41us)
33: 56210 ran(45) (94us)
34: 56074 ran(36) (72us)
53: 55990 ran(63) (110us)
54: 55899 rad(238,60) (100us)
62: 55893 rad(31,49) (82us)
65: 55874 ran(64) (114us)
67: 55861 seq(264,25) (44us)
68: 55757 ran(120) (197us)
75: 55718 ran(24) (44us)
76: 55591 ran(56) (99us)
79: 55568 ran(40) (74us)
80: 55565 ran(32) (58us)
83: 55529 ran(103) (171us)
85: 55479 seq(164,46) (78us)
99: 55408 ran(37) (68us)
107: 55320 ran(4) (8us)
111: 55261 seq(409,73) (682us)
112: 55179 ran(60) (737us)
113: 55167 ran(27) (259us)
126: 55150 ran(115) (491us)
134: 55072 ran(34) (61us)
140: 55069 ran(9) (20us)
144: 55036 seq(360,87) (152us)
147: 55013 ran(41) (73us)
165: 54914 ran(47) (89us)
200: 54894 ran(18) (34us)
203: 54753 rad(71,16) (28us)
213: 54720 ran(8) (13us)
231: 54675 ran(110) (182us)
263: 54668 rad(204,17) (27us)
265: 54583 ran(29) (50us)
279: 54581 ran(101) (165us)
281: 54511 seq(222,20) (35us)
291: 54330 ran(117) (195us)
299: 54306 ran(52) (93us)
316: 54241 ran(7) (14us)
333: 54184 ran(108) (176us)
384: 54149 rad(111,33) (59us)
400: 54141 ran(38) (70us)
528: 54045 seq(172,42) (74us)
587: 54023 ran(32) (59us)
642: 54014 ran(131) (208us)
683: 53902 ran(33) (62us)
704: 53871 ran(74) (131us)
727: 53868 ran(80) (138us)
733: 53862 ran(51) (91us)
769: 53838 rad(293,15) (23us)
789: 53797 ran(99) (165us)
790: 53758 seq(224,51) (83us)
791: 53717 ran(34) (63us)
838: 53688 ran(57) (99us)
869: 53671 ran(94) (157us)
883: 53646 ran(70) (124us)
902: 53598 ran(101) (172us)
969: 53573 ran(60) (103us)
980: 53572 ran(71) (127us)
984: 53559 rad(359,19) (33us)
997: 53477 rad(80,29) (46us)
1016: 53444 ran(9) (18us)
1110: 53432 rad(233,12) (22us)
1137: 53429 seq(399,4) (7us)
1169: 52966 rad(367,70) (113us)
1196: 52917 seq(257,11) (17us)
1229: 52904 ran(55) (100us)
1284: 52893 ran(120) (196us)
1309: 52842 ran(98) (167us)
1319: 52831 ran(33) (60us)
1373: 52811 ran(51) (90us)
1375: 52744 ran(63) (110us)
1437: 52662 ran(57) (99us)
1561: 52656 ran(54) (94us)
1712: 52638 ran(38) (70us)
2030: 52610 rad(368,42) (68us)
2054: 52580 ran(59) (103us)
2221: 52559 ran(27) (48us)
2319: 52556 ran(49) (91us)
3024: 52355 rad(27,120) (185us)
3041: 52348 ran(26) (47us)
3049: 52337 ran(54) (98us)
3062: 52285 ran(96) (160us)
3102: 52261 ran(66) (112us)
3114: 52239 ran(77) (130us)
3151: 52168 ran(29) (54us)
3191: 52142 rad(19,38) (62us)
3275: 52121 ran(74) (126us)
3325: 52099 ran(78) (133us)
6147: 52090 seq(391,8) (15us)
7652: 52085 rad(383,29) (50us)
7840: 52059 rad(416,9) (16us)
7875: 52056 ran(82) (139us)
10129: 52055 seq(110,19) (31us)
10239: 51987 ran(77) (130us)
10272: 51973 ran(95) (161us)
10445: 51964 rad(313,41) (69us)
10497: 51948 ran(21) (36us)
10558: 51890 ran(55) (98us)
11130: 51882 seq(341,57) (89us)
11271: 51829 ran(70) (121us)
11309: 51823 ran(25) (45us)
11653: 51801 ran(117) (186us)
11822: 51779 seq(276,10) (18us)
11845: 51744 ran(85) (143us)
11858: 51724 ran(49) (87us)
11991: 51721 ran(75) (126us)
12214: 51698 rad(20,30) (50us)
13224: 51685 rad(172,41) (71us)
13254: 51670 ran(56) (101us)
13288: 51541 ran(69) (116us)
13302: 51514 ran(24) (42us)
13615: 51502 ran(106) (176us)
13760: 51496 seq(125,12) (23us)
15054: 51419 seq(101,34) (60us)
15074: 51417 ran(75) (134us)
15147: 51399 ran(88) (150us)
15845: 51393 ran(43) (78us)
16216: 51384 seq(170,23) (37us)
16232: 51363 ran(79) (136us)
18350: 51315 rad(295,76) (117us)
18388: 51313 rad(299,30) (51us)
18563: 51268 rad(361,28) (48us)
27451: 51238 rad(360,15) (25us)
32949: 51232 seq(297,18) (31us)
36311: 51231 seq(360,28) (45us)
74444: 51181 rad(242,47) (79us)
74532: 51179 ran(40) (70us)
74581: 51174 ran(60) (103us)
74646: 51027 rad(286,30) (49us)
74695: 50969 ran(7) (13us)
80526: 50953 seq(420,27) (46us)
80558: 50947 ran(10) (19us)
96003: 50940 ran(105) (173us)
96948: 50933 seq(290,28) (48us)
50933 local minimum found (after 100,000 greedy mutations)
10832 ms (only recreate)
50778 global minimum
13.35user 0.00system 0:13.37elapsed 99%CPU (0avgtext+0avgdata 4672maxresident)k
0inputs+64outputs (1major+199minor)pagefaults 0swaps
pi@raspberrypi5:~/tsp $
TODO:
There is a lot of copying, current tour config T is copied into R, that gets ruined and recreated, and if improvement (greedy) T=R is copied again.
In little example code I have solution already, just need to integrate here.
Instead of erasing iterator from list, splice the single iterator at end of a helper list.
Before doing so, push_back the successor of it onto a vector.
These operations happen on T, no copy R.
In case cost did not improve after ruin and recreate step, the vector and auxiliary list allow for "T.restore()" operation, with runtime proportional to the items removed.
Much more to come, but not in this gist. Development of this gist is stopped, no further updates.
Code is split up, and a loader was added allowing for different problems.
In addition that repo has 111 TSP problems with 108 corresponding optimal tours.
New repo:
https://github.com/Hermann-SW/RR/tree/main?tab=readme-ov-file#ruin-and-recreate
So many new features, and Mona Lisa ...
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Revision 4:
The last item indicates improvement potential when doing those calculations inside of AMD GPU HIP kernel code.