générer des paires pour un tournoi suisse

J'essaie de créer un générateur de tournoi suisse et je suis coincé sur la partie où les joueurs sont jumelés s'ils ont le même score ou ont le score le plus proche par rapport à d'autres possibles paires, sauf lorsqu'elles se sont déjà affrontées lors des tours précédents. J'ai entendu dire que ceci peut être modélisé comme un problème de graphes où chaque joueur est un sommet relié à tous les autres sommets à moins que les deux joueurs ne se soient déjà joués. Chaque arête est pondérée de sorte que plus le poids est élevé, moins la paire doit être calculée. Ensuite, il devient un problème de correspondance maximum avec les arêtes de poids | wins (a) - wins (b) | pour chaque paire {a, b}.générer des paires pour un tournoi suisse

J'ai regardé Edmund's Blossom algorithm qui je pense fonctionne pour les graphiques pondérés et non-pondérés. Je cherchais une implémentation Java mais je n'ai trouvé de solutions que sur des graphes non pondérés ou des implémentations en Java qui étaient difficiles à suivre pour moi. The closest thing I've found is this mais il ne prend pas en compte les bords pondérés

Source

2016-09-12 user1153395

On ne sait pas ce que vous demandez. Voulez-vous une référence à une bibliothèque d'algorithmes Blossom? C'est [hors sujet] (http://stackoverflow.com/help/on-topic) sur StackOverflow. Avez-vous besoin d'aide pour comprendre les règles des tournois suisses? Avec la modélisation du problème sous forme de graphique? En complétant votre implémentation de l'algorithme de Blossom? Adaptation de l'algorithme pour travailler avec des poids? Trouver des moyens alternatifs de mettre en œuvre un générateur de tournoi suisse? Tout cela, nous pouvons vous aider. Qu'avez-vous jusqu'à maintenant? –

J'ai juste besoin d'aide pour trouver un algorithme qui génère des paires de compétiteurs qui suivent les règles du tournoi suisse. J'ai lu que l'algorithme Blossom sur graphique pondéré est le meilleur pour cela et j'ai fait des recherches en ligne à ce sujet et j'ai essayé de le convertir en code Java, mais en attendant je me demandais si une telle implémentation existe déjà.Ou s'il y a une autre solution alternative – user1153395

Comme je l'ai dit, la fourniture de bibliothèques est hors sujet. Cependant, je ne pouvais pas trouver un Java qui gère les bords pondérés non plus, donc vous êtes coincé avec (1) en importer un à Java (par exemple à partir de Python) - (2) Coder vous-même - (3) Résoudre le problème autrement , comme l'a suggéré Benson Lin. Modifiez votre question pour répondre à l'une de ces solutions, et nous serons en mesure d'aider! –

2 choses:

garder une trace des joueurs joueur i a déjà joué contre pour tous les joueurs.
Gardez une trace du score de chaque joueur dans un ensemble ordonné.

Nous savons que pour trouver la différence minimale entre n'importe quel 2 joueurs, il doit s'agir de l'une des différences entre 2 scores adjacents lors de la commande. Par exemple, nous avons les scores:

1 2 4 7 9 10

La plus petite différence entre les 2 scores adjacents doit être l'une des paires suivantes:

{1,2} {2,4} {4,7} {7,9} {9,10}

Donc ce que vous pouvez faire est la suivante:

Itérer dans l'ordre (ordre croissant ou décroissant) parmi les joueurs disponibles.
À chaque joueur, vérifiez le joueur suivant (dans l'ordre) si les 2 ont déjà joué.

2a. Si c'est le cas, passez au suivant.

2b. Si ce n'est pas le cas, jumelez les 2 et retirez-les de l'ensemble (ou marquez-les de sorte que les vérifications ultérieures n'utilisent pas les mêmes joueurs).

Source

2016-09-12 10:34:26

J'ai essayé cela et parfois il me reste une paire qui s'est déjà jouée. Cette personne a eu un problème similaire http://stackoverflow.com/questions/28629235/swiss-tournament-pairing-algorithm?rq=1. Dans ce cas, il faudra faire quelques retours en arrière, je me demandais s'il y avait un moyen d'éviter cela. – user1153395

générer des paires pour un tournoi suisse

Répondre

Questions connexes