Programming Problenm Stable Marriage Using Backtracking The Problem: You have n

Question

Programming Problenm Stable Marriage Using Backtracking The Problem: You have n men and n woman, and their preference rankings of each other, and you need to match them up so that the total matching is "stable." The preference rankings: You are given 2 n X n arrays, mp (men's preference) which gives the men's ranking of the women, and wp (women's preference) which gives the women's ranking of the men So mpii] gives man i's ranking of woman j and likewise for the women's ranking of the men in wp. For example in the following tables we have n-3 and the women and men are "named" 0, 1 or 2 and the raking are in the range 0 highest, 1 second highest and 2 lowest.

Explanation / Answer

men women

0 2

1 0

2 1

example of stability: WO is matched with M1, but she prefers M2, and likewise M2 prefers WO to his current partner W1.

Thus the following is not a correct solution.(it should be eliminated by OK function)

q

0 1 2

int mp[3][3]={0,2,1

0,2,1

1,2,0};

int wp[3][3]={2,1,0

0,1,2,

2,0,1}

so man 1 assigns W2 the rank of 1

bool OK(int q[],int c) {

/* c indicates the new man and q[c] is the woman proposed for man c*/

}

WP   

0 1 2

1

MP

0 1 2

0

would 102 be a solution?

0 1 0 1 0 < -----------------1   

1 -------------------->0 1 --------------------> 0 1 0

2 2 2 --------------------> 2 2< ---------------- 2

There are 3 cases:

case 1: MO prefers WO ; but its not a danger because WO prefers its own partner.

case 2: M1 prefers W0 to W2, so o instability, similarly M2 prefers W2 to WO.

case 3:MO prefers W2 to W1, but W2 prefers her wn partner to MO. So no instability.W1 prefers MO preference of M2, there would be no instability.

2 0 1

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.