Visualizza il feed RSS

Titolo provvisorio...

“Cielo... mio marito!”

Valuta questo inserimento
di pubblicato il 21-04-2020 alle 23:10 (202 Visite)
La celeberrima battuta tratta da “Tailleur pour dames” del grande Georges Feydeau, una delle più esilaranti (e copiate) pochade incentrate sul tema delle relazioni extraconiugali, si presta splendidamente ad introdurre il non meno famoso problema combinatorio noto come “Problema dei matrimoni stabili”.

Sfatiamo subito un mito: scorrendo l'ormai vastissima lista delle applicazioni nate attorno a questo problema e sue variazioni, si vede come in realtà l'uso di tali algoritmi in ambito matrimoniale e simili (dating online, etc.) è sporadico, pressoché inesistente. Come spessissimo avviene, il riferimento usato nel nome del problema è volutamente metaforico e serve unicamente a creare uno spiritoso spunto mnemonico e situazionale per quello che è un serissimo problema di assegnazione di risorse in operations research, nato attorno ad una istanza importante (l'assegnazione di studenti ai college universitari e, indipendentemente, dei medici tirocinanti alle cliniche) ed evolutosi poi in una serie di generalizzazioni con un vastissimo campo applicativo: dall'assegnazione di posti istituzionali in enti pubblici e parastatali di ogni genere alla logistica, dalla pianificazione della produzione all'assegnazione di risorse ai centri di costo, alla gestione di affiancamenti nell'ambito sanitario o militare, eccetera.

In cosa consiste esattamente il problema Stable Marriage (SM)? Esistono numerose varianti, ma nella formulazione originale, dovuta a Gale e Shapley nel 1962, si hanno due distinti gruppi (“uomini” e “donne”), di pari dimensione. Ciascun membro di ogni gruppo esprime in una lista completa le proprie preferenze per “l'altro sesso”, ordinandole - per fissare le idee - in modo decrescente, dalla più alla meno desiderabile. In pratica, ad ogni elemento di uno dei due insiemi si associa una particolare permutazione dell'altro insieme. Si procede quindi a formare le “coppie”, seguendo gli elenchi di preferenze: la soluzione ottenuta è detta “matrimonio stabile” se non esistono due individui, uno per insieme, i quali preferiscono reciprocamente l'altro individuo al proprio partner attuale.
L'algoritmo pubblicato nel 1962 (che chiameremo GS) è basato su semplicissimi passaggi detti "proposte", che vengono accettate o rifiutate secondo il semplice confronto posizionale tra il partner attuale e il proponente nella scala delle priorità della parte che riceve la proposta. Se la ricevente preferisce il proprio partner attuale al proponente, scatta il manzoniano "Questo matrimonio non s'ha da fare" e si passa alla successiva preferenza.
L'idea tipica, nelle intenzioni di Gale & Shapley, è che l'insieme M degli "uomini" (es. studenti) si propone e quello delle "donne" W (es. college, cliniche) valuta le proposte, ma ovviamente nulla impedisce di eseguire l'algoritmo seguendo la convenzione opposta.
Il principale merito di Gale & Shapley è quello di avere dimostrato che:

1) Qualunque istanza del problema SM ammette almeno una soluzione stabile;

2) Tale soluzione ha la proprietà di essere proponent-optimal, ossia garantisce a ciascun membro dell'insieme proponente il migliore accoppiamento in assoluto rispetto a qualsiasi altra eventuale soluzione stabile (e non). Questa proprietà è la cosiddetta ottimalità paretiana debole.

Il tutto usando un algoritmo di estrema semplicità che, dati due insiemi non vuoti M e W di cardinalità n e le relativi matrici di preferenze, genera la soluzione male-optimal (o female-optimal) in O(n2) al caso peggiore. L'analisi del caso medio di esecuzione avrebbe diritto ad un intero articolo dedicato, ma ci limitiamo qui a presentarne il risultato che coinvolge la definizione di numero armonico.

Formula LaTeX: H_n=\sum_{k=1}^{n}k^{-1}=\gamma+\psi_0(n+1)

Hn è appunto l'ennesimo numero armonico. Nell'espressione analitica più a destra, gamma è la costante di Euler-Mascheroni e psi è la funzione digamma, ossia la derivata logaritmica della funzione gamma, a sua volta estensione del fattoriale ai numeri reali. Detto questo, il numero medio di proposte nell'algoritmo GS è dato da Formula LaTeX: n\cdot H_n+O((\text{log}n)^4). Ne consegue che la complessità media è dell'ordine di Formula LaTeX: \Theta (n\text{log}n).

La soluzione ottenuta può essere ovviamente espressa in vari modi. Sostanzialmente essa consta di un elenco di n coppie (m,w) con elementi presi rispettivamente dai due insiemi M e W. Si abbiano i seguenti elenchi di preferenze, rispettivamente maschili e femminili, in cui ogni membro dei due insiemi è codificato da un piccolo intero positivo:

Formula LaTeX: \begin{matrix} 1: & 4 & 1 & 2 & 3\\ 2: & 2 & 3 & 1 & 4\\ 3: & 2 & 4 & 3 & 1\\ 4: & 3 & 1 & 4 & 2 \end{matrix}

Formula LaTeX: \begin{matrix} 1: & 4 & 1 & 3 & 2\\ 2: & 1 & 3 & 2 & 4\\ 3: & 1 & 2 & 3 & 4\\ 4: & 4 & 1 & 3 & 2 \end{matrix}

