Problème d'itération/récursion?

Je travaille sur un programme où j'ai deux tableaux 2d. on s'appelle les mâles et les femelles. ils sont tous deux de taille 3x3. Le tableau contient un score de combien une personne aime l'autre.Problème d'itération/récursion?

ie (matrice mâle) Cela signifie que male0 aime female0 8, male0 aime Femme 1 5, male0 likes féminin2 8, Male1 aime female0 9, Male1 aime Femme 1 5, et ainsi de suite ....

8 5 8 
    9 5 7 
    5 6 8

J'ai aussi un autre tableau comme celui-ci pour les femelles où ils évaluent les mâles.

Ensuite, une marque autre tableau 2d où ajouter les notes pour chaque femme (i, j) et mâle (i, j)

Comment puis-je faire pour savoir quelle combinaison donne le plus grand score total? Je voudrais venir avec quelque chose comme

Best combination is: 
male0 -> female2 
male1 -> female0 
male2 -> female1

Source

2010-09-26 user69514

Cela ressemble étrangement à un problème d'appariement, qui est NP-complet. La force brute peut être le seul moyen. – JoshD

Je le marquerais comme devoirs si je pouvais. –

Une façon est d'essayer toutes les permutations d'une matrice femelle, pour chaque permutation trouver le score total, et à la fin choisir la permutation qui donne le meilleur score.

Source

2010-09-26 06:49:53 Reinderien

Je suis d'accord. Il y a six façons de jumeler les hommes avec les femmes (dans ce cas), donc ce serait raisonnablement rapide. Si je ne me trompe pas, c'est aussi l'approche générale la plus efficace. (Sauvegarder les scores pour chaque paire aidera à l'accélérer dans les grands cas, mais c'est toujours un problème O (n!). – JoshD

C'est le Stable Marriage Problem

Source

2010-09-26 07:13:28 McTrafik

"Les appariements pondérés ne doivent pas nécessairement être stables, mais dans certaines applications, un appariement pondéré maximal est préférable qu'un stable. " – ide

Répondre

Questions connexes