Come scambiarsi regali di Natale in maniera ottimale con un Secret Santa e l’aiuto della Ricerca Operativa. A cura di Veronica Dal Sasso, Operations Research Scientist di Optrail s.r.l..

Da qualche anno partecipo a un Secret Santa. Si tratta di uno scambio di regali di Natale in cui a ognuno è assegnata una persona a cui fare un regalo. Il “Secret” sta nel fatto che, fino al momento dello scambio dei doni, una persona non sa da chi riceverà il proprio regalo.

Un Secret Santa inglese

Il Secret Santa a cui partecipavo è un po’ particolare: non è necessario che tutti i partecipanti si conoscano di persona né che si trovino nella stessa città (o perfino continente), visto che non c’è un’occasione per uno scambio fisico, ma i regali vengono spediti. Inoltre, il regalo deve essere fatto a mano, sfruttando uno o più dei propri hobbies creativi. Per far sì che, comunque, il manufatto non sia troppo lontano dai gusti del ricevente, ogni partecipante compila un questionario in cui elencare preferenze e abitudini.

Già a settembre comincia ad esserci fermento: si raccolgono adesioni, si preparano questionari, cosicché, con congruo anticipo, a ognuno venga assegnato un ricevente. Ma questo Secret Santa viene organizzato in Inghilterra e spedire pacchetti ora è più complicato: c’è il rischio di incorrere in costi di dogana che spesso superano il valore dell’oggetto spedito. Nel clima di difficoltà attuale, quest’anno non mi andava di rischiare di appesantire qualche situazione economicamente già difficile facendo pagare inattese spese di dogana.

Per quest’anno, quindi, niente Secret Santa. È un peccato, vero? Infatti. Dopo circa un paio d’ore dalla decisione di non partecipare alla versione inglese, avevo già deciso di organizzarne una italiana.

Il mio Secret Santa

Il format è uguale: ognuno compila un questionario per dare un’idea dei propri gusti e hobbies alla persona che deve confezionare il regalo, dopodiché gli viene assegnata un’altra persona. Ma come viene assegnata questa persona?

La risposta più semplice ed imparziale è: scegliendo a caso! Per esempio, consideriamo me (Veronica), mio fratello Giacomo, la coppia di amici Alice e Bob, e altri due amici, Chiara e Domenico. Partendo dalla prima persona, costruisco un ciclo estraendo in modo random la persona seguente. Così facendo, ottengo la sequenza Veronica → Alice → Bob → Chiara → Giacomo → Domenico e, chiudendo il ciclo, avremo Domenico → Veronica.

Ho stabilito così chi prepara il regalo a chi, ma il mio ciclo random non mi soddisfa per niente. Nel mio gruppo di partecipanti ci sono sorelle, fratelli, conviventi: di sicuro a Natale già si faranno dei regali, quindi sarebbe molto più bello se in quest’occasione venissero loro assegnate persone al di fuori della cerchia famigliare. Inoltre, non voglio assolutamente ricevere il regalo da Domenico, né che Alice debba farlo a Bob, o che Giacomo lo faccia a Domenico. E so che sia Giacomo sia Chiara amano cucinare, e che Chiara e Domenico vanno in palestra insieme.

In generale

Ci sono sottogruppi di amici che già si conoscono, e persone che tra loro non si conoscono affatto ma che hanno hobbies e passioni comuni: perché non cogliere l’occasione per ampliare le conoscenze, invece di ritrovarsi a preparare un regalo per l’amico con cui si passa già molto tempo?

Voglio quindi creare un ciclo che includa ogni partecipante e che cerchi di soddisfare al meglio alcuni requisiti:

• scartare a priori gli assegnamenti che non si vogliono fare;
• evitare, se possibile, di accoppiare parenti o conviventi;
• cercare di assegnare le persone in base a hobbies comuni.

Questo vuol dire che devo dare, a ogni possibile coppia di partecipanti, una “misura” di quanto vorrei sia auspicabile assegnare una persona all’altra. Possiamo formularla come una probabilità, o come una “distanza” tra le persone.

