[Alg] Geautomatiseerde stoel-/tafelindeling.

[Uhmmie]

Het probleem
Ik heb mijn zwager beloofd dat ik eens zou kijken of ik het voor elkaar kan krijgen om een applicatie te schrijven om stoelen/tafels automatisch in te delen.
In eerste instantie lijkt het probleem niet zo groot, totdat je rekening wilt houden dat bepaalde tafels gecombineerd kunnen worden.

Mijn eerste opzet was iets als een structure met daarin alle tafels, zoals:
tafel 1, 4 stoelen
tafel 2, 2 stoelen
tafel 3, 6 stoelen
tafel 4, 4 stoelen
etc
etc

Vervolgens een structure met alle mogelijke combinaties, zoals:
tafel 1, tafel 2
tafel 2, tafel 3
etc
etc

Dit betekend dat ook automatisch dat tafel 1,2 en 3 in het bovenstaande voorbeeld ook tot een grote tafel van 10 stoelen gecombineerd zou kunnen worden.

Het probleem is nu dat stel dat ik eerste 2 stoelen nodig heb, dat het logisch zou zijn dat ik dat aan tafel 2 zou plannen. Echter komt daarna reservering voor 8 man dan zou dat niet meer kunnen. Maar als ik die eerste reservering dan aan tafel 1 zou herplannen, dan had ik wel tafel 2 en 3 vrij gehad voor die 8 man.

Dit brengt een hoop wiskunde met zich mee en alles moet natuurlijk realtime berekend worden, dus eindeloos lopen tot ik een mogelijkheid gevonden heb (of de uit eindelijke conclusie is dat het niet mogelijk is) is geen optie. Nu vraag ik hier niet direct na een oplossing, maar voor mijn gevoel zal er vast wel ergens online een website oid zijn waarin er op dit soort problematiek in gegaan wordt, echter kan ik dit na wat google'n niet vinden.

Iemand enige advies waar ik meer over dit onderwerp kan vinden? Of iemand die toevallig een bepaald soort techniek kent waarmee dit soort problemen opgelost kunnen worden? (dan heb ik iig een richtpunt, waarmee ik misschien weer verder kan ).

Alvast bedankt.

[Zoijar]

Zo op het eerste gezicht heeft het erg veel weg van het "knapsack" probleem ( Wikipedia: Knapsack problem ) Dat is niet zo eenvoudig optimaal op te lossen, maar er zijn wel goede benaderingen te verkrijgen. Misschien is je probleem makkelijker en kan je het met linear programmeren formuleren; dat weet ik niet.

(Ik vraag me af of je het zou kunnen formuleren als een soortgelijk probleem dat ik laatst hier heb besproken: [Alg] Assignment probleem met categorieen )

[ Voor 19% gewijzigd door Zoijar op 16-04-2009 18:38 ]

[djluc]

Vanuit de praktijk in de horeca begin je gewoon met het probleem: De grote groepen. Vervolgens bouw je de rest er omheen.

[Recursio]

Een programmeertaal als ProLog kan hier uitkomst bieden.