[VB(A)/ALG] Indelings algoritme ontwerp

[Clock]

Goedenavond,

Ik ben voor mijn werk een tooltje (lees: excel sheet) aan het schrijven om het een en ander wat soepeler te laten verlopen. Het programmeren an-sich is geen probleem, echter heb ik hulp nodig met een algoritme-ontwerp.

Situatie: er zijn ongeveer 10-15 personen (uit een pool van 60), die elk een 1e, 2e en 3e voorkeur hebben voor een 'object'. Er zijn in totaal 10 objecten. Ik heb een overzicht die per object aangeeft welke personen dit in hun voorkeurslijst hebben staan.

code:

                   1e V                       2e V             3e V
Object 1         persoon 2                 persoon 6        persoon 8
                                           persoon 3
Object 2         persoon 3                                  persoon 9
                 persoon 8
Object 3                                   persoon 4        persoon 2
Object 4         persoon 9          
etc

Ik wil bereiken dat een een zo goed mogelijke verdeling wordt gemaakt van de mensen over de objecten. Dit houdt in dat ieders voorkeur waar mogelijk maximaal gerespecteerd wordt.

Snelheid is niet van belang, (n)evenals absolute nauwkeurigheid. Ik ben op zoek naar een (evt bestaand) klein en relatief simpel algoritme, wat geïmplementeerd moet worden in VBA. Kunnen jullie mij helpen met een aanpak of een verwijzing naar een plek waar ik meer info kan vinden?

Alvast bedankt

Edit: zie deze post voor grafische verduidelijking

Ik was van mening dat een topic over programmeer ontwerpen thuishoort in PROG ipv in het office subfora. Indien ik verkeerd gedacht heb mijn excuses. Edit: overigens zie ik net dat ie beter in SE&A had gepast

[ Voor 9% gewijzigd door Clock op 14-03-2010 20:35 ]

[_js_]

10 objecten over 10 personen verdelen is niet een heel groot aantal, dit kun je wel brute forcen in korte tijd (10! mogelijkheden), als een van de objecten overeenkomt met een voorkeur zou je bijvoorbeeld resp. 4, 2, 1 punten kunnen geven, en het hoogste gezamenlijke puntental als oplossing nemen. Je kunt nog een deel van de mogelijkheden weghalen als een object maar bij weinig personen de voorkeur heeft.

[Clock]

_js_ schreef op donderdag 11 maart 2010 @ 22:55:
10 objecten over 10 personen verdelen is niet een heel groot aantal, dit kun je wel brute forcen in korte tijd (10! mogelijkheden), als een van de objecten overeenkomt met een voorkeur zou je bijvoorbeeld resp. 4, 2, 1 punten kunnen geven, en het hoogste gezamenlijke puntental als oplossing nemen. Je kunt nog een deel van de mogelijkheden weghalen als een object maar bij weinig personen de voorkeur heeft.

Zolang de executietijd beneden de 30 seconden blijft is er geen probleem. Een puntensysteem is iets wat mij ook te binnen schoot. Het enige probleem leek mij het voorkomen dat een persoon in dezelfde berekening 2 of 3 maal wordt meegenomen (omdat hij 3 maal vermeld staat in het voorkeurenschema). Als echter alle 3 miljoen mogelijkheden worden afgelopen is dat geen probleem.

Een loop die alle mogelijkheden afgaat, een puntentotaal berekend, de tot dan toe best scorende opstelling opslaan. Als het goed is komt daar dan de beste uit. Lijkt me goed, zijn er ook nog simpele algoritmische oplossingen?

[Leftblank]

Eventueel kun je inspiratie opdoen op het stable marriage problem op Wikipedia, er is een algoritme gegeven. Niet triviaal, maar wel de optimale indeling . Wellicht zijn er ook nog eenvoudigere oplossingen te vinden wat dit betreft. Mocht snelheid en optimaliteit echt geen probleem zijn dan kun je dit natuurlijk skippen, het is zeker geen eenvoudige oplossing.

[Soultaker]

Veel simpeler dan brute-force wordt 't nooit natuurlijk. Efficiënter wel.

