Det sociala golfproblemet (SGP) är ett kombinatoriskt designproblem inom diskret matematik som härrör från en fråga som publicerades i usenet-nyhetsgruppen sci.op-research i maj 1998. Problemet är följande: 32 golfare spelar golf en gång i veckan i grupper om fyra. Schemalägg dessa golfare att spela i så många veckor som möjligt utan att två golfare spelar tillsammans i en grupp mer än en gång.

Mer generellt kan detta problem definieras för vilken som helst golfare som spelar i grupper av golfare för veckor. Lösningen innebär att antingen verifiera eller motbevisa existensen av ett schema och, om ett sådant schema existerar, bestämma antalet unika scheman och konstruera dem.

Utmaningar

SGP är ett utmanande problem att lösa av två huvudskäl:

För det första är det det stora sökutrymmet som är ett resultat av problemets kombinatoriska och mycket symmetriska natur. Det finns totalt scheman i sökfältet. För varje schema kan veckorna , grupper inom varje vecka , spelare inom varje grupp och individuell spelare , alla permuteras. Detta leder till totalt isomorfismer – scheman som är identiska genom någon av dessa symmetrioperationer. På grund av sin höga symmetri används SGP ofta som ett standardriktmärke för symmetribrytning i villkorsprogrammering ( symmetribrytande begränsningar ).

Det andra är valet av variabler. SGP kan ses som ett optimeringsproblem för att maximera antalet veckor i schemat. Därför kan felaktigt definierade initialpunkter och andra variabler i modellen leda processen till ett område i sökrummet utan lösning.

Lösningar SGP är inom Steinersystemet S(2,4,32) eftersom 32 golfare är indelade i grupper om 4 och både grupp- och veckotilldelningen för 2 golfare kan identifieras unikt. Strax efter att problemet föreslogs 1998 hittades en lösning på 9 veckor och existensen av en lösning på 11 veckor visade sig vara omöjlig. I fallet med det senare, observera att varje spelare måste spela med 3 unika spelare varje vecka. För ett schema som varar i 11 veckor kommer en spelare att grupperas med totalt andra spelare. Eftersom det bara finns 31 andra spelare i gruppen är detta inte möjligt. Det är nu känt att en lösning för 10 veckor kunde erhållas från resultat som redan publicerades 1996 av Hao Shen, men den konstruerades aldrig explicit. Den första explicita lösningen konstruerades oberoende av Alejandro Aguado år 2004 med en annan metod. Detta är lösningen som presenteras nedan. +10-veckorslösning till det sociala golfarproblemet (Aguado - 2004)Grupp 1Grupp 2Grupp 3Grupp 4Grupp 5Grupp 6Grupp 7Grupp 8Vecka 010,1,2,34,5,22,236,7,20,218,25,26,279,10,11,2412,13,15,3014,28,29,3116,17,18,19Vecka 020,4,8,281,6,18,232,7,17,223,5,26,319,13,14,2710,15,19,2111,25,29,3012,16,20,24Vecka 030,11,14,211,7,10,282,15,20,253,13,22,244,9,18,315,16,27,306,8,19,2912,17,23,26Vecka 040,18,24,271,9,19,262,8,11,163,10,17,254,7,12,295,6,14,1513,20,23,2821,22,30,31Vecka 050,6,13,261,4,11,152,9,21,283,8,14,235,12,18,257,19,24,3010,16,22,2917,20,27,31Vecka 060,7,25,311,5,24,292,12,14,193,18,28,304,6,10,278,13,17,219,15,16,2311,20,22,26Vecka 070,5,19,201,14,22,252,23,27,293,4,16,216,9,17,307,11,13,188,10,12,3115,24,26,28Vecka 080,15,17,291,13,16,312,4,26,303,6,11,125,7,8,910,14,18,2019,22,27,2821,23,24,25Vecka 090,9,12,221,8,20,302,5,10,133,7,15,274,14,17,246,16,25,2811,19,23,3118,21,26,29Vecka 100,10,23,301,12,21,272,6,24,313,9,20,294,13,19,255,11,17,287,14,16,268,15,18,22 Det finns många metoder för att lösa SGP, nämligen designteoritekniker, SAT-formuleringar ( propositionellt satisfierbarhetsproblem ), begränsningsbaserade metoder, metaheuristiska metoder och talbasmetoden.

Talbasmetoden delar in golfare i grupper baserat på addition av tal i basen Variabler i det allmänna fallet med SGP kan omdefinieras som golfare som spelar i grupper av golfare för valfritt antal . Det maximala antalet veckor som dessa golfare kan spela utan att omgruppera två golfare är .

Tillämpningar Att arbeta i grupp uppmuntras i klassrummen eftersom det främjar aktivt lärande och utveckling av kritiskt tänkande och kommunikationsförmåga. SGP har använts för att dela in studenter i grupper i kemikurser på grundnivå och i grupper i online-mötesprogram för att maximera studentinteraktion och socialisering.

SGP har också använts som modell för att studera turneringsplanering.

Se även Round-robin-turnering

Referenser

Wolfram Community: Radix-metoden för att lösa problemet med sociala golfare och grafvisualisering Wolfram Mathworld: Problem med social golfare

Kategori:Matematiska problem Kategori:Sidor med ogranskade översättningar