Algoritme for holds mulige placeringer i en turnering

[Bertel Lund Hansen]

Hej alle

For sjovs skyld har jeg lavet et progranm der kan holde styr på
VM i fodbold. Det er relativt banalt.

Jeg har indført en farvning af holdene. Jeg er endt med 6 mulige
farver. Vi kan bruge bogstaver hvis det bliver nødvendigt at
betegne dem:
A Sikker 1.- eller 2.-plads, færdig med alle kampe
B Sikker 1.-plads, ikke færdig
C Sikker 2.-plads, ikke færdig
D Uafgjort, færdig
E Uafgjort, ikke færdig
F Ude uanset om færdig

Jeg har lavet en uperfekt algoritme hvor jeg for hvert hold
beregner bestcase og worstcase ved at oprette to arrays til
sortering. Begge arrays indeholder subarrays på formen:

array (score,måldiff,holdnr) // et array pr. hold.

I bestcase lægges holdenes opnåede værdier, men bedste
hypotetiske resultat for det hold hvis værdi skal findes.
Sorteringspositionen angiver den bedste placering som holdet har
mulighed for.

I worstcase lægges de bedst mulige værdier for holdene, men kun
opnåede resultater for det aktuelle hold.

Som hypotetisk målscore for en uspillet kamp bruger jeg 3-0.

Eksempel:

Hold Kampe V U T Mål Point
Uruguay: 2 1 1 0 3-0 4
Mexico: 2 1 1 0 3-1 4
Frankrig: 2 0 1 1 0-2 1
Sydafrika: 2 0 1 1 1-4 1

Der er 2 kampe tilbage i puljen.

Jeg dropper holdnummeret i eksempel-arrayene.

Bedst mulige placering for Uruguay:
Uruguay (4+3,3+3) // hypotetiske værdier. Resten er de opnåede
Mexico (4,2)
Frankrig (1,-2)
Sydafrika (1,-3)

Sorteret ligger de så
Uruguay(7,6)
Mexico(4,2)
Frankrig(1,-2)
Sydafrika(1,-3)

bestcase(Uruguay) = 1. plads
======================

Værst mulige placering for Uruguay:
Uruguay (4,3) // opnåede værdier. Resten er hypotetiske
Mexico (4+3,2+3)
Frankrig (1+3,-2+3)
Sydafrika (1+3,-3+3)

Sorteret ligger de så
Mexico(7,5)
Uruguay(4,3)
Frankrig(4,1)
Sydafrika(4,0)

worstcase(Uruguay) = 2. plads
======================


Min algoritme giver i worstcase alle andre hold maksimumscore
selv om den enes maksimum jo svarer den andens minimum (der er en
taber hvis der er en vinder).

Og så spørgsmålet:
Hvordan skal en algoritme skrues sammen hvis den skal være helt
præcis - altså tage hensyn til antallet af resterende kampe samt
til at hvis en får maksimum, må en anden nødvendigvis få minimum?

[Andreas Andersen]

Post by Bertel Lund Hansen
Hvordan skal en algoritme skrues sammen hvis den skal være helt
præcis - altså tage hensyn til antallet af resterende kampe samt
til at hvis en får maksimum, må en anden nødvendigvis få minimum?

Der er det lidt interessante ved den slags algoritmer, at de blev meget
sværere, da nogle besluttede at gå fra 2 point for en sejr til 3 point
for en sejr. Et kendt problem i datalogi er at afgøre, om et givet hold
har mulighed for at vinde puljen, hvilket jo er meget relateret til dit
problem. Når en sejr giver 3 point til vinderen, og uafgjort giver 1
point til hvert hold, er der ingen kendt algoritme, der kan løse det
asymptotisk bedre, end bare at beregne alle mulige udfald og se om
holdet vinder i et af tilfældene. Selvfølgelig sætter man holdet til at
vinde alle sine egne kampe. Hvis du finder en polynomiel algoritme, har
du vist P=NP og kan tilbringe resten af dine dage i luksus, hvor i
verden du skulle have lyst.

Hvis derimod en sejr kun giver 2 point, kan det løses polynomielt ved en
simpel max-flow-algoritme. Jeg kan ikke lige huske den i hovedet, men
den skulle være til at google - "Handball Problem" hed det vist i den
opgave, vi havde om det i algoritmik på uni.

Den afgørende forskel er, at der i det sidste tilfælde altid kommer det
samme antal point ud af en kamp.

[Bertel Lund Hansen]

Post by Andreas Andersen
problem. Når en sejr giver 3 point til vinderen, og uafgjort giver 1
point til hvert hold, er der ingen kendt algoritme, der kan løse det
asymptotisk bedre, end bare at beregne alle mulige udfald og se om
holdet vinder i et af tilfældene.

Okay. Det er jo også forholdsvis overkommeligt med 6 hold. Jeg
funderer over om ikke man kan lave en rekursiv funktion, men man
skal jo løbende holde styr på det bedste resultat uden for
funktionen.

Post by Andreas Andersen
Den afgørende forskel er, at der i det sidste tilfælde altid kommer det
samme antal point ud af en kamp.

Ja, jeg kan godt se at det er vigtigt.

[Jacob Sparre Andersen]

Post by Bertel Lund Hansen

Post by Andreas Andersen
problem. Når en sejr giver 3 point til vinderen, og uafgjort giver 1
point til hvert hold, er der ingen kendt algoritme, der kan løse det
asymptotisk bedre, end bare at beregne alle mulige udfald og se om
holdet vinder i et af tilfældene.