Is het nu de bedoeling dat elke persoon precies één object krijgt? Of kan dat nog wisselen?

[Clock]

Leftblank schreef op donderdag 11 maart 2010 @ 23:19:
Eventueel kun je inspiratie opdoen op het stable marriage problem op Wikipedia, er is een algoritme gegeven. Niet triviaal, maar wel de optimale indeling . Wellicht zijn er ook nog eenvoudigere oplossingen te vinden wat dit betreft. Mocht snelheid en optimaliteit echt geen probleem zijn dan kun je dit natuurlijk skippen, het is zeker geen eenvoudige oplossing.

Ik heb het doorgenomen, maar ik geloof niet dat het algoritme werkt bij een ongelijk aantal mannen en vrouwen (objecten en personen). Ook zal het dan aangepast moeten worden aan de 'beperkte' voorkeuren (van 3 objecten ipv alle objecten). Oftewel: een wat te moeilijk algoritme waarvan de implementatie erg moeilijk gaat worden in een 'gebrekkige taal' als VBA (geen array-sort functies bijv). Toch erg bedankt voor je inbreng, is leuk leesvoer.

Soultaker schreef op vrijdag 12 maart 2010 @ 00:02:
Veel simpelere dan brute-force wordt 't nooit natuurlijk. Efficiënter wel.

Is het nu de bedoeling dat elke persoon precies één object krijgt? Of kan dat nog wisselen?

Elk object moet zoveel mogelijk aan een persoon gekoppeld worden. Mochten de voorkeuren voor 1 object compleet ontbreken moet daar degene komen die ook nergens anders past (lees: minst goed indeelbare). Ook zal het misschien in de toekomst nodig zijn om een object aan te wijzen (max 2 of 3) waar 2 personen bij gevonden moeten worden. Maar dat is vooralsnog toekomstmuziek.

[ Voor 24% gewijzigd door Clock op 12-03-2010 00:20 ]

[321X]

Ik snap je omschrijving niet helemaal...

Stel je hebt 9 personen met 3 voorkeuren (zoals je nu hebt aangegeven), wil je dan dat pér object 3 personen per voorkeur gekozen worden?

In je omschrijving zeg je "die elk een 1e, 2e en 3e voorkeur hebben voor een 'object'. Er zijn in totaal 10 objecten" daaruit maak ik op dat elk persoon bij elk object en 3 voorkeuren heeft...

[Clock]

321X schreef op vrijdag 12 maart 2010 @ 10:00:
Ik snap je omschrijving niet helemaal...

Stel je hebt 9 personen met 3 voorkeuren (zoals je nu hebt aangegeven), wil je dan dat pér object 3 personen per voorkeur gekozen worden?

In je omschrijving zeg je "die elk een 1e, 2e en 3e voorkeur hebben voor een 'object'. Er zijn in totaal 10 objecten" daaruit maak ik op dat elk persoon bij elk object en 3 voorkeuren heeft...

Sorry voor de verwarring. Wat ik bedoel:
Er zijn een aantal objecten (nu 10, maar dit kan +-1)(een vast aantal: 8 ). Tevens zijn er zijn 10 tot 15 personen die verdeeld moeten worden over die objecten. Ik wil per object kunnen aangeven hoeveel personen aan dat object gekoppeld moeten worden (dit zal meestal 1 persoon zijn, maar soms 2).

Nu wil ik de personen niet random over de objecten verdelen, maar zoveel mogelijk rekening houden met de door hun opgegeven voorkeur. Elke persoon heeft 3 voorkeursobjecten opgegeven (1e, 2e en 3e voorkeur). Ik wil de beste verdeling voor het systeem als geheel (iedereen zoveel mogelijk tevreden => een zo hoog mogelijke totale tevredenheid).

Mochten er objecten zijn die geen voorkeur verdienen van elk van de personen, moet daar toch een persoon aan gekoppeld worden. Verder is het mogelijk dat er meer mensen zijn dan 'plaatsen' bij de objecten. In dit geval wordt de beste combo gemaakt en blijven er mensen over die niet worden toegewezen.

Lastig lastig

