189 lines
5.0 KiB
C++
189 lines
5.0 KiB
C++
|
#include "common.h"
|
||
|
|
||
|
auto hwElsGenV(tsp::Solution const& solution, RNG& rng) {
|
||
|
return Descent{}(Move2Opt{}(solution, rng));
|
||
|
}
|
||
|
|
||
|
auto hwElsInner(tsp::Solution const& solution, std::vector<RNG>& rngs, std::size_t id, std::size_t nCore) {
|
||
|
std::size_t n = ELS_GEN;
|
||
|
std::size_t maxThreads = nCore;
|
||
|
|
||
|
std::size_t const nThreads = std::min<std::size_t>(maxThreads, ELS_GEN);
|
||
|
|
||
|
std::vector<std::thread> threads{nThreads-1};
|
||
|
std::size_t const step = n/nThreads;
|
||
|
std::size_t const remainBase = n - step*nThreads;
|
||
|
std::size_t remain = remainBase;
|
||
|
|
||
|
auto run = [&solution,&rngs](tsp::Solution& out, std::size_t id, std::size_t k) {
|
||
|
tsp::Solution best{};
|
||
|
|
||
|
if(k)
|
||
|
best = hwElsGenV(solution, rngs[id]);
|
||
|
for(std::size_t i = 1; i < k; ++i) {
|
||
|
tsp::Solution current = hwElsGenV(solution, rngs[id+i]);
|
||
|
best = selectMin(std::move(best), std::move(current));
|
||
|
}
|
||
|
|
||
|
out = std::move(best);
|
||
|
};
|
||
|
|
||
|
std::size_t start{};
|
||
|
std::vector<tsp::Solution> bests(nThreads);
|
||
|
|
||
|
for(std::size_t i = 0; i < nThreads-1; ++i) {
|
||
|
std::size_t offset = !!remain;
|
||
|
remain -= offset;
|
||
|
threads[i] = std::thread{run, std::ref(bests[i]), id+start, step+offset};
|
||
|
start += step+offset;
|
||
|
}
|
||
|
|
||
|
run(bests[nThreads-1], id+start, step);
|
||
|
|
||
|
for(auto& thread: threads) thread.join();
|
||
|
|
||
|
tsp::Solution best;
|
||
|
// best = *std::min_element(std::begin(solutions), std::end(solutions));
|
||
|
if(nThreads) best = std::move(bests[0]);
|
||
|
for(std::size_t i = 1; i < nThreads; ++i)
|
||
|
best = selectMin(std::move(best), std::move(bests[i]));
|
||
|
|
||
|
return best;
|
||
|
}
|
||
|
|
||
|
auto hwEls(tsp::Solution const& solution, std::vector<RNG>& rngs, std::size_t id, std::size_t nCore) {
|
||
|
tsp::Solution best = Descent{}(solution);
|
||
|
|
||
|
for(std::size_t i = 0; i < ELS_ITER_MAX; ++i) {
|
||
|
tsp::Solution current = hwElsInner(best, rngs, id, nCore);
|
||
|
best = selectMin(std::move(best), std::move(current));
|
||
|
}
|
||
|
|
||
|
return best;
|
||
|
}
|
||
|
|
||
|
auto hwGraspGen(tsp::Problem const& problem, std::vector<RNG>& rngs, std::size_t id, std::size_t nCore = 1) {
|
||
|
return hwEls(rgreedy()(problem, rngs[id]), rngs, id, nCore);
|
||
|
}
|
||
|
|
||
|
/* *** */
|
||
|
|
||
|
auto hwGraspEls(tsp::Problem const& problem, std::vector<RNG>& rngs) {
|
||
|
tsp::Solution best;
|
||
|
|
||
|
auto graspIter = [&](tsp::Problem const& problem, tsp::Solution& s, std::size_t id) {
|
||
|
tsp::Solution cur = hwGraspGen(problem, rngs, id);
|
||
|
s = selectMin(std::move(s), std::move(cur));
|
||
|
};
|
||
|
|
||
|
if(GRASP_N) {
|
||
|
auto graspInit = [&](tsp::Problem const& problem, tsp::Solution& s) {
|
||
|
s = hwGraspGen(problem, rngs, 0);
|
||
|
};
|
||
|
#ifdef SUBTIME
|
||
|
timeit(RUSAGE_THREAD, "[GRASP] ", graspInit, problem, best);
|
||
|
#else
|
||
|
graspInit(problem, best);
|
||
|
#endif
|
||
|
}
|
||
|
|
||
|
for(std::size_t i = 1; i < GRASP_N; ++i) {
|
||
|
#ifdef SUBTIME
|
||
|
timeit(RUSAGE_THREAD, "[GRASP] ", graspIter, problem, best, i*ELS_GEN);
|
||
|
#else
|
||
|
graspIter(problem, best, i*ELS_GEN);
|
||
|
#endif
|
||
|
}
|
||
|
|
||
|
return best;
|
||
|
}
|
||
|
|
||
|
template<std::size_t K>
|
||
|
auto hwGraspElsPar(tsp::Problem const& problem, std::vector<RNG>& rngs) {
|
||
|
std::size_t const n = GRASP_N;
|
||
|
std::size_t const maxThreads = K;
|
||
|
|
||
|
std::size_t const nThreads = std::min<std::size_t>(maxThreads, n);
|
||
|
std::size_t const cores = maxThreads/nThreads;
|
||
|
|
||
|
std::vector<std::thread> threads(nThreads-1);
|
||
|
std::size_t const step = n/nThreads;
|
||
|
std::size_t const remainBase = n - step*nThreads;
|
||
|
std::size_t remain = remainBase;
|
||
|
|
||
|
auto iter0 = [&problem,&rngs](tsp::Solution& best, std::size_t id, std::size_t cores) {
|
||
|
best = hwGraspGen(problem, rngs, id, cores);
|
||
|
};
|
||
|
auto iter = [&problem,&rngs](tsp::Solution& best, std::size_t id, std::size_t cores) {
|
||
|
tsp::Solution current = hwGraspGen(problem, rngs, id, cores);
|
||
|
best = selectMin(std::move(best), std::move(current));
|
||
|
};
|
||
|
|
||
|
auto run = [&](tsp::Solution& out, std::size_t id, std::size_t k, std::size_t cores) {
|
||
|
tsp::Solution best{};
|
||
|
|
||
|
if(k) {
|
||
|
#ifdef SUBTIME
|
||
|
timeit(RUSAGE_THREAD, "[GRASP] ", iter0, best, id*ELS_GEN, cores);
|
||
|
#else
|
||
|
iter0(best, id*ELS_GEN, cores);
|
||
|
#endif
|
||
|
}
|
||
|
|
||
|
for(std::size_t i = 1; i < k; ++i) {
|
||
|
#ifdef SUBTIME
|
||
|
timeit(RUSAGE_THREAD, "[GRASP] ", iter, best, (id+i)*ELS_GEN, cores);
|
||
|
#else
|
||
|
iter(best, (id+1)*ELS_GEN, cores);
|
||
|
#endif
|
||
|
}
|
||
|
|
||
|
out = std::move(best);
|
||
|
};
|
||
|
|
||
|
std::size_t start{};
|
||
|
std::vector<tsp::Solution> bests(nThreads);
|
||
|
|
||
|
for(std::size_t i = 0; i < nThreads-1; ++i) {
|
||
|
std::size_t offset = !!remain;
|
||
|
remain -= offset;
|
||
|
threads[i] = std::thread{run, std::ref(bests[i]), start, step+offset, cores};
|
||
|
start += step+offset;
|
||
|
}
|
||
|
|
||
|
run(bests[nThreads-1], start, step, cores);
|
||
|
|
||
|
for(std::thread& thread: threads) thread.join();
|
||
|
|
||
|
tsp::Solution best;
|
||
|
if(nThreads) best = std::move(bests[0]);
|
||
|
for(std::size_t i = 1; i < nThreads; ++i)
|
||
|
best = selectMin(std::move(best), std::move(bests[i]));
|
||
|
|
||
|
return best;
|
||
|
}
|
||
|
|
||
|
/* *** */
|
||
|
|
||
|
tsp::Solution hw_seq_v(tsp::Problem const& p, RNG& seeder, Arguments const&) {
|
||
|
std::size_t n = GRASP_N * ELS_GEN;
|
||
|
|
||
|
std::vector<RNG> rngs;
|
||
|
rngs.reserve(n);
|
||
|
for(std::size_t i = 0; i < n; ++i)
|
||
|
rngs.emplace_back(seeder());
|
||
|
|
||
|
return hwGraspEls(p, rngs);
|
||
|
}
|
||
|
|
||
|
tsp::Solution hw_par_v(tsp::Problem const& p, RNG& seeder, Arguments const&) {
|
||
|
std::size_t n = GRASP_N * ELS_GEN;
|
||
|
|
||
|
std::vector<RNG> rngs;
|
||
|
rngs.reserve(n);
|
||
|
for(std::size_t i = 0; i < n; ++i)
|
||
|
rngs.emplace_back(seeder());
|
||
|
|
||
|
return hwGraspElsPar<NTHREADS>(p, rngs);
|
||
|
}
|