Welk algoritme gebruiken voor verdeling stageplaatsen?*

[JokerLash]

Voor school moeten we een applicatie maken waar studenten 3 voorkeuren kunnen opgeven voor stage opdrachten. De stagecoördinator moet mbv een algoritme een goed beeld krijgen hoe deze het beste ingedeeld kunnen worden. Zodat bij bijna iedere student zoveel mogelijk wordt voldaan aan zijn of haar voorkeur.

Welk algoritme kunnen we het beste hiervoor gebruiken?

[Pkunk]

Modbreak:

Waarom zie ik je wel klagen, maar geen topicreport? Om de sfeer binnen een topic niet te verzieken is het hier op GoT expliciet niet de bedoeling om als user mensen terecht te gaan wijzen; daar zijn topicreports voor, zodat een moderator dat kan doen.

[ Voor 85% gewijzigd door NMe op 24-01-2006 23:30 ]

[Koppensneller]

Modbreak:

En dat geldt ook voor jou.

[ Voor 97% gewijzigd door NMe op 24-01-2006 23:25 ]

[Nielson]

Probeer het eens met 'Fuzzy Logic' i.p.v. een vaststaand algoritme, pas ook goed bij je TS

[JokerLash]

Nee ik vraag alleen of een van jullie weet welk algoritme we hiervoor het beste kunnen gebruiken, de implementatie in C doen we ZELF!!!

[Varienaja]

't komt neer op 't volgende:

- bepaal alle mogelijke verdelingen van stage-opdrachten over de studenten
- bereken de gemiddelde 'tevredenheid' van de studenten hierover
- de verdeling met de hoogste score is de beste.

Dit probleem is niet efficient op te lossen, en jouw opdracht zal waarschijnlijk precies gaan over hoe je hiervoor toch nog een goede oplossing kunt krijgen binnen eindige tijd.

Volgens mij is dit gewoon op te vatten als een variant op het 'handelsreizigers-probleem', daarover kan je op internet zeker weten veel informatie en voorbeeld-algoritmen vinden.

[ Voor 17% gewijzigd door Varienaja op 24-01-2006 23:17 ]

[Johnny]

De voorkeuren van de studenten hebben waarschijnlijk een volgorde. Je moet dus een lijst maken van alle studenten die een bepaalde stageopdracht willen en deze sorteren op de volgorde van de voorkeuren, studenten die de opdracht als eerste keuze hadden komen dan bovenaan.

Dit zegt touwens nog niet sover hoe geschikt een student is voor een opdracht, dan heb je meer variablen nodig zoals de aard van de opdracht en misschien de cijfers van de studenten voor bepaalde vakken.

[JokerLash]

Varienaja schreef op dinsdag 24 januari 2006 @ 23:14:
't komt neer op 't volgende:

- bepaal alle mogelijke verdelingen van stage-opdrachten over de studenten
- bereken de gemiddelde 'tevredenheid' van de studenten hierover
- de verdeling met de hoogste score is de beste.

Dit probleem is niet efficient op te lossen, en jouw opdracht zal waarschijnlijk precies gaan over hoe je hiervoor toch nog een goede oplossing kunt krijgen binnen eindige tijd.

Volgens mij is dit gewoon op te vatten als een variant op het 'handelsreizigers-probleem', daarover kan je op internet zeker weten veel informatie en voorbeeld-algoritmen vinden.

Traveling salesman had ik ook al aan gedacht....maar das toch niet te doen omdat er 3 voorkeuren in volgorde opgegeven kunnen worden.

[MBV]

Wat heb je zelf aan onderzoek gedaan?

Ik zou hierbij uitgaan van statistische gegevens. Ga een paar mensen interviewen die een stage hebben gedaan, waar zij hem op hebben geselecteerd en of dat achteraf goed was. Ook kan je aan hun vragen waar ze op hadden moeten letten, achteraf gezien. Als je een paar van die bepalende factoren hebt gevonden, kan je een enquete doen onder de doelgroep. Ik zou daarvoor aan een modje van W&I vragen of je een poll neer mag zetten .

Als je die basisinfo hebt (welke 3 inputs je gaat krijgen) kan je eens gaan nadenken hoe je het samenvoegt. En dan kan je de dingen van hierboven gaan toepassen.

[ Voor 16% gewijzigd door MBV op 24-01-2006 23:23 ]

[JokerLash]

Johnny schreef op dinsdag 24 januari 2006 @ 23:15:
Dit zegt touwens nog niet sover hoe geschikt een student is voor een opdracht, dan heb je meer variablen nodig zoals de aard van de opdracht en misschien de cijfers van de studenten voor bepaalde vakken.

De geschiktheid van persoon bij opdracht is bij de vraagstelling totaal niet van toepassing.

[Varienaja]

