Ein perfekter Plan

Postkarte - Fussball

 

Wir bestimmen als erstes die Menge der Teampaarungen, die auf die einzelnen Termine und Spielfelder im Turnier verteilt werden sollen. Teams werden durch Zahlen 1 – 6 repräsentiert, jedes Turnierspiel durch ein Paar (i, j) mit i < j. So kommt jede Zweierkombination der Zahlen 1 – 6 genau einmal vor, d. h. jedes Team spielt genau einmal gegen jedes andere. Es gibt insgesamt 15 Paare, die man aus der folgenden Matrix ablesen kann:

  2 3 4 5 6
1 (1,2) (1,3) (1,4) (1,5) (1,6)
2   (2,3) (2,4) (2,5) (2,6)
3     (3,4) (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)

also von oben links nach unten rechts aufgelistet: (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6)

Für das Verteilen der 15 Paare auf die 16 Termine gelten nun die folgenden Regeln: Da kein Team mehr als zweimal direkt nacheinander spielen darf und kein Team gleichzeitig gegen zwei andere Teams spielen kann, spielen immer 4 verschiedene Teams gleichzeitig und die anderen beiden Teams setzen aus. Welche Teams aussetzen, wechselt von Runde zu Runde ab und wiederholt sich dementsprechend alle 3 Runden. Wir können also schon einmal willkürlich festlegen, welche Teams jeweils aussetzen und ergänzen die Spielplan-Tabelle um eine entsprechende Spalte:

Runde Feld A Feld B Pause
1     5, 6
2     3, 4
3     1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4

Eine einfache Lösungsstrategie geht hier einfach alle Termine der Reihe nach durch und wählt in jedem Schritt das erste Paar aus der Menge der noch zu verteilenden Paare, das alle Regeln erfüllt.

Fangen wir also an: In Runde 1 pausieren 5 und 6, damit scheiden alle Paare mit 5 oder 6 für Feld A aus. Die entsprechenden Zeilen und Spalten sind in der Matrix der Spielpaare rot markiert. Liest man die Matrix von oben links an zeilenweise, findet man als erstes das Paar (1,2), das zu diesem Termin spielen kann (grün markiert).

Im ersten Schritt wird also das Paar (1,2) auf Feld A gelegt:

Runde Feld A Feld B Pause
1 (1,2)   5, 6
2     3, 4
3     1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1 (1,2) (1,3) (1,4) (1,5) (1,6)
2   (2,3) (2,4) (2,5) (2,6)
3     (3,4) (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)
 

Anschließend wird das Paar (1,2) aus der Matrix der noch zu verteilenden Paare entfernt.

Für Feld B scheiden im nächsten Schritt alle Paare mit 1 oder 2 zusätzlich aus, da Team 1 und 2 nicht zur selben Zeit auf Feld A und B spielen können. Das Paar (3,4) bleibt als einziges für diesen Termin übrig:

Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2     3, 4
3     1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4) (1,5) (1,6)
2   (2,3) (2,4) (2,5) (2,6)
3     (3,4) (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)

Im nächsten Schritt scheiden für Feld A alle übriggebliebenen Paare mit 3 oder 4 aus, da diese Teams in Runde 2 pausieren. Man findet nun (1,5) als erstes freies Paar für diesen Termin:

Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5)   3, 4
3     1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4) (1,5) (1,6)
2   (2,3) (2,4) (2,5) (2,6)
3       (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)

Für Feld B bleibt dann nur das Paar (2,6) übrig:

Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3     1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4)   (1,6)
2   (2,3) (2,4) (2,5) (2,6)
3       (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)

So geht es bis Runde 8 weiter, bis alle 15 Paare verteilt sind:

Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5)   1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4)   (1,6)
2   (2,3) (2,4) (2,5)  
3       (3,5) (3,6)
4       (4,5) (4,6)
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4     5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4)   (1,6)
2   (2,3) (2,4) (2,5)  
3         (3,6)
4       (4,5) (4,6)
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5)   1, 2
4 (1,3)   5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1   (1,3) (1,4)   (1,6)
2   (2,3) (2,4) (2,5)  
3         (3,6)
4       (4,5)  
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5     3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)   (1,6)
2   (2,3) (2,4) (2,5)  
3         (3,6)
4       (4,5)  
5         (5,6)

Runde

Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5)   1, 2
4 (1,3)   5, 6
5 (1,6)   3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)   (1,6)
2   (2,3)   (2,5)  
3         (3,6)
4       (4,5)  
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6     1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)    
2   (2,3)   (2,5)  
3         (3,6)
4       (4,5)  
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6 (3,6)   1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)    
2   (2,3)      
3         (3,6)
4       (4,5)  
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6 (3,6) (4,5) 1, 2
7     5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)    
2   (2,3)      
3          
4       (4,5)  
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6 (3,6) (4,5) 1, 2
7 (1,4)   5, 6
8     3, 4
 
  2 3 4 5 6
1     (1,4)    
2   (2,3)      
3          
4          
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6 (3,6) (4,5) 1, 2
7 (1,4) (2,3) 5, 6
8     3, 4
 
  2 3 4 5 6
1          
2   (2,3)      
3          
4          
5         (5,6)
Runde Feld A Feld B Pause
1 (1,2) (3,4) 5, 6
2 (1,5) (2,6) 3, 4
3 (3,5) (4,6) 1, 2
4 (1,3) (2,4) 5, 6
5 (1,6) (2,5) 3, 4
6 (3,6) (4,5) 1, 2
7 (1,4) (2,3) 5, 6
8 (5,6)   3, 4
 
  2 3 4 5 6
1          
2          
3          
4          
5         (5,6)

Das hier vorgestellte Lösungsverfahren gehört zu den sogenannten “Greedy”-Algorithmen, also den “gierigen” Algorithmen. Diese Verfahren basieren auf dem Prinzip, die aktuelle Teillösung in jedem Schritt “gierig” so zu erweitern, dass die folgende Teillösung zum Zeitpunkt der Wahl gültig ist bzw. den größten Gewinn erzielt. Das wird solange fortgeführt, bis eine Gesamtlösung erreicht ist oder man in eine Sackgasse läuft. In diesem Fall müsste man Schritte rückgängig machen und andere Entscheidungen fällen.

Für kleinere Spielplan-Probleme wie dieses eignet sich ein “Greedy”-Algorithmus in der Praxis ganz gut und kann sehr einfach als Computerprogramm umgesetzt werden.