Aspetta un attimo, tutto questo mi suona molto familiare… Ma è un Travelling Salesman Problem (TSP), ovvero, il problema del commesso viaggiatore!

Il problema del commesso viaggiatore in chiave natalizia

Il TSP è già noto su questa piattaforma e si può adattare facilmente al problema in questione. Rivediamo insieme la definizione formale del problema.

Sia N un insieme di persone. Per ogni coppia distinta (n, m) di persone, sia d(n,m) = d(m,n) la distanza tra esse. Dato il grafo completo G = (V, A), in cui i nodi di V rappresentano le persone e il peso degli archi in A è dato dalla distanza d(.), si vuole trovare un ciclo che passi esattamente per tutti i nodi del grafo e che abbia peso minimo.

Essendo il TSP un problema classico della ricerca operativa, nonché notoriamente molto difficile, ci sono già svariati modelli utilizzati per la sua risoluzione.

La maggiore difficoltà del TSP sta nel fatto che bisogna porre particolare attenzione a non creare dei sottocicli: non sarebbe bello che Alice e Giacomo si scambiassero i regali a vicenda, e che Bob, Chiara, Domenico e Veronica se li scambiassero tra di loro.

Tenuto conto di questo aspetto, però, non mi interessa veramente utilizzare il modello più efficiente, o quello che meglio scala all’aumentare della dimensione del problema (questo forse mi servirà i prossimi anni, quando sempre più persone vorranno partecipare al mio Secret Santa?). Per il mio scopo scelgo quindi un modello piuttosto semplice da implementare, come quello formulato da Miller–Tucker–Zemlin, dove si evita la formazione di sottocicli dando a ogni nodo un numero progressivo di una sequenza che va da 1 a N.

Mi manca ora da definire le distanze tra i partecipanti. Anche qui, per il momento non complichiamo troppo le cose: prendo due costanti p ed a (con p nettamente maggiore di a) che rappresentano, rispettivamente, la distanza che voglio mettere tra parenti e amici. Considero le funzioni indicatrici P(n,m) e A(n,m). P(n,m)=p se gli individui n e m sono parenti, mentre P(n,m)=0 se non lo sono. Allo stesso modo, A(n,m) assume valore pari ad a solo se n e m sono amici. Sia C(n,m) il numero di hobbies comuni tra n ed m, ed h una costante (molto più piccola di a). Allora la distanza tra due persone sarà data da d(m,n) = P(m,n) + A(m,n) -h*C(m,n).

Nel nostro esempio

Vediamo cosa succede nel nostro esempio: decido il valore delle costanti (p = 99, a = 30, h = 5) e ottengo il grafo pesato nella figura sottostante, dove ho rimosso già i collegamenti che voglio assolutamente evitare.

Ora posso implementare velocemente il modello matematico del TSP in un solver passandogli questa istanza particolare, per ottenere finalmente un ciclo soddisfacente!

Il ciclo ottenuto è Veronica → Alice → Giacomo → Chiara → Domenico → Bob → Veronica. Non ho selezionato nessun arco rosso che nel suo peso comprende la costante p, Giacomo e Chiara sono collegati, e così pure Chiara e Domenico!

Questo Secret Santa, grazie alla Ricerca Operativa, ha sicuramente una marcia in più! Prevedo già ulteriori miglioramenti negli anni futuri, quando, per esempio, vorrò evitare che una persona si ritrovi a rifare il regalo alla stessa persona dell’anno precedente. Basterà togliere dal grafo l’arco corrispondente, e il gioco sarà fatto.

Infine, sotto l’albero…

Visto che lo spirito del Natale aleggia su più di una persona, c’è chi ha affrontato lo stesso problema e l’ha risolto diversamente, per esempio con un approccio più algoritmico.

Il TSP potrebbe anche essere doppiamente risolutivo in questo problema: se la persona che vi è stata assegnata è appassionata di Ricerca Operativa, potreste farle un bel segnalibro e regalarle anche il libro di William J. Cook sull’argomento! Date un’occhiata alla recensione qui.

Non solo il Natale è dappertutto… Anche la ricerca operativa non scherza (e non è solo nei treni)!

Auguri di Buone Feste!

Alice Raffaele