JokerLash schreef op dinsdag 24 januari 2006 @ 23:22:
Traveling salesman had ik ook al aan gedacht....maar das toch niet te doen omdat er 3 voorkeuren in volgorde opgegeven kunnen worden.

Volgorde van bezoeken van steden, waarbij je de minimale afstand zoekt
vs
Volgorde van stageopdrachten over de studenten waarbij je de maximale tevredenheid zoekt

Je moet idd een formule voor 'tevredenheid' gaan maken, en dat heeft met die 3 voorkeuren te maken. Maar het probleem is in principe 1:1 hetzelfde.

[NMe]

JokerLash schreef op dinsdag 24 januari 2006 @ 23:14:
Nee ik vraag alleen of een van jullie weet welk algoritme we hiervoor het beste kunnen gebruiken, de implementatie in C doen we ZELF!!!

Tsja, met zo'n magere topicstart als deze kun je natuurlijk wel verwachten dat je dergelijke replies zoals hierboven krijgt op je topic. Hier in Programming & Webscripting verwachten we van users dat ze op zijn minst een beetje vooronderzoek doen voor ze hun topic starten, en dan natuurlijk ook in het topic vermelden wat ze gedaan hebben om tot een oplossing te komen, en dat mis ik hier een beetje, en zo te zien was ik niet de enige.

[MBV]

JokerLash schreef op dinsdag 24 januari 2006 @ 23:23:
[...]


De geschiktheid van persoon bij opdracht is bij de vraagstelling totaal niet van toepassing.

Impliciet wel: als de persoon niet geschikt is, zal hij ook erg ontevreden zijn. Als ik een stage had gehad waarbij ik een kleuterklas moest leiden, zou het meer lijden worden, maar dan voor mij . Zonder gekheid: als je iets krijgt waar je te goed/niet goed genoeg voor bent, ga je het niet naar je zin hebben. En helemaal niet naar je zin met je cijfer

offtopic:
@-NME- Als je dan al die kritiek weghaalt, met als mededeling dat een modje die taak overneemt, waarom zeg je er dan niks van? Ik wil bloed zien!

[ Voor 14% gewijzigd door MBV op 24-01-2006 23:47 ]

[Confusion]

JokerLash schreef op dinsdag 24 januari 2006 @ 23:07:
Voor school moeten we een applicatie maken waar studenten 3 voorkeuren kunnen opgeven voor stage opdrachten. De stagecoördinator moet mbv een algoritme een goed beeld krijgen hoe deze het beste ingedeeld kunnen worden. Zodat bij bijna iedere student zoveel mogelijk wordt voldaan aan zijn of haar voorkeur.

Welk algoritme kunnen we het beste hiervoor gebruiken?

Dat is niet te beantwoorden zonder dat je criteria geeft voor 'het beste' en 'zoveel mogelijk'. Moeten zoveel mogelijk studenten hun eerste keus krijgen? Als je de eerste keus drie punten geeft, de tweede twee en de derde een, moet het totaal aantal punten dan maximaal zijn? De bepaling van welk algoritme is iets dat eigenlijk geen P&W zaak is.

[Verwijderd]

JokerLash schreef op dinsdag 24 januari 2006 @ 23:07:
Voor school moeten we een applicatie maken waar studenten 3 voorkeuren kunnen opgeven voor stage opdrachten. De stagecoördinator moet mbv een algoritme een goed beeld krijgen hoe deze het beste ingedeeld kunnen worden. Zodat bij bijna iedere student zoveel mogelijk wordt voldaan aan zijn of haar voorkeur.

Welk algoritme kunnen we het beste hiervoor gebruiken?

Volgens mij is dit probleem zeer geschikt voor grafentheorie
Stel dat elke student en elke stage plek een node in de graaf voorsteld. De lijnen in de graaf zijn de voorkeuren voor een bepaalde stageplek. Deze kan je ook een zwaarte geven om voorkeur tussen de 3 plaatsen aan te geven. Vervolgens moeten er matchings gezocht worden (setjes van 2) in een dusdanige manier dat zoveel er maximale matching is. Daar zijn een aantal mogelijkheden voor, van deze mogelijkheden moet degene gekozen worden met het kleinste cumalatieve zwaarte (of grootste afhankelijk van wat je met de zwaartes gedaan hebt).

Dit is natuurlijk allemaal erg theoretisch maar dit kan allemaal vertaald worden naar C

[Zoijar]

Volgens mij is het een twee dimensionaal kopelings probleem, dat is _niet_ NPC en dus ook niet equivalent aan TSP (3+ dimensies _wel_, ie. een leraar, een lokaal en een student, maar alleen een lokaal en een student is polynomiaal). Het is dus gewoon polynomiaal op te lossen met lineaire programmering.

