Défi Algorithmique
Pouvez-vous faire mieux que notre algorithme ?
Pour un très grand nombre de candidats, les recherches exhaustives ne peuvent fonctionner. La limite de la méthode exacte développée ici est d'environ 45 candidats pour un calcul sur PC (qui prend de l'ordre de l'heure). Sur ce site web, elle est bridée à 25 candidats pour garantir un temps de réponse de l'ordre de la seconde.
Au-delà, il faut utiliser des méthodes heuristiques ayant une part aléatoire, ce qui fait que l'on ne peut garantir mathématiquement que le score obtenu est l'optimum absolu.
Le défi : Les votes ont été générés aléatoirement pour offrir la difficulté maximale lors de la recherche de l'optimum. Pouvez vous touver une solution avec un meilleur score pour le cas à 200 candidats ? Vous pouvez charger les données ci-dessous. On connait la réponse exacte pour les autres cas plus faciles qui vous sont donnés pour mémoire.
Règles et Format
- Le format est un fichier JSON contenant une liste de votes (un tableau de tableaux).
- Chaque vote est une suite de rangs :
[rang du candidat 0, rang du candidat 1, ...]. - Les candidats sont indexés de 0 à N-1.
- Les rangs commencent à 0 pour le candidat préféré.
Calcul du score
Pour un résultat où les candidats sont placés dans l'ordre (...x...y...), le score
est :
La somme du nombre de fois où x bat y, diminuée
du nombre de fois où x est battu par y,
et cela pour tous les couples où x est classé avant y dans votre
solution.
Jeux de données disponibles
| Action | Candidats | Votes | Meilleur Score Actuel | Méthode de calcul |
|---|---|---|---|---|
| Télécharger | 5 | 5 | 24 | Méthode exhaustive |
| Télécharger | 25 | 25 | 1078 | Méthode exhaustive (limite du site) |
| Télécharger | 45 | 45 | 4406 | Méthode exhaustive (1h sur PC) |
| Télécharger | 200 | 200 | 196352 | Méthode heuristique |