Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Algo de calcul de meilleur classement possible (football)
Bonjour,
Alors voilà je cherche à écrire un algo qui me permettrait, à partir d'un classement et des matches restant à jouer, de calculer le meilleur classement possible d'une équipe.
Le sport visé est le football (mais je pense que ça pourrait se généraliser facilement).
Je ne vois pas trop comment m'y prendre ...
J'aimerais donc de l'aide, voire savoir s'il existe déjà un algo de la sorte.
Merci d'avance !
Salut,
Quelque chose de tout simple : ton équipe gagne tous les matchs à venir x nbr de point par match et les équipes devant ordonnées de celle qui a le + de point à celle qui en a le moins gagne tous ses matchs restant. Ca marche ?
Ressources proposées par 3DArchi - Les fonctions virtuelles en C++ - Cours et tutoriels C++ - FAQ C++ - Forum C++.
Que l'équipe choisie gagne la totalité de ses matches restant : OK, ça me semble logique.
Par contre, faudrait que tous ceux qui sont devant perdent tous leurs matches restant.
Mais s'ils s'affrontent entre eux, ça pose problème ...
Il faudrait alors regarder si le club est "dépassable" ou non, je pense ...
S'il y a un affrontement entre 2 équipes mieux classées et qu'une des deux n'est pas "dépassables", il faudrait que ce soit elle qui gagne (tant qu'à faire).
Sinon, il faudrait voir pour un match nul, éventuellement ...
Mon soucis premier est de définir des bonnes règles (pour que la solution obtenue soit optimale).
Mon second soucis concerne la représentation et la modélisation de ces règles !
Salut
Tu prends toutes les équipes devant celle que tu as choisie.Envoyé par pontus21
Celle-ci gagne tous ses matches.
La première du classement les gagne tous sauf un (celui contre ton équipe).
La seconde les gagne tous sauf deux (celui contre ton équipe et celui contre le premier)
Etc etc
Normalement, au final, tu as le meilleur classement de ton équipe si les autres équipes jouent au mieux.
Ma logique voit ça comme ça... mais elle n'est pas infaillible
Ta logique est effectivement faillible !
Si l'équipe choisie a respectivement 4, 7 et 10 points de retard sur le 1er, 2e et 3e, avec ton algo, elle ne les dépassera jamais !
Il faut minimiser le nombre de points pris par les équipes qui devancent l'équipe choisie ...
En fait non, dit comme je l'ai dit, c'est bon, c'est effectivement le meilleur classement si les autres équipes jouent au mieux
Mais apparemment ce n'est pas ce que tu veux
Houla... si j'ai 4 points de retard sur le premier et 10 sur le troisième, le troisième devrait se retrouver devant le premier... c'est pas logique!
... au risque de maximiser celui de l'équipe qui est juste derrière l'équipe choisie.
ok... donc tu peux tester en modifiant mon algo, en faisant gagner tous les matches sauf un à la dernière équipe du classement, tous sauf deux à l'avant-dernière, et en remontant vers le premier. Bien sûr, ton équipe gagnant toujours tous ses matches.
Sinon il faut parcourir l'arbre des possibilités... et choisir la meilleure config...
Exact, je m'étais un peu embrouillé aussi !
Par contre, je pense que l'arbre qui contient tous les résultats possibles est la meilleure solution.
Je l'avais déjà envisagé mais ça fait un arbre super grand !
Exemple :
S'il reste 8 journées, avec 10 matches à chaque journée, notre arbre contiendra 3^80 feuilles !
Il faudrait alors élaguer cette arbre avec certaines règles.
Par exemple pour toutes les équipes ayant moins de points que l'équipe choisie (au début de l'algo), on peut leur faire gagner leurs matches. Vu que l'équipe choisie gagnera tout, ils ne la dépasseront pas !
On peut aussi voir si certaines équipes ne sont pas "rattrapables". Dans ce cas, on peut aussi leur faire gagner tous leurs matches.
Ca enlève déjà des possibilités et donc des feuilles !
Si je ne m'abuse, ça revient à faire un mini-championnat en ne conservant que les équipes mieux classées que celle que l'on choisit, mais encore rattrapables (et en gardant le nombre de points de chaque équipe). Le meilleur classement de l'équipe choisie sera donc son classement "optimal" du mini-championnat + le nombre d'équipe mieux classées irrattrapables. Par contre il faudrait supprimer également les matches déjà joués entre équipes de ce mini-championnat.
Ca doit être plus léger à calculer horticolement parlant.
Effectivement, ça en revient à un mini-championnat !
On peut totalement occulter les autres équipes et donc un bon nombre de matches !
Par contre, si on veut chercher le meilleur classement de l'équipe classée 20e, ça nous fait quand même occulter aucune équipe (si l'équipe classée première est "rattrapable"). Mais c'est bien le pire des cas.
Tu penses que la meilleure solutions est un arbre ?
A moins que tu démontres formellement une formule qui te donne ça, oui...
Pour ton mini-championnat :
- si le nombre de points de l'équipe choisie + 3*nombre de matchs restants est inférieur au nombre de points de l'équipe classée 1ère du championnant à ce moment, tu peux dégager. Et ainsi de suite jusqu'à ce que le nombre devienne supérieur au score de l'équipe devant ton équipe, ou alors jusqu'à ce que tu arrives à ton équipe.
- tu peux réitérer ce test pour élaguer, si par le biais de rencontres entre équipes devant toi, une équipe deviendrait inatteignable. Mais il me semble que ça n'élaguera pas beaucoup. Un peu au début peut-être. En effet, si tu as 30 points d'écart, qu'il reste 10 matchs, et que l'équipe choisie et l'autre équipe gagnent. Il y a toujours 30 points d'écart, mais il ne reste que 9 matchs -> pas possible de rattrapper. D'un autre côté, cette équipe pourrait perdre aussi, et peut-être te fournir une meilleure configuration, qui permettrait à l'équipe choisie de la dépasser.
Voilà quelques pistes de réflexion.
Mon blog anglais - Mes articles et critiques de livres - FAQ C++0x, avec liste des nouveautés - Conseils sur le C++ - La meilleure FAQ du monde - Avant de créer des classes que vous réutiliserez, regardez si ça n'existe pas déjà - Le site du comité de normalisation du C++
Le guide pour bien débuter en C++ - Cours et tutoriels pour apprendre C++
Je viens de faire deux/trois tests sur un tableur... mais en gérant tout le championnat, j'ai mis tous les résultats des matches dans un tableau NxN (N: nombre d'équipes)
Je te propose cette méthode:
- état de base: résultats après J journées (toutes les équipes ont joué J matches)
- choix de ton équipe. Là, tu divises tes équipes en deux groupes: les mieux classées, et les moins bien classées (on laisse de côté les irrattrapables, ça met la panique dans la gestion sinon)
- tu fais gagner tous les matches de ton équipe, et tu fais gagner tous les matches non encore joués des équipes moins bien classées, en commençant par la mieux classée et en allant vers la dernière (càd que si il y a match entre deux équipes moins bien classées, c'est la mieux classée des deux qui gagne) -> nouveau classement.
- à ce niveau, il ne reste que les matches des équipes qui étaient mieux classées après l'état de base à définir. Tu les repères dans le classement après l'étape précédente (elles ne seront pas forcément dans le même ordre que dans l'état de base) , et tu leur fais perdre tous leur matches en partant de la mieux classée et en allant vers la moins bien classée (si match entre deux équipes mieux classée, c'est la moins bien classée qui gagne donc) -> classement final
Il faudrait voir si on arrive au même résultat avec un arbre....
C'est pas mal comme reflexion, plegat ...
Mais je ne pense pas qu'on arrive au même résultat avec un arbre, pour la simple raison que tu ne prends pas en compte les matches nuls.
En effet, si chaque équipe mieux classée doit jouer un seul match encore, et contre une autre équipe mieux classée, lors de ta dernière étape, il serait mieux de leur faire faire match nul.
Elles marqueraient chacune 1 point ...
Après, si notre équipe choisie aura 70 points avec tous ses matches gagnés et que les deux équipes A et B qui doivent se rencontrer lors du dernier match ont respectivement 69 et 66, c'est mieux de faire gagner B.
Si elles ont 68 et 68, c'est mieux de faire match nul ...
Ce que tu as mis en place est un bon début, je dirais.
Mais je pense qu'il y a encore plus de règles à mettre en place !
Merci également à Alp pour ses idées !
Si elles sont mieux classées, on leur fait perdre leurs matches... pas gagner. Mais c'est vrai qu'on risque de favoriser une des deux équipes, et donc ne pas minimiser les points. On peut donc modifier la règle: si match contre une équipe moins bien classée, défaite, si match contre une équipe mieux classée, match nul.
On peut également appliquer ceci pour les équipes moins bien classées...
ça veut dire qu'initialement, notre équipe avait 67 points (70-3). Donc que celle à 69 est mieux placée, et doit donc perdre, et celle à 66 moins bien classée, et doit donc gagner, ce qui correspond à ce que tu dis. Si elles ont toutes les deux 68, on en revient à la modif précédente de la règle des mieux classés, donc match nul.
Je pense aussi. Mais en faisant cette modif pour intégrer les matches nuls, on ne doit pas en être loin
Le mieux serait de faire des tests sur un championnat avec un nombre réduit d'équipes pour limiter la taille de l'arbre. Et comparer avec un traitement par règles.
Effectivement, on ne doit pas être loin du compte.
Je vais essayer ça ce week-end !
Par contre, j'aurai peut-être besoin d'aide pour l'arbre. J'en ai déjà fait, mais je ne me souviens plus très bien ...
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager