J'écris une application qui divise une population d'utilisateurs en paires dans le but d'effectuer une tâche ensemble. Chaque utilisateur peut spécifier diverses préférences sur leur partenaire, par exemple
Idéalement, j'aimerais que l'utilisateur puisse spécifier si chacune de ces préférences est une "bonne d'avoir" ou un "DOIT avoir", par exemple. "Je préférerais être assorti à un orateur anglais natif, mais je ne dois pas être assorti à une femme".
Mon objectif est de maximiser la qualité moyenne globale des matchs. Par exemple, supposons qu'il y a 4 utilisateurs dans le système, A, B, C, D. Ces utilisateurs peuvent être adaptés de 3 manières: donc dans cet exemple artificiel, La 3ème option serait choisie car elle a la plus haute qualité de match globale, même si A et D ne sont pas très bien associés du tout. Y a-t-il un algorithme qui peut m'aider à: < ul>
Il n'est pas absolument nécessaire que chaque utilisateur soit assorti, il est donc préférable d'annoncer de manière significative la qualité globale des matchs, et laissant quelques utilisateurs sans match, je choisirais ce dernier. Évidemment, j'aimerais que l'algorithme qui calcule les allumettes à compléter le plus rapidement possible, car le nombre d'utilisateurs du système pourrait être assez important. Enfin, ce système de scores de correspondance informatique et maximiser la moyenne globale est juste un hurcicique que j'ai proposé moi-même. S'il y a un bien meilleur moyen de calculer les paires, merci de me le faire savoir. Le problème que j'ai décrit semble être une similaire à la problème de mariage stable pour laquelle il existe une solution bien connue. Cependant, dans ce problème, je n'ai pas besoin que les paires choisis soient stables. Mon objectif est de choisir les paires de sorte que le "score de match" moyen soit maximisé Mise à jour
5 Réponses :
Qu'est-ce que Algorithmes de correspondance maximum Avez-vous regardé? J'ai lu votre question trop à la hâte au début: il semble que vous ne vous limitez pas nécessairement à un graphique bipartite. Cela semble plus difficile.
En particulier, un problème de flux maximum minimum pourrait être utile ici, où le coût d'un match pourrait être inversement proportionnel à sa bonté.
Pour trouver une correspondance maximale dans un graphe arbitraire, il existe une variante pondérée de l'algorithme correspondant d'Edmond:
Je crois que ce problème pourrait être représenté comme un problème de programmation linéaire. Et puis vous pouvez utiliser Méthode simplex pour le résoudre.
Ce problème ne peut être caractérisé que sous forme de problème de programmation linéaire si le "score de correspondance" est une fonction linéaire de chaque préférence de l'utilisateur.
J'ai fourni une solution possible à un problème similaire ici . C'est un algorithme de mesure de la dissimilarité - plus les données mesurées similaires concernent des données attendues, plus votre nombre résultant sera petit.
Pour votre candidature, vous définiriez les préférences de la personne comme les données attendues et l'autre que vous comparez à la mesure des données mesurées. Vous voudriez filtrer les "données mesurées" pour éliminer ces cas comme "ne doivent pas être assorties avec une femme", que vous mentionnez dans votre question initiale avant d'exécuter la comparaison.
Une autre option pourrait utiliser un algorithme de chi-carré.
Par l'apparence de celui-ci, votre problème n'est pas bipartite, il me semblerait donc que vous recherchiez une correspondance maximale de poids dans un graphique général. Je n'envie pas la tâche d'écrire cela comme l'algorithme de rétrécissement de Blossum d'Edmond n'est pas facile à comprendre ni à mettre en œuvre efficacement. Il existe des implémentations de cet algorithme, un tel exemple étant le citron de la bibliothèque C ++ ( http: // citron .cs.elte.hu / trac / citron ). Si vous souhaitez qu'une correspondance de poids maximale de cardinalité maximale, vous devez utiliser l'algorithme de correspondance de poids maximum et ajouter un poids important (somme de tous les poids) à chaque bord pour forcer la cardinalité maximale comme première priorité.
Alternativement, comme vous l'avez mentionné dans l'un des commentaires ci-dessus que vos termes de match ne sont pas linéaires et que la programmation linéaire est sortie, vous pouvez toujours adopter une approche de programmation de contrainte qui n'exige pas que les termes soient linéaires.
Pourriez-vous définir «assez grand», c'est-à-dire des centaines, des milliers, des millions?
@IVan Idéalement, j'aimerais que le système puisse effectuer l'algorithme correspondant à quelques millions d'utilisateurs en quelques heures.
Je m'approche un problème similaire (avec une différence sur laquelle mes "hommes" et mes "femmes" doivent être jumelés avec le sexe opposé et il n'y a pas de population équilibrée) - Je vois que vous n'avez pas accepté une solution - qui approche avez-vous descendu?