?
Solved

3d stable marriage problem

Posted on 2003-02-25
9
Medium Priority
?
714 Views
Last Modified: 2007-12-19
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
Comment
Question by:n0152974
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
  • 2
9 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 8016936
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 Comment

by:n0152974
ID: 8016981
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 Comment

by:n0152974
ID: 8017025
does this help or make thing worse?
0
Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

 

Author Comment

by:n0152974
ID: 8017081
a mistake in the first posting, there can be more point in the FIRST and not the second sorry
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 8017656
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 Comment

by:n0152974
ID: 8017779
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
 
LVL 4

Accepted Solution

by:
jos010697 earned 300 total points
ID: 8017812
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 Comment

by:n0152974
ID: 8018132
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
 
LVL 4

Expert Comment

by:jos010697
ID: 8018207
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

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
Suggested Courses
Course of the Month11 days, 13 hours left to enroll

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question