Algoritme om maximaal te behalen positie te bepalen

[andre]

Hallo,

Ik probeer te ontdekken of het voor een voetbalteam mogelijk is om te achterhalen of dit team nog eerste kan worden.

Uitgangspunt is een poule met teams die allemaal een zeker aantal punten hebben behaald.
Een team krijgt per wedstrijd: 3 punten bij winst, 1 punt bij gelijkspel, 0 punten bij verlies.

Stel dat er 5 teams zijn: team A, B, C, D en E
Stel dat dit respectievelijk de huidige stand is: A=4, B=6, C=5, D=8, E=11
Stel dat ieder team nog een keer tegen ieder ander team moet spelen. (A-B, A-C, A-D, A-E, B-C, B-D, B-E, C-D, C-E, D-E)

Is het dan mogelijk om te achterhalen of bijv team A nog eerste kan worden in deze poule?

Voor een maximaal resultaat moet A alles winnen en komt dan op 4 * 3 = 12 + 4 = 16 punten
Als we dan voor een minimaal resultaat gaan bij de andere teams, is er dan geen enkel ander team meer dat hier overheen gaat met punten?

Ik ben heel erg benieuwd!

Groet,
Andre

[andre]

Wat ik zelf had bedacht was om voor iedere nog te spelen wedstrijd, waar team A niet in meespeelt, het volgende te hanteren:

Indien het verschil in punten tussen de twee teams >= 3, dan laten we het team met de laagste score winnen.
Het team met de laagste score krijgt er dan dus 3 punten bij en en het andere team 0.

Indien het verschil in punten tussen de twee teams < 3, dan laten we de twee teams gelijkspelen en krijgen beide teams 1 punt.

Dit dus met het idee om een zo laag mogelijk score van het beste team (buiten A) te verkrijgen.
Dan is het slechts een kwestie van deze score te vergelijken met de hoogst mogelijke score van team A.

Dit lijkt echter niet altijd goed te werken, waardoor er soms een onjuiste voorspelling uitrolt.
Bijvoorbeeld in het geval wanneer we 4 teams hebben A, B, C en D met punten: A=2, B=3, C=8, D=11
Afhankelijk van de speelvolgorde komt er dan een andere resultaat uit met bovengenoemde rekenregels.

Stel dat er ieder weekend twee wedstrijden zijn.
Hier de eerste volgorde:

A-D en B-C levert A=5, B=6, C=8, D=11
A-B en C-D levert A=8, B=6, C=11, D=11
A-C en B-D levert A=11, B=9, C=11, D=11

Hier een andere:

A-C en B-D levert A=5, B=6, C=8, D=11
A-D en B-C levert A=8, B=7, C=9, D=11
A-B en C-D levert A=11, B=7, C=10, D=12

Willen we weten of A nog eerste kan worden, dan is dat in de eerste berekening mogelijk (afhankelijk van doelsaldo). In de tweede berekening wordt A hooguit tweede.

Ik zoek dus een betere methode

[arie]

Een alternatieve strategie:

Ga uit van de eindstand van de competitie:
[1] je favoriete team moet maximaal scoren = alles winnen, bepaal de maximaal haalbare score
[2] de andere teams moeten op (maar bij voorkeur onder) die score blijven:
[-- 2a] laat ze eerst allemaal onderling gelijk spelen (dan heb je in totaal het minst aantal punten verdeeld over de overige teams)
[-- 2b] kijk dan wie er moet verliezen van wie (dus: wie heeft er te veel punten en wie mag er nog punten bij krijgen): de verliezer van die partij verliest 1 punt van zijn totaal, de winnaar van die partij wint 2 punten
Herhaal dit zo lang nodig (en mogelijk)


Voorbeeld:

Jouw laatste voorbeeld: A=2, B=3, C=8, D=11 en alle ploegen spelen nog 3 wedstrijden:
A kan maximaal 3 keer winnen dus 9 punten erbij krijgen, maximale eindscore A = 2 + 9 = 11 punten