[321X]

Oke, duidelijk!

In eerste instantie zou ik denken om een object een weight geven om zo eerst de populariteit te bepalen. Alle objecten in een pool stoppen, de gene die aan meerdere personen gehangen kunnen worden komen dus meerdere keren voor. Deze sorteren op populariteit.

Dan zou je random de personen langs kunnen gaan en kijken of voorkeur 1 in de pool aanwezig is, zo niet voorkeur 2, zo niet voorkeur 3. Mocht dat niet het geval zijn, dan de eerst voorkomende in de lijst.

Je krijgt dan zo een eerlijke, random verdeling over de overgebleven niet-populaire objecten.

Zomaar een idee hoor

edit:
Populariteitsalgorithme toegevoegd

Om de populariteit te berekenen zou je misschien zoiets kunnen doen: (aantal objecten / 100) * (aantal keer gekozen voorkeur 1 * 1.2) * (aantal keer gekozen voorkeur 2 * 1.1) * (aantal keer gekozen voorkeur 3 * 1.0)

Voorkeur 1 heeft een grotere invloed dan 2 en 2 groter dan 3...

[ Voor 20% gewijzigd door 321X op 12-03-2010 10:40 ]

[Clock]

Om het duidelijk(er) te maken (ook voor mezelf) een overzicht van wat de bedoeling is:


Het is mogelijk dat het aantal personen kleiner dan, gelijk aan of groter dan het aantal objecten is. (aantal objecten is constant).

[ Voor 32% gewijzigd door Clock op 12-03-2010 11:14 ]

[Clock]

321X schreef op vrijdag 12 maart 2010 @ 10:36:
Oke, duidelijk!

In eerste instantie zou ik denken om een object een weight geven om zo eerst de populariteit te bepalen. Alle objecten in een pool stoppen, de gene die aan meerdere personen gehangen kunnen worden komen dus meerdere keren voor. Deze sorteren op populariteit.

Dan zou je random de personen langs kunnen gaan en kijken of voorkeur 1 in de pool aanwezig is, zo niet voorkeur 2, zo niet voorkeur 3. Mocht dat niet het geval zijn, dan de eerst voorkomende in de lijst.

Je krijgt dan zo een eerlijke, random verdeling over de overgebleven niet-populaire objecten.

Zomaar een idee hoor

edit:
Populariteitsalgorithme toegevoegd

Om de populariteit te berekenen zou je misschien zoiets kunnen doen: (aantal objecten / 100) * (aantal keer gekozen voorkeur 1 * 1.2) * (aantal keer gekozen voorkeur 2 * 1.1) * (aantal keer gekozen voorkeur 3 * 1.0)

Voorkeur 1 heeft een grotere invloed dan 2 en 2 groter dan 3...

Dit lijkt op een idee dat ik bedacht had. Objecten sorteren op populariteit, minst populaire object eerst indelen (is vaak maar 1 keuze). Vervolgens alle objecten in oplopende populariteit langsgaan en steeds de persoon pakken die niet reeds gekoppeld is (beginnen bij 1e voorkeuren, dan 2e en dan 3e). Ik kan echter niet beoordelen of er dan een goede verdeling tot stand komt waarbij de maximale 'tevredenheid' kan worden behaald.

[321X]

Ik denk het wel, in elk geval wel als je zoals ik aangaf doe.

Want:

1) Als eerst wordt gekeken of je 1e voorkeur nog beschikbaar is
2) is dit neit het geval, je 2e voorkeur
3) is dit niet het geval, je 3e voorkeur
4) is geen van bovenstaande meer beschikbaar dan wordt de meest populaire gekozen

Je kan zelf natuurlijk bepalen wanneer je een volgend random persoon kiest, na het proberen van de 3 voorkeuren of na het proberen van 1x...

In de praktijk is het bijna nooit het geval dat iedereen 100% tevreden wordt, op deze manier haal je denk ik wel de hoogst mogelijke percentage.

