[DOCKER] Découvrez les dates du tournoi fou

Introduction

―― Un tournoi sportif se tiendra dans ** 8 pays **. Supposons que vous jouiez à 4 jeux pendant 7 jours. ――Il est supposé que vous connaissez le classement de popularité de la réputation précédente. ―― Autant que possible, essayez de faire correspondre la paire populaire en seconde période et créez un programme qui vous mettra mal à l'aise jusqu'à la fin.

Résolvons ce problème avec Optimisation de combinaison.

Formulation

Soit les variables 0-1 variables qui représentent «choisir et choisir» la combinaison pour le pays 1, le pays 2 et le jour.

Aussi, le "poids du match un jour (k) avec deux pays (i, j)" correspondant à la variable est le suivant. En maximisant la somme de ces pondérations, les «correspondances entre les pays ayant un classement inférieur» seront priorisées. $ Poids = \ frac {2 ^ k} {i rang \ fois j rang} $

Maximiser $ \ sum_i {weight _i x_i} $ somme des poids
Variables $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Candidate $ Sélection de ce candidat td>
Contraintes $ \ sum_ {i \ in j, k paires ~~~~~} {x_i} = 1 ~ ~ \ forall j, k \ in \ mbox {country} $ Un dans la même paire
$ \ sum_ {i \ in Day k y compris le pays j ~~~~~~~~~~~~~} {x_i} = 1 ~ ~ \ forall j \ in \ mbox {Country }, \ forall k \ in \ mbox {day} $ Le même jour, un
Ce problème est un type de problème de planification.

Essayez-le avec Python

Commencez par créer un tableau de combinaisons.

python3


import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'Italie Pays-Bas Japon Corée Thaïlande République dominicaine Pérou Kazakhstan'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} #Nom du pays → classement
a = pd.DataFrame([(i, j, k, 2**k/rnk[i]/rnk[j]) for i, j in combinations(ss, 2)
                  for k in range(7)], columns='Pays 1 Pays 2 jours Poids'.split())
a[:3]
>>>
Pays 1 Pays 2 jours Poids
0 Italie Pays-Bas 0 0.5
1 Italie Pays-Bas 1 1.0
2 Italie Pays-Bas 2 2.0

Formulons et résolvons-le.

python3


m = LpProblem(sense=LpMaximize) #Modèle mathématique
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] #variable
m += lpDot(a.poids, a.Var) #Fonction objective
for _, b in a.groupby(['Pays 1', 'Pays 2']):
    m += lpSum(b.Var) == 1 #Un dans le même groupe
for s, i in product(ss, range(7)):
    #Le même pays, un le même jour
    m += lpSum(a.query('(Pays 1=="{0}" |Pays 2=="{0}") &journée=={1}'.format(s, i)).Var) == 1
m.solve() #Solution
a['Val'] = a.Var.apply(value) #résultat
#afficher
for i, b in a.groupby('journée'):
    print(i+1, 'journée')
    for _, r in b[b.Val > 0].iterrows():
        print(' %*s - %s'%(8-len(r.Pays 1), r.Pays 1, r.Pays 2))
>>>
Premier jour
Italie-Kazakhstan
Pays-Bas-Pérou
Japon-République Dominicaine
Corée-Thaïlande
le 2ème jour
Italie-Pérou
Pays-Bas-Kazakhstan
Japon-Thaïlande
Corée-République Dominicaine
Troisième jour
Italie-République Dominicaine
Pays-Bas-Thaïlande
Japon-Kazakhstan
Corée-Pérou
Jour 4
Italie-Thaïlande
Pays-Bas-République Dominicaine
Japon-Pérou
Corée-Kazakhstan
Jour 5
Italie-Corée
Pays-Bas-Japon
Thaïlande-Kazakhstan
République Dominicaine-Pérou
Jour 6
Italie-Japon
Pays-Bas-Corée
Thaïlande-Pérou
République Dominicaine-Kazakhstan
Jour 7
Italie-Pays-Bas
Japon-Corée
Thaïlande-République Dominicaine
Pérou-Kazakhstan

Le programme de chaque jour était sorti.

Une autre méthode peut être une combinaison de différences de force dans la première moitié et une combinaison de différences de force concurrentielle dans la seconde moitié.

Bonus

Temporairement, je lance mon dernier article sur Python sur Arukas.

  • https://qiita-jupyter.arukascloud.io/ ――Après avoir ouvert chaque article, sélectionnez une cellule et appuyez sur la touche Entrée tout en maintenant la touche Maj enfoncée pour exécuter.
  • Ceci est l'image originale ci-dessus.
    • https://hub.docker.com/r/tsutomu7/qiita-jupyter/

c'est tout

Recommended Posts