De andere ploegen spelen elk nog 2 wedstrijden onderling.
Indien ze alles gelijk spelen, wordt hun eindscore
eind B = 3 + 2 = 5
eind C = 8 + 2 = 10
eind D = 11 + 2 = 13

D haalt op deze manier de meeste punten, die gaan we eerst verminderen:
D kan maximaal 2 punten verliezen, namelijk eerst verliezen van B (B wint en krijgt er 2 punten bij):
eind B = 5 + 2 = 7
eind C = 10
eind D = 13 - 1 = 12
(merk op: D heeft nu nog te veel punten)

Vervolgens moet D verliezen van C (de enige andere tegenstander):
eind B = 7
eind C = 10 + 2 = 12
eind D = 12 - 1 = 11
Minder dan 11 punten kan D niet halen.

Echter: nu heeft C 12 punten, maar die kunnen we vervolgens nog verlagen via de wedstrijd van C tegen B:
als B die wedstrijd wint, krijgt C een punt minder en B 2 punten erbij:
eind B = 7 + 2 = 9
eind C = 12 - 1 = 11
eind D = 11


PS: wil je dit probleem automatiseren (= hiervoor een computerprogramma schrijven)?

[andre]

Hallo Arie,

Leuke oplossing! Lijkt te werken, maar zoals je jezelf al afvraagt: hoe valt dit te programmeren? Worden dat niet veel te veel iteraties?

[andre]

Ik dacht even dat dit de oplossing was. Maar het lijkt niet te werken in bijvoorbeeld de volgende situatie:

Er zijn 5 teams, A t/m E.
Er zij nog maar drie wedstrijden te gaan: team A tegen team C, team A tegen team D en team B tegen team D.
In het kort: A-C, A-D, B-D
Team E wil weten of het nog kan winnen.

Stel dat na het toepassen van de regels (E wint alles en de overigen spelen gelijk) de volgende stand zou ontstaan:

Team A heeft 4 punten
Team B heeft 4 punten
Team C heeft 1 punt
Team D heeft 6 punten

Team E heeft 5 punten en vraagt zich of het nog kan winnen.

Nu is de eerste stap het verlagen van de punten van team D.
Maar dan moeten we kiezen uit de wedstrijd A-D en B-D.

Kiezen we voor A-D dan wordt de stand:

A: 6 punten
B: 4 punten
C: 1 punt
D: 5 punten

We kunnen dan de score van team A verlagen middels de wedstrijd tegen C:

A: 5 punten
B: 4 punten
C: 3 punten
D: 5 punten

Team E kan dan met een goed doelsaldo nog eerste worden.

-----------------

Kiezen we in het begin echter voor de wedstrijd B-D om de score van team D te verlagen dan wordt de stand:

A: 4 punten
B: 6 punten
C: 1 punt
D: 5 punten

De score van team B kunnen we echter niet verder verlagen, waardoor het lijkt alsof team E hooguit de tweede plaats kan bereiken.

[andre]

Zou je dit willen ondervangen door in een programma dit met backtracken op te lossen, dus een wedstrijd uitproberen en dat pad volgen, om daarna terug te komen en een ander pad in te slaan en zo alle paden en hun uitkomsten met elkaar te vergelijken. Dan gaat dit in het ergste geval uitkomen op ongeveer (2*n)! mogelijke paden om te volgen (met n teams en ieder tweetal team speelt thuis en uit tegen elkaar). Dat wordt al snel te veel.

[arie]

Met grotere aantallen teams en wedstrijden kom je inderdaad uit op een optimalisatieprobleem.
Daar zal je geschikte zoekmethoden op los moeten laten.
Die (2n)! lijkt me iets te pessimistisch: elke wedstrijd heeft 3 mogelijke uitkomsten, dit levert een zoekruimte van 3^n, maar dat is nog steeds erg groot.
Is het de bedoeling dat je een dergelijk zoekprogramma moet schrijven?