[Alg] Algoritme bepaling

[Orphix]

Hallo,

Ik ben op dit moment bezig met een stukje programmatuur die het volgende moet berekenen:

Stel je hebt n aantal mensen, die in z eetrondes in y groepen moeten worden ingedeeld.

Het doel van het algoritme is dat elk persoon uiteindelijk zoveel mogelijk andere personen leert kennen.

Op dit moment pas ik dit toe door een soort van simulatie algoritme:
- Ik heb een kamer met y groepen.
- Vervolgens laat ik ze een voor een de 'kamer' binnenkomen.
- Op basis van een utility functie wordt de keuze bepaald tussen de groepen voor dat persoon
- Van elk persoon houd ik bij hoevaak hij elk ander persoon heeft gezien (waar de utility functie dus mee rekent).
- Dit proces herhalen voor elke sessie

Nu werkt dit best aardig met mooie aantallen. Bijvoorbeeld 16 personen, 4 groepen en 5 sessies. Je zal zien dat elk persoon elk ander persoon precies eenmaal ziet. Optimaal dus.

Echter stel ik nu 17 personen, 4 groepen, 5 sessies. Dan loopt het verkeerd. De 17e persoon ziet de helft van de personen 2x, andere personen weer geen een keer. Dit is niet gewenst.

Ik ben dus op zoek naar een algoritme waarbij voor elk individu:
- het aantal personen die hij kennismaakt maximaal is en
- de standaarddeviatie tussen de personen die hij kennismaakt minimaal

Hoewel ik algoritmes kan bedenken om het te verbeteren (bv door de volgorde van de kamer laten binnenlopen elke sessie anders te laten verlopen), blijf ik het lastig vinden om bewijs te vinden hoe optimaal het resultaat is.

Mijn vraag aan de informatici is in welke hoek ik moet zoeken?! Op welk algoritme probleem lijkt dit? Is het een combinatorisch probleem? NP-compleet?

Alvast bedankt!

[4VAlien]

Er staat me iets bij van Gaulois lichamen (algebra). Maar dat ga ik even voor je nakijken, het was niet m'n sterkste punt Je ziet het vanzelf als deze post nog geedit wordt.

edit: Galois rijen zijn hierbij betrokken maar die werken alleen voor een aantal deelnemers p^n met p een priem getal. Voor het getal 17 e.d. heb je daar dus niet zoveel aan en voor 16 had je al een oplossing..

[ Voor 39% gewijzigd door 4VAlien op 12-01-2006 13:16 ]

[bille]

Dit is een "operations research" vraagstuk, doet mij iig een beetje denken aan "the traveling salesman" problematiek (ter info: dat probleem is niet oplosbaar, dwz: een 100% oplossing zal je niet vinden).

optie 1:
- Probeer eerst eens uit te rekenen hoeveel verschillende combinaties er zijn... (waarschijnlijk best veel )
- programmeer het zo dat je alle mogelijke combinaties na loopt en de de meest optimale selecteerd.
optie 2: verdiep je in (non-)Linear Programming en wellicht dat je daarmee iets kan.

Indien je de opdracht niet voor school hebt maar het een commercieel vraagstuk is: neem eens contact op met www.cqm.nl

[Wouter Tinus]

bille schreef op donderdag 12 januari 2006 @ 12:47:
Dit is een "operations research" vraagstuk, doet mij iig een beetje denken aan "the traveling salesman" problematiek (ter info: dat probleem is niet oplosbaar, dwz: een 100% oplossing zal je niet vinden).

Traveling salesman is prima oplosbaar, alleen zijn de optimale oplossingen (vrijwel zeker) niet op een andere manier dan bruteforce te vinden .

[joepP]

Het geval met 17 personen is niet moeilijk, daarvoor kan je gewoon de oplossing voor 16 personen nemen, en persoon 17 altijd bij persoon 1 aan tafel zetten. Sim-pel

Je kan ook zien dat het geval van 16 personen, 4 groepen, 5 rondes op het grensje van mogelijk is. Je moet immers 16 * 15 / 2 = 120 paren bij elkaar aan tafel hebben. Elke tafel bevat 4 personen, dus 6 paren. Totaal 4 tafels en 5 ronden, dus je kan maximaal 120 paren kennis laten maken. Kantje boord. Of deze berekening ook omgekeerd geldt weet ik niet, maar ik vermoed haast van niet. De getallen zijn namelijk wel erg symmetrisch.

Ik zie niet in waarom de vorige poster met Travelling Salesman aan komt zetten, maar dat probleem lijkt hier volgens mij in de verste verte niet op. Een ILP formulering is uiteraard geen probleem, maar daarmee los je je probleem ook niet zomaar op, en inzicht krijg je er ook niet echt van. Ik durf eigenlijk geen probleem te noemen wat hier echt op lijkt uit de grafentheorie, en uitspraken over de complexiteit durf ik ook niet aan.

Mocht je er niet uitkomen dan kan je altijd nog een local-search algoritme proberen. Gok een willekeurige tafelverdeling over de ronden, en kijk of er door mensen van tafel te laten verwisselen verbeteringen mogelijk zijn. Maar dat had je zelf ook vast al bedacht.

[joepP]

Wouter Tinus schreef op donderdag 12 januari 2006 @ 13:49:
[...]

Traveling salesman is prima oplosbaar, alleen zijn de optimale oplossingen (vrijwel zeker) niet op een andere manier dan bruteforce te vinden .

Dat is niet helemaal waar.

Er zijn hele goede heuristieken voor het geval dat de steden punten op een kaart zijn. Als de onderlinge afstanden echter willekeurig zijn is het probleem moeilijker. Maar in de praktijk heb je gelijk.

[RickN]

tijdens de eerste ronde stop je iedereen in één groep, de andere groepen laat je leeg.

