Produire une commande totale ou partielle à partir d'une relation incohérente
Imaginez que je veuille construire une commande totale à partir d'un ensemble d'éléments, $E$, mais la fonction de comparaison produit des résultats non déterministes. Je produis une liste de paires d'éléments (e, e) par application répétée de la fonction de comparaison, de sorte que chaque élément de l'ensemble soit représenté au moins une fois.
Comment puis-je utiliser cette entrée pour produire une commande totale? Quelle est la classe d'algorithmes qui peut être appliquée ici?
Pour plus de clarté, je vais donner un exemple concret.
Quelles sont les meilleures garnitures de pizza?
Mon ensemble d'éléments $E$ comprend quelques garnitures de pizza populaires: pepperoni, fromage, champignon, ananas, poivron, olive.
Ensuite, pour chacun de mes amis, je choisis des sous-ensembles de garnitures de taille aléatoire et je demande à mon ami de les mettre en ordre du meilleur au pire. Mes amis répondent consciencieusement et créent l'entrée pour mon algorithme:
- fromage, pepperoni, olive
- fromage, ananas, champignon, olive
- poivron, champignon, olive
- pepperoni, fromage, olive
- fromage, poivron
Il semble y avoir un ordre flou ici (tout le monde convient que les olives sont les pires) mais mes amis ne sont pas parvenus à un consensus sur la meilleure garniture de pizza: fromage ou pepperoni. Compte tenu de l'emplacement des éléments dans les entrées et de la fréquence à laquelle ils se produisent, je produirais probablement une commande comme celle-ci.
- fromage> pepperoni> poivron> ananas> champignon> olive
Je ne sais tout simplement pas comment formaliser cela et le faire fonctionner pour des intrants beaucoup plus importants.
Je pense que la solution implique probablement des graphiques et des arêtes pondérées, mais je ne connais pas suffisamment les algorithmes de graphes pour reconnaître s'il s'agit d'un domaine d'étude nommé. Je suis déjà tombé sur le "tri topologique" mais cela ne fonctionne que pour les graphes acycliques dirigés, et je suis particulièrement intéressé par les entrées qui ne peuvent pas produire un DAG.
J'ai également remarqué que ce problème semble similaire au vote pour les élus. S'agit-il, en fait, de la même catégorie de problèmes?
Réponses
C'est difficile à dire sans plus de contexte et plus de modélisation. Il faudra certaines hypothèses sur la manière dont les résultats de la fonction de comparaison se rapportent à l'ordre total souhaité (masqué).
Il est possible que vous souhaitiez le modèle Bradley-Terry-Luce . Si tel est le cas, il existe de nombreux algorithmes standard. Voir égalementhttps://cs.stackexchange.com/a/85204/755.
Il est possible que vous souhaitiez un système de classement, comme Elo, etc.
Il est possible que vous souhaitiez un système de vote avec classement , tel que l'IRV, la méthode Condorcet, le décompte Borda ou tout autre système. Ils ont tous divers défauts et compromis. Il y a une preuve qu'aucun système n'aura toutes les propriétés que nous pourrions souhaiter - voir, par exemple, le théorème d'Arrow et le problème de la non-transitivité (que même si chacune des préférences individuelles de votre ami est transitive, c'est-à-dire un ordre total, alors il n'y a aucune garantie qu'il existe un ordre global global qui soit cohérent avec chacun d'eux).