(m'n masters scriptie bevat een stukje over dit probleem (pag. 53), alleen zoek ik de grootste cardinaliteit matching, en dan kan je een greedy algoritme gebruiken. Jij zoekt minimum weight, en dat gaat net iets anders. De combinatie maximale cardinaliteit + minimum weight is overigens wel weer NPC...)

[ Voor 43% gewijzigd door Zoijar op 25-01-2006 11:10 ]

[chris]

hokitoki: ik kan me niet voorstellen dat dat snel is. Verder kan ik niet zo snel een snelle oplossing bedenken. Natuurlijk is het heel simpel om het antwoord te krijgen, dat is inderdaad brute-forcen. De kunst is natuurlijk om het snel te krijgen.

Zijn er trouwens evenveel studenten als stageplaatsen?

[Verwijderd]

chris schreef op woensdag 25 januari 2006 @ 11:21:
hokitoki: ik kan me niet voorstellen dat dat snel is. Verder kan ik niet zo snel een snelle oplossing bedenken. Natuurlijk is het heel simpel om het antwoord te krijgen, dat is inderdaad brute-forcen. De kunst is natuurlijk om het snel te krijgen.

Zijn er trouwens evenveel studenten als stageplaatsen?

Er zijn geloof ik enkele algoritmes die dit nog redelijk snel kunnen. Maar dit blijft volgens mij een behoorlijk complex probleem waar je alleen sneller kunt worden met greedy algoritmes die helaas niet altijd het optimale antwoord geven. Daarnaast is natuurlijk ook van belang of het snel moet, misschien schiet dat het doel voorbij en wordt het alleen maar lastiger voor de TS of juist uitdagender

[n3ck]

Dat probleem kun je het beste herschrijven als een OR-probleem; gaat het snelste en is het makkelijkste.

Nog ff verder gedacht, maar volgens mij moet het zo wel in OR te passen zijn.

2 matrixen:
voorkeur:
studenten (1..n), voorkeur (1..m)
(hoe je hem precies invult maakt niet uit; voor student 1 zou [0,0,10,0,0,20,0,0,70] bijvoorbeeld kunnen)

beslissing
studenten (1..n), voorkeur (1..m)

constraint
1 student per stage dus som van de voorkeuren per student is kleiner gelijk dan 1

max: som(beslissing*voorkeur)

[ Voor 68% gewijzigd door n3ck op 25-01-2006 17:09 ]

[djluc]

Wat gebeurt er als je eerst alle nr1 stageplaatsen vol zet, vervolgens de mensen die er niet in pasten de indelen bij de 2e keuze en vervolgens bij de 3e? Daarna ga je kijken wie er over zijn, je pakt dus hun 1e keuze, streept bij die stage iemand weg en plaatst die bij een alternatief. Dan krijg je vanzelf een correcte oplossing. Niet gebaseerd op enige theorie natuurlijk maar gewoon op doorplaatsen.

[MBV]

Goede reacties, had ik eigenlijk niet verwacht met zo'n topicstart. Maar ik ben toch erg benieuwd wat de TS zelf al had gevonden, en welke factoren hij gaat gebruiken. Ik zou namelijk geen 3 factoren kunnen verzinnen om mijn stage mee te vinden. Dus TS: wat is het stuk voor het algoritme? Wat zijn de specificaties waar het algoritme aan moet voldoen?
_{Uiteraard te geven in wiskundige notatie, iets als (Maximum x::(Sum y: y element of Student: ...))}

[Eelke Spaak]

Je kan ook eens zoeken op constraint satisfaction met neurale netwerken. Dat is natuurlijk equivalent met een algoritme, maar dan hoef je het zelf niet meer te bedenken en kan je gewoon de regeltjes volgen om het net 'up te wiren' en dan gaat het vanzelf .

[chris]

Ik denk dat dit probleem prima wiskundig te modelleren is, en dat een neuraal netwerk helemaal niet handig is. Een neuraal netwerk kan een goede oplossing geven, maar het is er niet op gebouwd om een optimale oplossing te geven. Ook moet je het trainen, en dat zou niet nodig zijn. Een wiskundig bewijsbare oplossing is denk ik wenselijk.

djluc: ik denk dat een greedy-oplossing zoals jij die schetst geen optimale oplossing zal geven. Ik heb even geen tijd om een tegenvoorbeeld te verzinnen, maar volgens mij gaat dat niet werken.

[joepP]

Er zijn geloof ik enkele algoritmes die dit nog redelijk snel kunnen. Maar dit blijft volgens mij een behoorlijk complex probleem waar je alleen sneller kunt worden met greedy algoritmes die helaas niet altijd het optimale antwoord geven. Daarnaast is natuurlijk ook van belang of het snel moet, misschien schiet dat het doel voorbij en wordt het alleen maar lastiger voor de TS of juist uitdagender

Dit probleem heet maximum weight matching, en er zijn algoritmen die inderdaad redelijk snel zijn. Met deze term is het eenvoudig op google zoeken