New Topic/Question
Reply
Hello everyone..!
I have a problem in my project, its a web application for collage students, it assigned a graduation projects to students; by offering many projects online,
student login, selects many project he interested in ( he can choose up to six projects),
after that doctor can see names of students who have chosen his project, doctor ranked them from 1-6 ( may less )
i want to match between student's choice and doctor's choice, and get best order.
there is six choices for student, and also six choices for doctor,
and we have many doctors and many students,
the problem is:
when student select a project as 1st choice,
and doctor also select this student as 1st in that project
then it is (1:1) , best match, the student gets the project.
but in the other cases, what should we put first?
(1:3) // doctor select student in 1st, student selects project in 3rd
or (2:2) // student and doctor select 2nd
so, whats come first? (1:3) or (2:2)
there are some other cases.
this is a similar problem: Stable roommates problem
http://en.wikipedia....ommates_problem[url]
i tried to do this:
- for any case, doctor choice comes higher than student's.
but also in some cases i can't apply this, (e.g (3:3) and (1:6)doctor 1st, but student 6,comes before )
thanxx
5 Replies - 2340 Views - Last Post: 28 January 2011 - 10:30 AM
#1 Guest_bluue Hnno*
matching ALGORITHM.. a question..!
Posted 28 January 2011 - 09:10 AM
MultiQuoteReplies To: matching ALGORITHM.. a question..!
#2
LivingNightmare
- D.I.C Head
-
Reputation: 21
- Posts: 129
- Joined: 07-July 10
Re: matching ALGORITHM.. a question..!
Posted 28 January 2011 - 09:38 AM
Hmm, I believe what you want is the stable marriage problem ( http://en.wikipedia....arriage_problem ) - This is really similar to the stable roommates problems, but slightly different. Take a look at that perhaps...
Was This Post Helpful?
0
#3
mojo666
- D.I.C Addict
-
Reputation: 409
- Posts: 885
- Joined: 27-June 09
Re: matching ALGORITHM.. a question..!
Posted 28 January 2011 - 09:41 AM
It seems like you want to use the marriage algorithm here. You should have all the students pick their favorite project, then the doctor rejects all but the most preferred student who is trying for that particular project. Every student who was not rejected for a project stays while all the rejected students move on to their next preferred project. This continues untill no student is rejected.
Was This Post Helpful?
0
#4 Guest_bluue Hnno*
Re: matching ALGORITHM.. a question..!
Posted 28 January 2011 - 10:03 AM
LivingNightmare, on 28 January 2011 - 09:38 AM, said:
Hmm, I believe what you want is the stable marriage problem ( http://en.wikipedia....arriage_problem ) - This is really similar to the stable roommates problems, but slightly different. Take a look at that perhaps...
yes, thanx a lot.. i also have checked this, but i think "roommate" is more similar to my problem, why you think the marriage is much similar.. please tell me because i'll work on it for all next semester
the stable marriage: based on woman first rank, whatever it was,
but my project should takes care about student ranks and doctor ranks,
of course doctor's rank comes higher; since he has seen where the student selects the project(in which rank), and the doctor already knows how much each student interest in the project.
i wrote a lot of things, but every time there are some irregular cases,
i need a bit help in how to write algorithm for such problems.
Thanx..
#5
LivingNightmare
- D.I.C Head
-
Reputation: 21
- Posts: 129
- Joined: 07-July 10
Re: matching ALGORITHM.. a question..!
Posted 28 January 2011 - 10:08 AM
Well the marriage problem is just an instance of a generic problem. But if you just look at the abstraction of the marriage problem, you'll see that what you're trying to do is almost identical to the marriage problem. Instead of having males and females picking their spouses, you have students giving a ranking of projects, and you have each doctor (which I assume that each doctor is in charge of one project), pick which students they would rather work with. This is essentially the same abstraction as the stable marriage problem.
The reason I know this, is because we covered a really similar doctor/student example in class when I had seen this algorithm
"Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference ... " So as you can see, this is basically what you want. You would have to modify it slightly to find n students and m doctors perhaps... but the logic should be very similar.
The reason I know this, is because we covered a really similar doctor/student example in class when I had seen this algorithm
"Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference ... " So as you can see, this is basically what you want. You would have to modify it slightly to find n students and m doctors perhaps... but the logic should be very similar.
This post has been edited by LivingNightmare: 28 January 2011 - 10:10 AM
Was This Post Helpful?
0
#6 Guest_bluue Hnno*
Re: matching ALGORITHM.. a question..!
Posted 28 January 2011 - 10:30 AM
ahaa!!
my supervisor also told me about marriage algorithm,mmm but may be coz i didn't see it abstractly..
will try to understand it well..
and will back with my Qs =)
Thanx,
my supervisor also told me about marriage algorithm,mmm but may be coz i didn't see it abstractly..
will try to understand it well..
and will back with my Qs =)
Thanx,
Page 1 of 1
| 