Je kan het nog ingewikkelder maken door een relevantie mee te nemen (als dat al mogelijk is), dus als geen van je 3 keuzes meer beschikbaar zijn, een eventueel object te selecteren die gerelateerd is aan de voorgaande objecten.
Dit kan je denk ik relatief eenvoudig realiseren door iets als keywords (tags) aan objecten te hangen en dan a.d.v. de beschikbare keywords het populairste relevante object kiezen.

[Clock]

Het verschil tussen onze benadering is dat jij door de personen loopt en ik door de objecten. Ik ben even heel hard aan het denken hoe het er dan uit komt te zien bij jouw benadering.

Een 100% tevredenheid is niet haalbaar (wellicht in een unieke situatie). Ik wil bereiken dat iedereen zo tevreden mogelijk is, en dat de som van alle persoon-tevredenheid per dag/berekening zo hoog mogelijk is.

Ik wil nog wel even vermelden dat de verschillende objecten niet met elkaar gerelateerd zijn. Zie het als mogelijke werkplekken. De enige sortering die erop gemaakt kan worden is populariteit. Ofwel een populariteitssortering die uitgaat van de selectie personen uit de pool, ofwel de populariteitsselectie gebaseerd op de totale personenpool.

[ Voor 55% gewijzigd door Clock op 12-03-2010 11:35 ]

[321X]

Clock schreef op vrijdag 12 maart 2010 @ 11:32:
Het verschil tussen onze benadering is dat jij door de personen loopt en ik door de objecten. Ik ben even heel hard aan het denken hoe het er dan uit komt te zien bij jouw benadering.

Een 100% tevredenheid is niet haalbaar (wellicht in een unieke situatie). Ik wil bereiken dat iedereen zo tevreden mogelijk is, en dat de som van alle persoon-tevredenheid per dag/berekening zo hoog mogelijk is.

Ik wil nog wel even vermelden dat de verschillende objecten niet met elkaar gerelateerd zijn. Zie het als mogelijke werkplekken. De enige sortering die erop gemaakt kan worden is populariteit. Ofwel ook populariteitssortering die uitgaat van de selectie personen uit de pool, ofwel de populariteitsselectie gebaseerd op de totale personenpool.

Hoe dacht je het dan te doen als je door de objecten loopt? Hoe houd je bijvoorbeeld rekening met de voorkeuren?

[Clock]

