――Ein Sportturnier findet in ** 8 Ländern ** statt. Angenommen, Sie spielen 4 Tage lang 4 Spiele. ――Es wird davon ausgegangen, dass Sie das Beliebtheitsranking des vorherigen Rufs kennen. ―― Versuchen Sie so weit wie möglich, das beliebte Paar in der zweiten Halbzeit zusammenzubringen, und erstellen Sie einen Zeitplan, in dem Sie sich bis zum Ende unwohl fühlen.
Lösen wir dieses Problem mit Kombinationsoptimierung.
Die Variablen seien 0-1 Variablen, die die Kombination für Land 1, Land 2 und Tag "auswählen und auswählen" darstellen.
Das "Gewicht des Spiels an einem Tag (k) mit zwei Ländern (i, j)", das der Variablen entspricht, ist wie folgt. Durch die Maximierung der Summe dieser Gewichte werden "Übereinstimmungen zwischen Ländern mit niedrigeren Rankings" priorisiert.
| Maximieren Sie | $ \ sum_i {weight _i x_i} $ | Summe der Gewichte |
| Variablen | $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Kandidat $ | Gibt an, ob dieser Kandidat ausgewählt werden soll td> |
| Einschränkungen | $ \ sum_ {i \ in j, k Paare ~~~~~} {x_i} = 1 ~ ~ \ forall j, k \ in \ mbox {country} $ | Ein und dasselbe Paar |
| $ \ sum_ {i \ in Tag k einschließlich Land j ~~~~~~~~~~~~~} {x_i} = 1 ~ ~ \ forall j \ in \ mbox {Land }, \ forall k \ in \ mbox {Tag} $ | Am selben Tag ein |
Erstellen Sie zunächst eine Tabelle mit Kombinationen.
python3
import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'Italien Niederlande Japan Korea Thailand Dominica Republik Peru Kasachstan'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} #Ländername → Rangfolge
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='Land 1 Land 2 Tage Gewicht'.split())
a[:3]
>>>
Land 1 Land 2 Tage Gewicht
0 Italien Niederlande 0 0.5
1 Italien Niederlande 1 1.0
2 Italien Niederlande 2 2.0
Formulieren und lösen wir es.
python3
m = LpProblem(sense=LpMaximize) #Mathematisches Modell
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] #Variable
m += lpDot(a.Gewicht, a.Var) #Zielfunktion
for _, b in a.groupby(['Land 1', 'Land 2']):
m += lpSum(b.Var) == 1 #Einer in derselben Gruppe
for s, i in product(ss, range(7)):
#Das gleiche Land, eines am selben Tag
m += lpSum(a.query('(Land 1=="{0}" |Land 2=="{0}") &Tag=={1}'.format(s, i)).Var) == 1
m.solve() #Lösung
a['Val'] = a.Var.apply(value) #Ergebnis
#Anzeige
for i, b in a.groupby('Tag'):
print(i+1, 'Tag')
for _, r in b[b.Val > 0].iterrows():
print(' %*s - %s'%(8-len(r.Land 1), r.Land 1, r.Land 2))
>>>
Erster Tag
Italien-Kasachstan
Niederlande-Peru
Japan-Dominikanische Republik
Korea-Thailand
der 2. Tag
Italien-Peru
Niederlande-Kasachstan
Japan-Thailand
Korea-Dominikanische Republik
Dritter Tag
Italien-Dominikanische Republik
Niederlande-Thailand
Japan-Kasachstan
Korea-Peru
Tag 4
Italien-Thailand
Niederlande-Dominikanische Republik
Japan-Peru
Korea-Kasachstan
Tag 5
Italien-Korea
Niederlande-Japan
Thailand-Kasachstan
Dominikanische Republik-Peru
Tag 6
Italien-Japan
Niederlande-Korea
Thailand-Peru
Dominikanische Republik-Kasachstan
Tag 7
Italien-Niederlande
Japan-Korea
Thailand-Dominikanische Republik
Peru-Kasachstan
Der Zeitplan für jeden Tag wurde ausgegeben.
Ein anderes Verfahren kann eine Kombination von Stärkeunterschieden in der ersten Hälfte und eine Kombination von Wettbewerbsstärkeunterschieden in der zweiten Hälfte sein.
Vorübergehend mache ich meinen letzten Python-bezogenen Beitrag auf Arukas.
das ist alles
Recommended Posts