Вместо того, чтобы пробовать случайные перестановки, мы можем применить генетический алгоритм со случайным ключом (BRKGA). Этот общий метод оптимизации может найти решение для n = 7 только с четырьмя паузами на один матч, все разными игроками:
1 4 1
1 3
0 4
2 5
1 6
2 3
4 5
0 6
3 5
1 2
4 6
0 3
1 5
2 6
3 4
0 1
2 4
3 6
0 5
1 4
0 2
5 6
Код С++:
#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <tuple>
#include <utility>
#include <vector>
namespace {
constexpr int kNumPlayers = 7;
constexpr int kNumMatches = kNumPlayers * (kNumPlayers - 1) / 2;
class Solution {
public:
template <typename Generator> static Solution Random(Generator &generator);
template <typename Generator>
Solution MateWith(const Solution &that, Generator &generator) const;
std::array<std::tuple<int, int>, kNumMatches> Matches() const;
private:
Solution() = default;
std::array<double, kNumMatches> keys_;
};
template <typename Generator> Solution Solution::Random(Generator &generator) {
Solution solution;
std::uniform_real_distribution<double> uniform;
for (int k = 0; k < kNumMatches; k++) {
solution.keys_[k] = uniform(generator);
}
return solution;
}
template <typename Generator>
Solution Solution::MateWith(const Solution &that, Generator &generator) const {
Solution child;
std::bernoulli_distribution biased_coin(0.7);
for (int k = 0; k < kNumMatches; k++) {
child.keys_[k] = biased_coin(generator) ? this->keys_[k] : that.keys_[k];
}
return child;
}
std::array<std::tuple<int, int>, kNumMatches> Solution::Matches() const {
std::array<std::tuple<double, std::tuple<int, int>>, kNumMatches> rankings;
{
int k = 0;
for (int i = 0; i < kNumPlayers; i++) {
for (int j = i + 1; j < kNumPlayers; j++) {
rankings[k] = {keys_[k], {i, j}};
k++;
}
}
}
std::sort(rankings.begin(), rankings.end());
std::array<std::tuple<int, int>, kNumMatches> matches;
for (int k = 0; k < kNumMatches; k++) {
matches[k] = std::get<1>(rankings[k]);
}
return matches;
}
std::vector<std::tuple<int, int>>
Rests(const std::array<std::tuple<int, int>, kNumMatches> &matches) {
std::array<int, kNumMatches> last_match;
for (int k = 0; k < kNumMatches; k++) {
last_match[std::get<0>(matches[k])] = k - kNumMatches;
last_match[std::get<1>(matches[k])] = k - kNumMatches;
}
std::vector<std::tuple<int, int>> rests;
for (int k = 0; k < kNumMatches; k++) {
auto plays = [&](int i) {
rests.push_back({k - 1 - last_match[i], i});
last_match[i] = k;
};
plays(std::get<0>(matches[k]));
plays(std::get<1>(matches[k]));
}
return rests;
}
std::tuple<int, int, int>
Objective(const std::array<std::tuple<int, int>, kNumMatches> &matches) {
auto rests = Rests(matches);
int min_rest = std::get<0>(*std::min_element(rests.begin(), rests.end()));
std::array<int, kNumPlayers> player_to_min_rest_count;
std::fill(player_to_min_rest_count.begin(), player_to_min_rest_count.end(),
0);
for (auto [rest, player] : rests) {
if (rest == min_rest) {
player_to_min_rest_count[player]++;
}
}
return {-min_rest,
std::accumulate(player_to_min_rest_count.begin(),
player_to_min_rest_count.end(), 0),
*std::max_element(player_to_min_rest_count.begin(),
player_to_min_rest_count.end())};
}
std::vector<Solution> SortByFitness(const std::vector<Solution> &population) {
std::vector<std::tuple<std::tuple<int, int, int>, const Solution *>> tagged;
tagged.reserve(population.size());
for (const Solution &solution : population) {
tagged.push_back({Objective(solution.Matches()), &solution});
}
std::sort(tagged.begin(), tagged.end());
std::vector<Solution> sorted_population;
sorted_population.reserve(population.size());
for (auto [objective, solution] : tagged) {
sorted_population.push_back(*solution);
}
return sorted_population;
}
template <typename Generator> Solution BRKGA(Generator &generator) {
static constexpr int kRounds = 20000;
static constexpr int kNumEliteSolutions = 300;
static constexpr int kNumMatedSolutions = 600;
static constexpr int kNumRandomSolutions = 100;
static constexpr int kNumSolutions =
kNumEliteSolutions + kNumMatedSolutions + kNumRandomSolutions;
std::vector<Solution> population;
population.reserve(kNumSolutions);
for (int i = 0; i < kNumSolutions; i++) {
population.push_back(Solution::Random(generator));
}
for (int r = 0; r < kRounds; r++) {
population = SortByFitness(population);
std::vector<Solution> new_population;
new_population.reserve(kNumSolutions);
for (int i = 0; i < kNumEliteSolutions; i++) {
new_population.push_back(population[i]);
}
std::uniform_int_distribution<int> elite(0, kNumEliteSolutions - 1);
std::uniform_int_distribution<int> non_elite(kNumEliteSolutions,
kNumSolutions - 1);
for (int i = 0; i < kNumMatedSolutions; i++) {
int j = elite(generator);
int k = non_elite(generator);
new_population.push_back(
population[j].MateWith(population[k], generator));
}
for (int i = 0; i < kNumRandomSolutions; i++) {
new_population.push_back(Solution::Random(generator));
}
population = std::move(new_population);
}
return SortByFitness(population)[0];
}
void PrintSolution(const Solution &solution) {
auto matches = solution.Matches();
auto objective = Objective(matches);
std::cout << -std::get<0>(objective) << ' ' << std::get<1>(objective) << ' '
<< std::get<2>(objective) << '\n';
for (auto [i, j] : solution.Matches()) {
std::cout << i << ' ' << j << '\n';
}
}
} // namespace
int main() {
std::default_random_engine generator;
PrintSolution(BRKGA(generator));
}
person
David Eisenstat
schedule
29.01.2021