Intuitivamente, la riga 1 della seconda matrice ci dice che la signora #1 preferisce nell'ordine il signor 4, poi come seconda scelta il signor 1, e via di seguito in ordine discendente di preferenza.

La soluzione stabile male-optimal generata da GS è il seguente elenco di coppie che segue la convenzione (m,w): {(1,4),(2,3),(3,2),(4,1)}. Tale elenco può ovviamente essere espresso come una permutazione in notazione standard a due linee:

Formula LaTeX: \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix}

Leggendo la notazione da sinistra a destra e dall'alto in basso, ne risultano appunto le coppie (1,4),(2,3),(3,2),(4,1). In questa notazione, la permutazione identità della prima riga rappresenta l'insieme proponente nell'ordine naturale. Ne consegue che si può usare anche la notazione posizionale 1-line, come per qualsiasi altra permutazione, senza perdita di informazione: la notazione 4 3 2 1 rappresenta esattamente le medesime coppie, dove agli uomini è implicitamente assegnata la posizione 1..n crescente verso destra e le relative partner vengono specificate esplicitamente.

Tuttavia, la natura combinatoria elementare della soluzione non ci è di grande aiuto computazionalmente. Trovare tra le possibili permutazioni dell'insieme W (o M, se del caso) la soluzione ottimale per esaustione applicando il paradigma del “generate and test” è una via del tutto impraticabile anche per problemi di dimensioni assai modeste. Tale soluzione può anche essere vista nella sua natura di relazione binaria, ossia un sottoinsieme del prodotto cartesiano tra i due insiemi dati, il quale prodotto in soldoni non è altro che l'elenco di tutte le possibili n2 coppie ordinate formate prendendo un solo elemento per volta da ciascun insieme di partenza. Niente di trascendentale, in ultima analisi: ma come spesso avviene, gli algoritmi necessari ad ottenere una enumerazione esaustiva di tali soluzioni, come pure quelli dedicati a trovare particolari tipologie di soluzione, erano ben lungi dal vedere la luce ai tempi di Gale & Shapley, sono quasi tutti caratterizzati da complessità computazionale molto elevata e/o richiedono un approccio del tutto peculiare, con l'ausilio di strutture dati non banali.

A partire dalla metà degli anni Ottanta alcune pubblicazioni (principalmente dovute a Gusfield, Irving e Leather) avevano risvegliato l'interesse generale verso il problema, stimolando numerosi articoli divulgativi sulle principali riviste internazionali di programmazione applicativa e - come immediata conseguenza - anche diverse implementazioni di studio in vari linguaggi di alto livello (tra i quali Ada, C, Clipper, COMAL) da parte del sottoscritto. In questa puntata ci concentreremo quindi su una di tali implementazioni in COMAL 80 V. 2.01 per Commodore 64, restando nell'ambito del retrocomputing che sta riscuotendo sempre maggiori attenzioni e consensi tra i miei lettori.

Purtroppo invece non sarà possibile trattare un altro aspetto "retro" che varrebbe la pena di approfondire: il sorgente in ALGOL60 elaborato da McVitie e Wilson nel 1970 per la generazione esaustiva di tutte le soluzioni per la versione del problema generalizzata al caso di liste di dimensioni disuguali, che come caso particolare risolve l'istanza standard. Tale algoritmo, pur avendo prestazioni decisamente non entusiasmanti, ha una sua notevole importanza storica in quanto costituisce il primo tentativo di fornire una generazione esaustiva delle soluzioni, poi surclassato solo nel 1989 dalla pubblicazione della monografia di Gusfield e Irving i quali - grazie ad un attento studio della natura algebrica dello spazio delle soluzioni, e suggerendo un uso accorto di strutture dati in grado di garantire contemporaneamente sia l'accesso diretto indicizzato, sia cancellazioni in O(1) - hanno proposto l'algoritmo ancora attualmente in uso per la generazione esaustiva anche su istanze di grandi dimensioni, con prestazioni in O(n2), praticamente il medesimo ordine di grandezza del GS (che in quel tempo è in grado però di generare una singola soluzione, non tutte). Avremo modo di approfondire a dovere in che modo si ottengono incrementi prestazionali del genere, al momento opportuno.

Altro aspetto rilevante e divertente dell'algoritmo di McVitie e Wilson è la sua originale implementazione su un KDF-9 a transistor della English Electric Computers (poi English Electric LEO Marconi Computers), installato presso l'Università di Newcastle: questo è davvero retrocomputing, e del migliore! Di tale storico elaboratore esiste un emulatore scritto in Ada e dotato di una ricchissima documentazione, col quale il sottoscritto si è a lungo divertito.

La prima volta che mi sono occupato sistematicamente del problema in un contesto accademico, a fine anni Ottanta, esistevano decine di pubblicazioni al riguardo, SM era menzionato in almeno mezza dozzina di testi di algoritmica a partire dagli anni Settanta e vi erano ben tre monografie dedicate, sebbene una delle quali fondamentalmente incentrata solo sugli aspetti game-theoretic e l'altra, dovuta al venerabile D.E. Knuth, edita solo in francese fino al 1997. Sei lustri dopo il numero di pubblicazioni e di testi di algoritmica che fanno menzione del problema è pressoché raddoppiato, tuttavia si deve rilevare che molte delle questioni poste nelle principali monografie storiche, alle quali se ne è aggiunta una quarta pochi anni fa, non hanno ancora trovato soluzione e il problema rimane ricco di spunti di ricerca e applicativi. Ma avremo modo di parlare di questo in seguito.

A questo punto non posso che lasciare i lettori all'articolo completo in PDF.