Visualizza il feed RSS

Titolo provvisorio...

"Cielo... mio marito!", la seconda puntata

Valuta questo inserimento
di pubblicato il 06-05-2020 alle 18:16 (183 Visite)
Dopo la breve digressione introduttiva sul problema dei matrimoni stabili proposto nel 1962 da David Gale e Lloyd Shapley, doverosamente incentrata nel più genuino ambito retroinformatico, dedichiamo un altro articolo alla parte più moderna della sua lunga storia. Questo problema e i suoi numerosi derivati sono stati affrontati nei decenni attingendo a piene mani a tutto l'arsenale di tecniche tipiche dell'ottimizzazione combinatoria: programmazione lineare, constraint programming, algoritmi paralleli, metodi decentralizzati, perfino algoritmi genetici e ant-colony. Tuttavia, le più radicali ottimizzazioni sono arrivate solo tra fine anni Ottanta (grazie ad un cambio di paradigma che ha gettato una luce diversa sulla reale natura algebrica dello spazio delle soluzioni) e la prima metà degli anni Novanta, con una reinterpretazione «circuitale» del problema nell'ambito delle reti logiche: tutti algoritmi che sono poi giunti sostanzialmente invariati fino ai giorni nostri.

La maggior parte dei testi di algoritmica che fanno menzione del problema dei matrimoni stabili (SM) si fermano, senza apparente motivo, all'algoritmo man-optimal di Gale & Shapley, il quale tuttavia non è che il capostipite della famiglia di algoritmi risolutivi. Tra questi testi alcuni sono meritatamente famosissimi, come il Sedgewick, il Wirth o il Lawler, ma ce ne sono almeno altre due dozzine, tanto che una elencazione esaustiva sarebbe del tutto inappropriata in questo contesto.

Pagato il doveroso tributo ai padri fondatori di questo settore di ricerca con un precedente articolo a pieno titolo intriso di tematiche di retroprogramming tra computer a transistor KDF-9, memorie a nuclei magnetici, ALGOL e COMAL, vogliamo ora andare oltre e dedicare il giusto spazio alla vera e propria pietra angolare nella storia del problema: l'algoritmo di generazione esaustiva delle soluzioni di Dan M. Gusfield (University of California, Davis) e Robert W. Irving (University of Glasgow, Scotland), i cui principi di funzionamento saranno esaminati nel modo più didattico possibile, al fine di raggiungere la più vasta platea di lettori, con particolare riguardo agli studenti più giovani.

Come a più riprese accennato, nei decenni il problema è stato affrontato da numerosi punti di vista, non solo da quello algoritmico: in particolare, economisti e teorici dei giochi (categoria alla quale appartengono anche Gale e Shapley, peraltro) hanno approfondito ad esempio l'uso di metodi come inganno, manipolazione, corruzione, coalizioni segrete per coartare a vantaggio di singoli o piccoli gruppi l'output dell'algoritmo classico. Dal punto di vista computazionale, è stato collaudato l'uso di tecniche asseverate come programmazione lineare, constraint programming, algoritmi paralleli, metodi decentralizzati, perfino algoritmi genetici e ant-colony per risolvere casi particolari del problema (es. SMI, Hospital/Residents) e sue immediate derivazioni: su tutte il problema detto Stable Roommates (SR). Tuttavia, ad oggi l'approccio maggiormente efficiente per la generazione esaustiva rimane quello del quale qui discutiamo.

Si esorta il lettore a fissare subito bene in mente i tre capisaldi fondamentali che hanno motivato la stesura del presente articolo:

1. Le istanze del problema Stable Marriage a cui pensiamo sono dell'ordine di grandezza di 103-105 proponenti (cliniche, college, posti pubblici in generale a livello di nazioni o grandi regioni): per questo motivo le prestazioni dell'algoritmo in spazio e in tempo sono fondamentali, ed è essenziale comprendere almeno a grandi linee la struttura algebrica dello spazio delle soluzioni e le idee alla base dell'algoritmo;

2. Enumerare tutte le soluzioni stabili per istanze di tali dimensioni ha ampiamente senso non solo a scopo di ricerca e studio, ma anche e soprattutto nella pratica, per garantire in casi specifici la possibilità di individuare rapidamente una soluzione intermedia con determinate caratteristiche (ad esempio le cosiddette soluzioni «minimum regret» nelle quali si cerca un compromesso tra le preferenze di ambedue i gruppi, approccio diverso rispetto all'ottimalità paretiana debole): riuscire a farlo in tempi accettabili diventa quindi fondamentale e, di nuovo, è importante comprendere il funzionamento dell'algoritmo almeno nei suoi passaggi principali.

3. La monografia in oggetto è totalmente incentrata sugli aspetti algoritmici e sulla struttura algebrica dello spazio delle soluzioni: gli autori non forniscono neppure un minimale esempio di codice in un qualsivoglia linguaggio, né nel testo né in un sito web di riferimento. A quanto pare, in generale, non è reperibile sul web alcuna implementazione di riferimento o di studio dell'algoritmo di Gusfield e Irving, mentre ve ne sono in abbondanza per l'algoritmo di Gale-Shapley come per molti altri famosi esempi proposti privi di codice in manuali e monografie famose. Per contro, l'esperienza didattica conferma che un semplice esempio di codice aumenta notevolmente la comprensione della dinamica dell'intero algoritmo, dato anche il modo piuttosto dispersivo in cui viene presentato nel testo di Gusfield e Irving.

Invitiamo i lettori a proseguire con la lettura dell'articolo completo.

aggiornamento da 18-05-2020 a 21:26 di M.A.W. 1968

Categorie
Libri , Programmazione , Scienza