Okay. Det er jo også forholdsvis overkommeligt med 6 hold. Jeg
funderer over om ikke man kan lave en rekursiv funktion, men man
skal jo løbende holde styr på det bedste resultat uden for
funktionen.

Det behøver du vel ikke. Kan du ikke bare returnere det fra funktionen?

Hvordan håndterer du at det ved uafgjort på point er antallet af mål der
afgør sagen? (Er det ikke sådan reglerne er?) Eller er det
ligegyldigt, så du kan nøjes med at se på tabt, vundet og uafgjort for
hver kamp?

God fornøjelse,

Jacob

[Bertel Lund Hansen]

Post by Jacob Sparre Andersen
Hvordan håndterer du at det ved uafgjort på point er antallet af mål der
afgør sagen?

Ret simpelt i PHP. Jeg laver et sorteringsarray med

($point,$diff,$ownscore,$nr)

Når jeg laver en array_multisort() på det, bliver der sorteret
prioriteret på alle oplysningerne efter tur.

Post by Jacob Sparre Andersen
(Er det ikke sådan reglerne er?)

Jo. Point først, derefter måldifference, så egen målscore, og om
nødvendigt, indbyrdes opgør. Hvis det står lige i alle felter,
skal det vist afgøres på straffe.

[Andreas Andersen]

On 21 Jun., 20:12, Bertel Lund Hansen

Post by Bertel Lund Hansen

Post by Andreas Andersen
problem. Når en sejr giver 3 point til vinderen, og uafgjort giver 1
point til hvert hold, er der ingen kendt algoritme, der kan løse det
asymptotisk bedre, end bare at beregne alle mulige udfald og se om
holdet vinder i et af tilfældene.

Okay. Det er jo også forholdsvis overkommeligt med 6 hold. Jeg
funderer over om ikke man kan lave en rekursiv funktion, men man
skal jo løbende holde styr på det bedste resultat uden for
funktionen.

Funktionen kunne tage scorerne efter de allerede spillede kampe og
listen af de N resterende kampe. Beregne nye scorer for hvert af de 3
mulige udfald af den første af de resterende kampe og kalde rekursivt
med de ny-beregnede scorer og de N-1 sidste af de resterende kampe.
Til sidst vurdere og returnere det bedste resultat. Asymptotisk er det
O(3^(antal kampe)), som er overkommeligt for 15 kampe, svært for 20 og
umuligt for 30.

--
Andreas

[Niels L. Ellegaard]

Post by Bertel Lund Hansen
Hvordan skal en algoritme skrues sammen hvis den skal være helt
præcis - altså tage hensyn til antallet af resterende kampe samt
til at hvis en får maksimum, må en anden nødvendigvis få minimum?

Spørgsmålet er hvor hurtigt det skal gå. Hvis du har tid til at
vente, så vil jeg gætte på at du godt kan nå at undersøge alle de
sandsynlige kombinationer af kampresultater end ad gangen. Det burde
være OK.

Hvis du gerne vil bruge din opgave som en undskyldning for at lære
noget indviklet operationsanalyse, så kan du taget et kig på
heltalsprogrammering (integer programing). Ideen er at man opskriver
et system af uligheder, hvor ale variablene er heltal. Derefter
kan man bede en computer om at undersøge om der er en løsning.

x_ij (=-x_ji) er en heltals variabel der angiver målscoren i kampen
mellem i og j. Vi antager at variabelen kan antage værdier mellem
-M og M (eksempel M=20)

v_ij er 1 hvis i vandt over j ellers er den nul. Så vidt jeg kan se
opfylder disse variable at

x_ij - M * v_ij <= 0
(1-x_ij) - M * (1 - v_ij) <= 0

u_ij ( = u_ji) er 1 hvis i og j spiller uafgjort ellers er den
nul. Dette må give

v_ij + v_ji + u_ij = 1

p_i angiver antallet af points som hold i har fået. Dette giver

p_i = sum_j (3 x_ij + u_ij)

m_i er hold i's målscore

m_i = sum_j x_ij

s_i er en slag samlet score der viser hvor godt hold i har klaret
sig. (Jeg ganger p_i igennem med et meget stort tal, så det bliver vægtet
højere end målscoren)

s_i = 3*M*p_i + m_j

Bemærk at s_1 antager værdier mellem -M og 4M

k_ij er 1 hvis hold i fører over hold j i klassementet. Ellers er den
nul. Jeg tror at dette giver

(s_i - s_j) - 10*M * k_ij <= 0
(1 - (s_i - s_j)) - 10*M * (1 - k_ij) <= 0

r_i er positionen for hold i i det samlede klassement.

r_i + sum_j k_ij = 4

Givet dette sæt uligheder kan du forsøge at maximere eller minimere en
af variablene r_1, r_2, r_3 eller r_4.

Jeg har ikke helt overblik over hvilke programmer der virker på windows,
så det er lidt en bagdel ved metoden, men en mulighed er at kigge på LP-solve.

http://lpsolve.sourceforge.net

God fornøjelse

Niels

[Bertel Lund Hansen]

Post by Niels L. Ellegaard
Spørgsmålet er hvor hurtigt det skal gå. Hvis du har tid til at
vente, så vil jeg gætte på at du godt kan nå at undersøge alle de
sandsynlige kombinationer af kampresultater end ad gangen. Det burde
være OK.

Det var den løsning jeg valgte. Beregningstiden kan slet ikke
mærkes (det er PHP). Jeg takker for alle kommentarerne.