- Objecten sorteren op populariteit (# van personen die het object in hun voorkeurslijst hebben).
- Loop door alle objecten in toenemende populariteit (objecten met 0 voorkeuren niet meenemen)
-- Bij het eerste object zal weinig keus zijn (vaak maar 1 persoon met voorkeur voor dat object). Bij meerdere beschikbare personen wordt degene gekozen die het object het hoogst op zijn voorkeurslijst heeft staan. Deze persoon wordt gekoppeld aan dit object. Persoon wordt aangemerkt als 'bezet' en wordt niet meer meegenomen bij verdere vergelijkingen.
-- Bij de volgende objecten zal op eenzelfde manier steeds iemand gezocht worden die nog beschikbaar is en het object het hoogst op zijn voorkeurslijst heeft staan.
- Als alle objecten zijn doorlopen worden de overgebleven mensen 'random' toegewezen aan objecten met 0 voorkeuren (minst populair en onmogelijk naar tevredenheid toe te wijzen).

Dit was mijn oorspronkelijke opzetje. Het probleem wat ik nu zie is dat er af en toe opofferingen moeten worden gemaakt. In plaats van dat een persoon zijn eerste voorkeur toegewezen krijgt is het voor het geheel van indelingen soms beter dat hij genoegen neemt met zijn 2e voorkeur (zodat iemand anders ook aan 1 van zijn voorkeursobjecten gekoppeld kan worden). Dit 'berekenen' van opofferingen is hetgeen wat het volgens mij zo lastig maakt. De totale tevredenheid moet zo hoog mogelijk zijn, niet die van de eerste 5 personen heel hoog (allemaal 1e object keus), en de laatste 4 personen bagger omdat alle voorkeuren ingepikt zijn.

Het idee van brute-force met het toekennen van punten aan elke positie (10 voor 1e voorkeur, 6 voor 2e voorkeur en 3 voor 3e voorkeur) komt hier denk ik wel aan tegemoet.

Ik kan helemaal verkeerd zitten, dit is geen standaard kost voor mij. Mocht dat zo zijn geef aub een gil

[Clock]

Ik wil graag het brute-forcen een shot geven. Ben benieuwd hoe lang dat duren gaat. Echter hoe kan ik alle verschillende combinaties langslopen?

Bij een password brute-forcen kan ik me dat nog voorstellen in pseudocode, echter lukt het me hierbij niet zonder 8 geneste loops.

[ Voor 4% gewijzigd door Clock op 12-03-2010 13:46 ]

[_js_]

Clock schreef op vrijdag 12 maart 2010 @ 13:39:
Ik wil graag het brute-forcen een shot geven. Ben benieuwd hoe lang dat duren gaat. Echter hoe kan ik alle verschillende combinaties langslopen?

Bij een password brute-forcen kan ik me dat nog voorstellen in pseudocode, echter lukt het me hierbij niet zonder 8 geneste loops.

Een password-brute-force-algoritme aanpassen is niet heel veel werk, in plaats van de letters A-Z heb je de verschillende personen, en in plaats van een woord heb je de objecten. Het enige wat je moet toevoegen is een controle om te zorgen dat je niet meerdere objecten aan een persoon toekent (als je geen backtracking doet kost het misschien wel meer tijd, er moeten namelijk aantal_personen ^ aantal_objecten dingen worden gedaan, ipv aantal_personen! / (aantal_personen - aantal_objecten)! met backtracking).

[Clock]

_js_ schreef op zaterdag 13 maart 2010 @ 00:54:
[...]

Een password-brute-force-algoritme aanpassen is niet heel veel werk, in plaats van de letters A-Z heb je de verschillende personen, en in plaats van een woord heb je de objecten. Het enige wat je moet toevoegen is een controle om te zorgen dat je niet meerdere objecten aan een persoon toekent (als je geen backtracking doet kost het misschien wel meer tijd, er moeten namelijk aantal_personen ^ aantal_objecten dingen worden gedaan, ipv aantal_personen! / (aantal_personen - aantal_objecten)! met backtracking).

Ik heb het quick and dirty opgelost met wat geneste loops om te kijken hoelang die met een berekening bezig zou zijn. Zonder die controle van meerdere objecten per persoon zijn er +- 48.000.000 mogelijkheden. Die rekent ie met wat ongeoptimaliseerde code door in dik 10 seconden. Volkomen acceptabel voor mijn doel.

Nu wil ik het graag goed implementeren, waarbij er dus rekening moet worden met die beperking van 1 persoon per object en de mogelijkheid van meerdere slots per object. Ik heb me er vannacht suf over gepiekerd, maar ik krijg daar geen mooie code-opzet voor.

Zou iemand die dit wel voor zich ziet mij daarmee een zetje willen geven? Het gaat dus om het brute-forcen van alle mogelijkheden.

[Clock]

Ik heb verschillende manieren geprobeerd via een loop door de objecten en een loop door de personen. Bij beide manieren blijft het probleem zitten in de beperking dat een persoon maar 1 keer gekoppeld kan worden en dan niet meer meegenomen mag worden. (backtracing?)

Dit is bij password-brute-forcen niet aan de orde, dus daar kan ik geen inspiratie uit halen. (een letter kan meerdere keren gebruikt worden). Hulp erg graag gewenst, dan kan ik het zelf wel implementeren en is het klaar. Thnx!

Edit: Om nieuwe lezers van deze thread wat leesvoer en (nu irrelevante) discussies te besparen

Ik zoek een manier op alle mogelijke planningen door te lopen (de code om daar de beste planning uit te halen is al klaar). Het zal dan gaan om enkele miljoenen mogelijke planningen.

Voorwaarden/beperkingen:
- Per object kan het aantal persoon-slots variëren (tussen 0 en 3)
- Een persoon kan per planning maar toegewezen worden aan 1 object. (bij een volgende iteratie/planning weer aan een ander object natuurlijk)

[ Voor 36% gewijzigd door Clock op 14-03-2010 12:49 ]