rondes 2 tm z zijn overbodig.

Of hebben groepen een min/max grootte?

[leuk_he]

RickN schreef op donderdag 12 januari 2006 @ 14:18:
tijdens de eerste ronde stop je iedereen in één groep, de andere groepen laat je leeg.

Dat is niet de vraagstelling jij stelt y op 1, maar hij wil ook een y >1 aan kunnen.

[RickN]

leuk_he schreef op donderdag 12 januari 2006 @ 14:22:
[...]


Dat is niet de vraagstelling jij stelt y op 1, maar hij wil ook een y >1 aan kunnen.

Oh die andere groepen zijn er wel (zie het als tafels ofzo), maar ze zijn gewoon leeg.

Goed, aangenomen dat een groep niet leeg mag zijn:

ronde 1:
groep 1: personen 1-14
groep 2: persoon 15
groep 3: persoon 16
groep 4: persoon 17

ronde 2:
groep 1: personen 4-17
groep 2: persoon 1
groep 3: persoon 2
groep 4: persoon 3

ronde 3:
groep 1: personen 1,2,3,15,16,17

klaar.

Vraag blijft, wat zijn de eisen aan de grootte van een groep.

[Orphix]

bille schreef op donderdag 12 januari 2006 @ 12:47:
Dit is een "operations research" vraagstuk, doet mij iig een beetje denken aan "the traveling salesman" problematiek (ter info: dat probleem is niet oplosbaar, dwz: een 100% oplossing zal je niet vinden).

optie 1:
- Probeer eerst eens uit te rekenen hoeveel verschillende combinaties er zijn... (waarschijnlijk best veel )
- programmeer het zo dat je alle mogelijke combinaties na loopt en de de meest optimale selecteerd.
optie 2: verdiep je in (non-)Linear Programming en wellicht dat je daarmee iets kan.

Indien je de opdracht niet voor school hebt maar het een commercieel vraagstuk is: neem eens contact op met www.cqm.nl

Ik heb dynamische programmering behandeld gekregen. Echter voordat je met zulke methodieken kan werken moet het probleem voldoen aan enkele eisen (Markov keten). Een belangrijke eis is dat een oplossing slechts dan berekend kan worden wanneer acties genomen in het verleden niet meetellen voor het acties/resultaat in de toekomst. Ik vraag me echter af of dit waar is in dit geval aangezien wanneer bv persoon A bij persoon B in het verleden bij elkaar hebben gezeten dit invloed heeft op de keuzes in de toekomst (immers de utiliteit om persoon A en B bij elkaar te zetten is kleiner)

Maar misschien moet ik het probleem op een andere manier opstellen/benaderen dat dit wel een mogelijkheid is. Ik had er zelf nog niet aan gedacht iig!

joepP schreef op donderdag 12 januari 2006 @ 13:50:
Het geval met 17 personen is niet moeilijk, daarvoor kan je gewoon de oplossing voor 16 personen nemen, en persoon 17 altijd bij persoon 1 aan tafel zetten. Sim-pel

Probleem is dat je dan een onevenwicht krijgt. Immers ziet persoon 17 persoon 1 heel vaak en vice-versa. Bovendien krijgen zowel persoon 1 als persoon 17 per beurts slechts twee 'andere' personen te zien waardoor ze ook nog eens met minder aantal verschilledende personen in aanraking komen.
Daarom ook de eis (die ik overigens zelf bedacht heb, maar het leek me logisch):
- de standaarddeviatie tussen de personen die hij kennismaakt minimaal

RickN schreef op donderdag 12 januari 2006 @ 14:27:
Vraag blijft, wat zijn de eisen aan de grootte van een groep.

Om even een stap in de praktijk te nemen. Stel je organiseert een introductie voor aankomende studenten. Je organiseert vier eetrondes tijdens deze periode. Er zijn 17 personen en vier tafels.
Je wilt aan elke tafel ongeveer evenveel personen hebben. Dus 4 per tafel. Aan een tafel zullen er dan vijf komen te zitten. Dat is nu eenmaal niet anders.

Oftewel de min grootte is FLOOR(n/y), de max grootte CEILING(n/y).

Ik hoop dat het probleem zo duidelijker is omschreven.

---
Wat voorbeelden van planningen (applicatie is excel add-in):
16 personen, 4 groepen, 5 sessies. Optimale situatie dus
17 personen, 4 groepen, 5 sessies. Zeventiende persoon komt er bekaaid vanaf (veel personen 2x zien of 0x). Deviatie 15 voor persoon 17, voor anderen is het prima
17 personen, 4 groepen, 5 sessies. Na elke sessie is de lijst zo gesorteerd dat de persoon met de grootste als eerste mag kiezen. Voor persoon 17 is di tbeter. Maar het ziet er allemaal chaotisch uit en lijkt verre van optimaal.

[ Voor 12% gewijzigd door Orphix op 12-01-2006 15:34 ]

[joepP]

Volgens mij snap je mijn voorbeeldje van 17 man niet. Als je zorgt dat persoon 1 altijd aan de tafel zit met 5 man, kan je 17 daar altijd bij aan tafel zetten. Ik zie alleen niet hoe je dit kan uitbreiden naar 18 man, dus of je er echt wat aan hebt weet ik niet.

Maar waarom probeer je niet een local-search? Begin gewoon met een willekeurige verdeling, en wissel mensen van tafelpositie als dat zinvol is. Herhaal tot er geen verbetering meer mogelijk is, en sla de uiteindelijke oplossing op. Dit kan je natuurlijk zo vaak herhalen als je wilt. Je kan ook wat ingewikkelder wisselstrategieen proberen (drie mensen laten wisselen bijvoorbeeld) als dit niet zo goed werkt.