Problem 1 Given a set of 2n points in a plane, consider a situation where a modi

Question

Problem 1 Given a set of 2n points in a plane, consider a situation where a modified version of the Gale- Shapley algorithm is used to achieve Stable Matching. A point, A, ranks the other 2n 1 points in the increasing order of their Euclidean distances from A. Thus, in the preference list of A, the point which is at a minimum distance from A is ranked first. This approach is followed by each of the 2n points in order to rank the other 2n -1 points on their preference list. All distances are unique. The following pseudo code describes the modified Gale-Shapley algorithm and we also provide a basic description: During each iteration, a free point, proposes to another point based on its own (r's) prefer- ence list. However, an engaged point can break up from its current partner if a point ranked higher in its preference list proposes to it . The total number of points is 2n and is, thus, an even number. Any free point can propose to any of the remaining 2n - 1 points. Algorithm 1 Modified Gale-Shapley algorithm for Stable Matching of points in a plane Initially all p P are free while there is a point that is free and has not proposed to every other point do Choose such a point p Let qE P be the highest ranked point in p's preference list to which P has not yet proposed if q is free then (p, q) become engaged else q is currently engaged to p if (Distance of p from p remains free > (Distance of p' from q) then else (Distance of p from q)

Explanation / Answer

You have not mentioned the true/false questions.

So, i guess you are asking for the algorithm. I am writing the algorithm from the pseudocode.

This code is in C++.

#include<stdio.h>
#include<bits/stdc++.h>
#include<math.h>
#include<limits.h>
//point structure to store the point co-ordinate
struct point {
int x;
int y;
};
//this function will return the eucledian distance between the two points
double eucledian_distance (point p1, point p2) {
return sqrt(pow((p1.x-p2.x),2) + pow((p1.y-p2.y),2));
}

int main() {
int n;
scanf("%d",&n);
//creating 2n points
struct point a[2*n];
int i;
for (i = 0; i < 2 * n; i++) {
scanf("%d",&a[i].x);
//scanning the x co-ordinate
scanf("%d",&a[i].y);
//scanning the y co-ordinate
}
double dist [2*n][2*n];
//this dist array will keep the list of the eucledian_distance of each point to the other
int j;
for (i = 0; i < 2 * n; i++) {
for (j = 0; j < 2 * n; j++) {
dist[i][j] = eucledian_distance(a[i],a[j]);
}
}
int partner[2 * n];
for(i = 0; i < 2 * n; i++) {
partner[i] = -1;
}
//now this partner array will keep track of the nodes already partnered
//and with which node it partnered. If the node did not partner with anyone
//save -1. initially all the entries will be -1
while(1) {
int c = 0;
for(i = 0; i < 2 * n; i++) {
if(partner[i] == -1) {
c++;
break;
}
}
//c == 0 implies there is no un partnered node available anymore
//so we stop the execution
if(c == 0) {
break;
}
//check for every node
for(i = 0; i < 2 * n; i++) {
int mini = -1;
//mini is there to store the index position of q
int minval = INT_MAX;
int j;
//selecting the best preference from the list of distance preferences
for(j = 0;j < 2* n; j++) {
if(i != j && dist[i][j] < minval) {
minval = dist[i][j];
mini = j;
}
}
//point is not allocated
if (partner[j] == -1) {
partner[j] = i;
partner[i] = j;
//allocating i as partner of j and vice versa
}
else {
double dist1 = eucledian_distance(a[j],a[partner[j]]);
//distance between p' and q
//distance is less than distance between p and q , no change
//else deallocate partner of p' and p becomes new partner of j
if (dist1 > dist[i][j]) {
partner[partner[j]] = -1;
partner[j] = i;
partner[i] = j;
//allocating i as partner of j and vice versa
}
}
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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