Aller au menu - Aller au contenu

Alogrithme de Gale et Shepley

Implementation

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page 1 
Auteur Message
2 visiteurs sur ce sujet (2 anonymes)
Page 1 
Hors ligne soloy # Posté le 07/02/2012 à 00:49:57

Salut à tous!
j'ai un devoir d'informatique et je dois implementer l'algorithme de Gale et Shepley connu en français sous le nom de l'algorithme des mariages stables. voici un lien wikipedia http://en.wikipedia.org/wiki/Stable_marriage_problem qui expliquer un peu!
Je n'arrive à avoir le resultat voulu, voici ce que j'ai fait ci dessous! si quelqu'un pourra m'aider ça me fera très plaisir. Merci d'avance

A plus!

import java.util.LinkedList;


public class StableMatching implements StableMatchingInterface {
@Override
public int[] constructStableMatching(int n, int[][] menPrefs,
int[][] womenPrefs) {
// TODO Auto-generated method stub
// menPrefs = new int[n][n];
// womenPrefs = new int[n][n];
int bride[] = new int[n];
LinkedList<Integer> freeGuys = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
freeGuys.add(i);
}
int[] w = new int[n];
for (int i = 0; i < n; i++) {
w[i] = -1;
}
int[] h= new int[n];
int[] visited= new int[n];
for (int i = 0; i < n; i++) {
h[i] =visited[i]=-1;
}
int[][] free = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
free[i][menPrefs[i][j]]=j;
}
}
while (!freeGuys.isEmpty()) {
int thisGuy = freeGuys.getFirst();// soit un homme celibataire
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (w[i] == -1) {// si la femme est libre
bride[thisGuy] = i;
h[i]=thisGuy;
} else {
if (womenPrefs[i][j] < womenPrefs[i][thisGuy]) {
bride[thisGuy] = i;
freeGuys.add(j);
} else {
bride[j] = i;
}
}

}

}
freeGuys.removeFirst();
}
return bride;
}
}
Publicité # Posté le 07/02/2012 à 00:49:57

Hors ligne @lgorythme # Posté le 07/02/2012 à 21:08:18
Maths, algorithmie et C++ !
Avatar
Je te répond sans pour autant connaître la solution à ton problème, mais pour te signaler qu'il existe une balise pour présenter tes codes.

En effet ce que tu as fourni est illisible en raison du fait qu'en message de forum n'est pas adapté pour faire du codage.

Utilise la balise <Code>.

Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <iostream>

using namespace std;

int main()
{
     cout << "Oh mais quel beau code en C++ qu'il y a là ! " << endl;

     return 0;
}


Avec ça ton code sera plus clair et les gens auront plus d'envie de t'aider : empresse toi d'éditer ton message !
Algorithmie :
France IOI : niveau 3
Prologin, SPOJ, Projet Euler
Programmation :
C++, C++, C++, et C++ !
 
Hors ligne soloy # Posté le 08/02/2012 à 21:21:49

Bon voici le code!
Code : Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.LinkedList;


public class StableMatching implements StableMatchingInterface {
@Override
public int[] constructStableMatching(int n, int[][] menPrefs,
int[][] womenPrefs) {
// TODO Auto-generated method stub
// menPrefs = new int[n][n];
// womenPrefs = new int[n][n];
int bride[] = new int[n];
LinkedList<Integer> freeGuys = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
freeGuys.add(i);
}
int[] w = new int[n];
for (int i = 0; i < n; i++) {
w[i] = -1;
}
int[] h= new int[n];
int[] visited= new int[n];
for (int i = 0; i < n; i++) {
h[i] =visited[i]=-1;
}
int[][] free = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
free[i][menPrefs[i][j]]=j;
}
}
while (!freeGuys.isEmpty()) {
int thisGuy = freeGuys.getFirst();// soit un homme celibataire	
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (w[i] == -1) {// si la femme est libre
bride[thisGuy] = i;
h[i]=thisGuy;
} else {
if (womenPrefs[i][j] < womenPrefs[i][thisGuy]) {
bride[thisGuy] = i;
freeGuys.add(j);
} else {
bride[j] = i;
}
}

}

}
freeGuys.removeFirst();
}
return bride;
}
}

Retour au forum "Autres langages, outils et approches" ou à la liste des forums

Pour accéder à cette section
Connectez-vous !
connexion_rpx