I don't know if my request is appropriate for this forum, but it's not obvious to me exactly where I should look for direction.
I'll soon be facing a programming challenge for which I feel there must be solutions or at least related algorithms out there already; I don't want to waste time reinventing anything. The nature of it seems to demand a mathematical approach beyond my experience, so I'll likely end up hiring someone to help me -- though if I can offer that person a strategy to begin with, so much the better.
FYI I'm an Actionscript (Flash) and PHP programmer, so I use a mix of procedural and OOP (though I'd imagine this problem's solution will likely use C or Java). Not really apropos to the topic, but I thought I'd introduce myself.
The problem actually has two main components (the first involving distance-based clustering, which might end up getting combined with the rest of the suitability/unsuitability criteria), but right now I'm most concerned with its second half: I will have a bunch of people (in hundreds) to cluster into groups of 8 according to criteria describing their unsuitability. I say "unsuitability" because what I'm looking for might be called an "anti-matchmaking" algorithm: rather than increase the chances that A and B will end up in the same group of 8 because they share a particular characteristic, I want to decrease the chances.
Continuing with the matchmaking/anti-matchmaking analogy, imagine a small town where there's a limited pool of eligible partners, and once a month the local town hall hosts a singles event, seating people at tables of eight for dinner and drinks. The organizers pay attention to who's attended in the past and with whom they'd been seated, and wish to avoid assigning anyone to a table with a person they'd sat with before (within reason; perhaps only the previous two or three events would be considered).
To my mind, the computational requirements in order to minimize the potential for I-sat-with-you-last-time grow enormously as does the number of participants. A simple brute-force method -- examine every possible combination, assign penalty scores according to seating conflicts (assigning, perhaps, a higher penalty for having sat together one event ago, but a smaller penalty for two events, etc.), then sort the results and take the lowest-penalty-sum result as the answer -- would work, but be at best ungainly and at worst impossible.
I'm sure there are much more elegant approaches to solving this -- some of which I might be able to understand myself, some of which only with the aid of someone who specializes in math or computer science -- but I don't even know where to begin to look for such approaches, much less evaluate their suitability.
So -- if all I get out of posting this message is "just google XXXXXXXX and YYYYYYYYY", then I'll be one big step ahead of where I am now, since right now I don't know what to look for.
Thanks for wading through this post. I appreciate any suggestions.
Previous Topic
