• Status: Solved
• Priority: Medium
• Security: Public
• Views: 715

# 3d stable marriage problem

I have two arrays of point 3f and i want to get the best pairing of the two(in distance). There can be more points in the second array but not in the first. Is there a way in which i can get the best pairing of them. This is for metamorphosis so i know which points need to go to where. Any help would be grateful
Cheers
0
n0152974
• 5
• 2
• 2
1 Solution

Commented:
This is a duplicate of http://www.experts-exchange.com/Programming/Programming_Languages/Java/Q_20521453.html

I posted an implementation of that algorithm. Did it not help?
0

Author Commented:
sorry i'm not explaining it very well. I only need to pair up the points in first array to the second, i have the order of their "preference" but i dont know how to code it to do this. there is preference from the second array to the first and there can also be more than 1 point go to the same point in the second array, (only if all have a destination). I hope i'm explaining this well.
0

Author Commented:
does this help or make thing worse?
0

Author Commented:
a mistake in the first posting, there can be more point in the FIRST and not the second sorry
0

Commented:
Sounds like a bigamous stable marriage then ;-)

Please explain again. You've got the two arrays, you've got the set of preferences for each member in each array...?
0

Author Commented:
haha. I have two arrays of points, the first array can have more points than the second one. I have a list of preference for each point in the first array. This list is ordered according to distance from the point. All the points in the first array need a destination and all the points in the second array needs to be 'travelled to'. there can be more than 1 point going to the same piont. I hope this is clear, thank you
0

Commented:
There's something special about this particular Stable Marriage problem ... it is symmetric, i.e. if for any point P from the first set, point Q, for the second set, happens to be the point closest to P (P loves Q the most), then point P is the closest point to Q (Q loves P most).

This peculiarity reduces the SMP to a simple 'job assignment' problem. A very simple iterative algorithm could do the job as follows:

1: pair up all P's and Q's randomly
2" while there still exist two pairs P_i, Q_j and P_k, Q_l such that (P_i, Q_l) (P_k, Q_j) would yield a better solution,
3:      swap these two pairs

The solution space of this problem is convex, i.e. if a minimum cost value exist (and here it does), stepping downwards from a current solution until no cheaper solution exists always reached the global optimum.

For a much faster solution to this job assignment problem, google up 'job assignment problem' or 'minimal cost network flow problem'.

kind regards

0

Author Commented:
so all i do is randomly pair up the points and then go thro each point in the first array and check all the other pairs and c if there is a better solution?
0

Commented:
Almost; you pair up all points randomly and then you repeatedly check all *two* pairs; if these two pairs (A, B), (C, D) can be swapped, i.e. a better solution would be the result, you do the swap (A, D), (C, B) and repeat the process; until no two such pairs can be found anymore.

kind regards
0

## Featured Post

• 5
• 2
• 2
Tackle projects and never again get stuck behind a technical roadblock.