Jag håller på med ett hobbyprojekt och har kört fast... Hm... ganska abstrakt beskrivning... Det blir nog mycket enklare att greppa om du talar om vad det handlar om egentligen. OK, jag hade tänkt slippa undan med att vara lite abstrakt, men... - Vid varje tidpunkt ska de deltagare vars station inte är aktuell fördelas på de andra stationerna så att det, så långt det är möjligt, är lika många deltagare vid varje station. <b>>Tyvärr är problemet NP-komplett så det kan bli svårt att lösa ditt problem för 80 deltagare.</b> Ja, det är helt rätt. Jag hittade (http://www.cs.huji.ac.il/~fery/presentation.ppt) en appromixation till min. k-clustering. Den går ut på att använda en algoritm för att skapa ett minimalt uppspännande träd (t ex Kruskal's eller Prim's) och sedan dela upp det trädet i subträd med en viss diameter, vilket skapar själva klustren. Med en avståndsfunktion som visar om två personer har träffats så borde det kunna ge en hyffsad lösning för många personer. Tack för era svar! Jag har framförallt fått det bekräftat att jag inte missade någon enkel och självklar lösning i mitt grubblande. Eftersom det är ett hobbyprojekt kan jag inte sätta tänderna i det genast, men nu vet jag var jag ska börja iallafall. Om ett problem är för stort, delar man upp det i mindre...Fiffig algoritm, en utmaning ;-)
Så här är förutsättningarna, kort beskrivna:
Det jag ska lösa består av Deltagare, Stationer och Tillfällen.
- Deltagarna är grupperade två och två och är funktionärer för en speciell station.
- Tidpunkterna är tre
- Stationerna ska vara jämt fördelade mellan tidpunkterna, dvs om det finns 30 stationer ska det vara 10 stationer per tidpunkt.
- Vid varje tidpunkt ska de deltagare vars station inte är aktuell fördelas på de andra stationerna så att det, så långt det är möjligt, är lika många deltagare vid varje station.
- Två deltagare ska helst inte träffa på varandra vid mer än ett tillfälle
- Det förekommer "lösa" deltagare som inte är funktionärer för någon station
Min tekniska lösning är väl iochförsig ointressant men... En Accessdatabas och VB6
Har försökt men hamnar i evighetsloopar hela tiden och har egentligen annat jag borde göra... Sv: Fiffig algoritm, en utmaning ;-)
Sv:Fiffig algoritm, en utmaning ;-)
Programmet ska användas för att administrera vår årliga fest i bostadsområdet. Det hela går ut på att man äter förrätt på ett ställe, varmrätt på ett annat ställe och efterrätt på ett tredje ställe. Mycket trevlig umgängesform, bör provas ;-))
En tredjedel av deltagarna bjuder alltså på var och en av rätterna. Om man t.ex. har fått på sin lott att vara värd för varmrätt så är man själv och ens eventuella partner hemma i sitt hus under just varmrätten och får ett antal hemliga gäster. De som står för det totala festorganiserandet bjuder inte på mat hemma hos sig utan är gäster hela kvällen.
Trevligast är om man träffar så många olika människor som möjligt under kvällen, därför är det önskvärt att man träffar varje annan deltagare vid endast en rätt. Partnern träffar man hemma hos sig när man är värd.
Det är också önskvärt att vara ungefär lika många damer som herrar runt bordet.
Databasdesign:
+----------+ +-----------+ +-------------+
| Hus | |Besök | |Deltagare |
| ----------+ +-----------+ +-------------+
| HusID |\ |PersonID |-------|PersonID |
| Adress | \-- |HusID | | HusID |
| Maträtt | +------------+ |Namn |
+-----------+ | Man/Kvinna|
+-------------+
Tabellen "Besök" innehåller exakt tre poster per deltagare (förrätt, varmrätt och efterrätt).
Fältet HusID i Deltagartabellen anger vilket hus deltagaren bor i och alltså bör befinna sig i när dess maträtt är aktuell.
Vad jag har klart är:
Jag har fördelat maträtterna mellan husen och skapat poster i tabellen besök för deltagarna när de ska vara hemma och bjuda på mat.
Vad jag misslyckas med är:
Att skapa övriga poster i besökstabellen så att samma personer helst inte träffas mer än en gång och så att fördelningen herrar/damer blir schysst.Sv: Fiffig algoritm, en utmaning ;-)
- Två deltagare ska helst inte träffa på varandra vid mer än ett tillfälle
De ovanstående kraven i ditt problem kan lösas m h a en algoritm för MINIMUM K-CLUSTERING problemet.
Problemet finns beskrivet på http://www.nada.kth.se/~viggo/wwwcompendium/node129.html och genom att byta ut avståndsfunktion till en funktion som returner t ex 1 om personer har träffats och 0 annars kan du skapa grupper där så många som möjligt av deltagarna inte har träffat varandra. Tyvärr är problemet NP-komplett så det kan bli svårt att lösa ditt problem för 80 deltagare. Antagligen får du använda dig av någon branch-and-bound-metod för att utesluta lösningar som man tidigt ser inte kommer att bli optimala.
/AndréSv:Fiffig algoritm, en utmaning ;-)
Fast problemet är ju inte definierat så utan att kraven "helst" ska vara uppfyllda. Alltså borde någon hyfsad glupsk algoritm kunna göra det. Sen gäller det ju att komma på den...Sv: Fiffig algoritm, en utmaning ;-)
Sv:Fiffig algoritm, en utmaning ;-)
Sv: Fiffig algoritm, en utmaning ;-)
Det mista antal personer som man kan fördela på par/3 hus/3 måltider är 18
4 sådana 18-grupper ger 72 pers, lägg till 8 jokrar = 80
Varje 18-grupp innehåller 9 hus, dessutom blir det 3 jokerhus
Varje person kan max träffa 17 andra utom några som får träffa 18 andra (ett par mer än antalet hus)
Fördela inom varje grupp för sig i nummerordning (för varje måltid är två personer givna för varje hus, börja med dom, ta sedan dom andra i nummerordning så långt det funkar). Om någon inte passar in pga att man redan mött en person eller att det blir fel könkombination, byter man med någon i jokergruppen.
Sedan placeras jokergruppens personer i jokerhusen. Funkar det dåligt byter man med readan inplacerade.
Det här är kanske lättare att göra med papper och penna än att skriva ett program, men varför inte tänka sig ett program som simulerar vad man skulle gjort med papper och penna?