[Algoritme] Matching nxn groepen bij "top m"

[dtech]

Volgende probleem probeer ik uit te werken als oefening en voor de lol:

Er zijn 2 groepen van n objecten ("mensen" als je het makkelijker wilt maken om er over na te denken), groep A (kiezers/mannen) en groep B (gekozenen/vrouwen). Elk object uit groep A maakt een top-m (bijv. top 10) lijstje met wie zei graag gematched willen worden, naar volgorde van voorkeur.

Opdracht: maak een algoritme dat een zo goed mogelijke matching vormd. "goed mogelijk" heb ik niet gedefiniëerd, maar wel geldt dat een matching van A naar B die buiten A's top m staat zeer onwenselijk is.

Natuurlijk is er geen garantie dat dat altijd kan (tenzij m=n), maar gevallen die je in overweging kunt nemen zijn "gelijk verdeelt" (er is dus een stable matching), "populair" (1/2 n van B is populair en staat dus vaak in de top m) en "strict populair" (alle A's hebben dezelfde lijst)

De opdracht is geen huiswerk o.i.d., ik heb hem zelf verzonnen.

Mijn voorlopige idee staat hieronder

spoiler:

GS-algorithm gaat niet werken (onaangepast), tenzij n=m. Als voorkeur-lijst voor B zou je de "inverse" voorkeur kunnen gebruiken van groep A als geheel: object uit B prefereert dus alle object uit A waar het op de eerste plaatst staat, daarna alle objecten uit A waar het op de tweede plaatst staat enz.
Ben nu bezig het ook echt te implementeren en kijken of ik ergens vastloop.

Een redelijk "dom" algoritme, wat daarentegen wel heel effectief zou kunnen zijn, is om een score toe te kennen aan elke set van matches en ze domweg allen te berekenen en de beste te kiezen. Je zou bijv. kunnen zeggen m punten voor een A-B match waarbij B op de eerste plaats stond, m-1 punten voor een A-B match waarbij B op de tweede plaats stond enzovoort. Omdat je wil voorkomen dat A-B matches er komen die ongewenst zijn zou je daar strafpunten voor kunnen geven, bijvoorbeeld -2m punten.

Nadeel is dat dit algoritme zeer inefficiënt zou zijn, aangezien er n! verschillende matches zijn en O(n!) zo'n beetje de slechtste looptijd is die je kunt hebben. Maar misschien dus wel effectief bij kleinere n. Voordeel is wel dat als dit een echte situatie zou zijn je de paar beste oplossingen zou kunnen geven waarna iemand op andere overwegingen de uiteindelijke keuze kan maken.

Ik ben benieuwd of er mensen met ideeën komen

[Xuj]

Hm.. Interessant.

Is het niet onmogelijk om een keuze te maken, aangezien deze 'kiezers' geen verdere waarden hebben?
Alle kiezers zijn dus in dit geval gelijk en geen van hen heeft een zwaardere stem.
In het geval van een gelijke keus is er dan toch geen manier om te beslissen wie nu wie krijgt?

Wat ik nu heb is een onmiddelijke toekenning van het lid uit B aan een lid uit A, als het lid uit A de enige is met genoemd lid uit B op nummer één. Andere leden die op dezelfde plek gekozen zijn worden 'gedeeld' over de kiezers die hen gekozen hebben.

[Grijze Vos]

dtech schreef op woensdag 12 januari 2011 @ 14:00:
Opdracht: maak een algoritme dat een zo goed mogelijke matching vormd. "goed mogelijk" heb ik niet gedefiniëerd, maar wel geldt dat een matching van A naar B die buiten A's top m staat zeer onwenselijk is.

Ben je geinteresseerd in het algoritme, of in de definitie van "goed mogelijk". Dat zijn namelijk twee losse deelproblemen die los staan van elkaar. Die eerste kun je overigens uberhaupt niet maken zonder de tweede.

[Soultaker]

Als je de wenselijkheid (of onwenselijkheid) van een match kunt uitdrukken als een reëel getal en accepteert dat de beste oplossing die is met de hoogste (of laaagste) som daarvan, dan heb je een simpel assignment probleem te pakken. Daarvoor zijn standaardalgoritmen beschikbaar.

Wat betreft de waardering van matches, zoek je een monotone functie die aan posities een waardering toekent. Als x op de n'de plek staat bij y, dan is de matching x-y bijvoorbeeld 50+(10-n)² waard, en anders nul, maar je kunt natuurlijk allerlei andere functies verzinnen die een meer of minder zinnig resultaat geven. Grijze Vos heeft gelijk dat er verder weinig concreets over te zeggen valt als je niet nader kunt specificeren wat een oplossing "goed" maakt.

[NMe]

Algoritmes mogen in Software Engineering & Architecture, zie Waar hoort mijn topic?

PRG>>SEA

Verder zou je Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!* even kunnen doorlezen, die opdracht komt sterk overeen met wat jij aan het doen bent en je zou wat ideeën kunnen opdoen uit de inzendingen die nog steeds beschikbaar zijn.