Algoritmi per la nostra vita by Brian Christian & Tom Griffiths

autore:Brian Christian & Tom Griffiths [Christian, Brian & Griffiths, Tom]
La lingua: ita
Format: epub
editore: Apogeo
pubblicato: 2023-08-29T22:00:00+00:00

Pagare dazio: il Rilassamento lagrangiano

Vizzini: Inconcepibile!

Inigo Montoya: Continui a usare quella parola, ma non credo significhi quello che tu pensi significhi.

– La storia fantastica29

Quando Brian era ancora un bambino, un giorno si lamentava con la madre dei suoi doveri: i compiti, le faccende in casa... “Tecnicamente, non c’è niente che devi fare”, rispose lei. “Non devi fare quello che i tuoi maestri ti chiedono, né devi fare quello che ti chiedo io. Non devi neanche obbedire alla legge. Tutto ha conseguenze, e tu devi decidere se vuoi affrontare queste conseguenze”.

Per la mente del Brian bambino fu una tempesta: era un messaggio potente, risvegliava in senso del proprio agire, la responsabilità, il giudizio morale. E c’era anche altro: una potente tecnica computazionale chiamata Rilassamento lagrangiano.30 L’idea che soggiace al Rilassamento lagrangiano è semplice: un problema di ottimizzazione è composto di regole e di un sistema di valutazione del risultato; nel Rilassamento lagrangiano, prendiamo alcuni vincoli del problema e li spostiamo nel sistema di punteggio. In pratica, prendiamo l’impossibile e lo declassiamo a mera opzione costosa. (Nell’ottimizzazione dei posti al matrimonio, per esempio, potremmo rilassare il vincolo secondo cui ciascun tavolo deve contenere al massimo 10 persone, permettendo la composizione di tavolate più grandi, ma con una specie di penalità data dal fatto di ritrovarsi troppo stretti.) Quando i limiti di un problema di ottimizzazione dicono “Fai così, altrimenti vedrai!”, il Rilassamento lagrangiano risponde: “Vedrai... cosa?”. Una volta fuori dai limiti, anche solo per un po’, anche pagando qualche prezzo, diventano trattabili problemi che prima non lo erano.

Il Rilassamento lagrangiano ha un ruolo importante nella letteratura teorica sul problema del commesso viaggiatore e su altri difficili problemi informatici. Si tratta anche di uno strumento fondamentale per una serie di applicazioni pratiche. Per esempio, torniamo a Michael Trick della Carnagie Mellon, che, come raccontato nel Capitolo 3, deve organizzare il calendario della Major League Baseball e di alcuni campionati della NCAA. Quello che non abbiamo detto è come lo fa. Ogni anno la composizione del calendario è un enorme problema di ottimizzazione discreta, molto più complesso di quello che un qualsiasi computer potrebbe risolvere con la bruta forza del calcolo. Trick e i suoi colleghi dello Sports Scheduling Group sfruttano il Rilassamento lagrangiano per riuscire dell’impresa. Quando accendi la televisione o ti siedi in un palazzetto, sappi che la partita che ha luogo quella sera... insomma, non è necessariamente l’abbinamento ottimale; tuttavia ci va vicino, e per questo dobbiamo ringraziare non solo Michael Trick, ma anche il matematico francese del XVII secolo Joseph-Louis Lagrange.

Nel programmare una stagione sportiva, Trick rivela che il Rilassamento continuo descritto in precedenza non gli rende il compito più facili. “Se il tuo risultato richiede di giocare frazioni di partite, semplicemente non serve a niente”. Una cosa è un’allocazione a frazioni degli inviti a una festa o di luoghi dove sistemare i camion dei pompieri, quando i numeri possono essere arrotondati, ma nello sport i vincoli di integrità (su quante squadre possono giocare una partita, su quante partite vengono giocate in totale e su quante volte ogni squadra gioca contro ogni altra) sono troppo forti.

scaricare

Disconoscimento:
Questo sito non memorizza alcun file sul suo server. Abbiamo solo indice e link                                                  contenuto fornito da altri siti. Contatta i fornitori di contenuti per rimuovere eventuali contenuti di copyright e inviaci un'email. Cancelleremo immediatamente i collegamenti o il contenuto pertinenti.