Blog divulgativo sulla matematica applicata

Peppa Pig e voli low cost: il problema dello zaino, l'algoritmo ingordo e spunti didattici

Qualche tempo fa con mio figlio stavo vedendo una puntata di Peppa Pig (se per caso la odiate  sappiate che avete tutta la mia solidarietà).

In particolare guardavamo  su youtube la puntata in cui la simpatica famigliola si prepara per partire per una vacanza  e, proprio all'inizio della puntata, a papà Pig si pone il problema del chiudere l'enorme valigia stipata di ogni cosa inutile preparata da mamma Pig.

problema_valigia

È nel vedere questa scena che  mi è venuta l'idea per questo post.

Voi mi direte: "Che c'entra il preparare una valigia con la matematica?".  Qui di seguito cercheremo di rispondere a questa domanda.

Il problema dello zaino (o knapsack problem):

Chiunque abbia affrontato un viaggio, puntando per risparmiare su un volo Low Cost, sa benissimo che preparare una valigia rispettando i limiti imposti  per i bagagli a mano è tutto meno che una passeggiata.

viaggio_volo_low_cost_problema_zaino_knapsack

Probabilmente, però, non tutti voi saprete  che questo problema, indicato tradizionalmente come "problema dello zaino" (in inglese "Knapsack problem"), è invece un complesso problema matematico. Non entro nel dettaglio dello spiegare in che senso è complesso. Per i curiosi rimandiamo alla voce di wikipedia sui problemi NP-Completi.

Se la cosa si limitasse al preparare uno zaino rispettando un certo peso potremmo pensare che tale il problema sarebbe meritevole di  particolare attenzione.

Il fatto è, invece, che molti problemi reali alla fine possono essere ricondotti al "knapsack problem". Il bello della matematica è spesso questo: affronti un problema e poi scopri che quello stesso modo di risolverlo lo puoi usare in tanti altri contesti.

Facciamo qui solo alcuni esempi:

  • Dato un certo budget, decidere gli investimenti scegliendo fra n possibili pacchetti azionari;
  • come spendere il tuo stipendio per ottenere il maggior valore (o utilità) dai tuoi guadagni;
  • come gestire le scorte di un magazzino;
  • trovare il numero minore di aeroplani che possono essere utilizzati per fornire il servizio in una serie di tratte;
  • individuare quante persone dalle differenti abilità e corrispondenti salari si possono assumere in una azienda  per fare il maggior lavoro al minor costo 

Modello matematico: formalizziamo il problema dello zaino 0-1

zaino4

Vediamo quindi come formalizzare il problema dello zaino esprimendolo mediante il linguaggio matematico. Anche in questo caso la matematica si dimostrerà assolutamente efficace (leggi il nostro post il cui si parla della irragionevole efficacia).

Analizzeremo qui solo il caso in cui gli oggetti non si possano dividere ma si possa soltanto scegliere se metterli nello zaino (ne prendiamo 1) o non metterli nello zaino (ne prendiamo 0). Nel caso della nostro esempio iniziale del bagaglio a mano, ha perfettamente senso imporre la scelta 0-1 anche perchè portare mezzo maglione non è molto utile.

Segnaliamo che esiste anche la versione frazionaria dello stesso problema (piuttosto che rinunciare, a me è capitato di portare ad amici che vivevano all'estero, seguento le orme di Totò e Peppino e del loro mitico viaggio a Milano,   una cospicua frazione di forma di parmigiano!).

Nel caso 0-1 abbiamo una lista di n oggetti, il peso di ciascuno ed il corrispondente valore. A tutto questo si aggiunge il vincolo sul peso massimo ammissibile.

Abbiamo, quindi, n variabili x_1, x_2,....,x_n. Ciascuna generica variabile, indicata come x_j, può valere solo zero o uno:

knapsack problema zainoAbbiamo, inoltre, che la somma dei pesi deve essere minore di un valore massimo e che il nostro obiettivo è quello di rendere massimo il valore degli oggetti che mettiamo nel nostro zaino. In formule:

knapsack problema zaino

dove con v_j indichiamo il valore dell'oggetto j e  con p_j il corrispondente peso. Ricordiamo che con il simbolo \Sigma si indica l'operazione di sommatoria; messa per esteso la seconda relazione, per esempio, equivale a:p_1x_1+p_2x_2+p_3x_3+...p_nx_n \leq C.

Ora che abbiamo "formalizzato" il problema, la domanda successiva è: come lo risolvo?

Nel prossimo paragrafo vedremo uno dei possibili metodi risolutivi che sfrutta un particolare algoritmo  detto "greedy" che tradotto vuol dire  ingordo/goloso. Si conferma ancora una volta l'idea che gli algoritmi sono tutto intorno a noi! (Vi rimandiamo al post in cui vi parlavamo di questo).

L'algoritmo greedy ovvero ingordo

Proviamo a ragionare insieme sui possibili metodi per affrontare ilgreedy_algo problema.

La prima cosa che, in genere, si prova sempre è cercare la soluzione facendo tutti tentatitivi possibili. Questo metodo si chiama metodo per "forza bruta". Disponendo di computer, sulla carta, è un metodo promettente visto che la fatica la facciamo fare ad una macchina. Se, però, il numero di oggetti è elevato questo metodo non si può applicare perché, pur disponendo del computer più potente al  mondo, non ce la farebbe a calcolare il risultato  in un tempo ragionevolmente finito (per capirci: ci  mette un secolo e il tuo aereo è già bello che partito!).

Infatti per ogni oggetto nella lista devo scegliere se prenderlo o meno;  ogni elemento in più raddoppia le possibili scelte ed in generale queste crescono come 2^n. Per fare un esempio se ho 3 oggetti ho 2^3 casi, mentre se ho 1000 oggetti ne ho 2^{1000} che è un numero, direbbe Dante Alighieri, da "far tremar le vene ed i polsi" per quanto è grande.

È evidente che dobbiamo quindi cercare un criterio "furbo" per scegliere ed evitare di provare delle strade inutili. In altri termini serve ridurre le possibili strade da percorrere.

L'algoritmo greedy che, ricordiamo, vuol dire goloso, fa esattamente questo: offre un modo di scegliere poichè, dopo aver ordinato gli oggetti sceglie quello che "fa più gola"... vediamo con un esempio di capire meglio.

Consideriamo il seguente caso:

imageAbbiamo nove oggetti da mettere nel nostro ipotetico zaino/contenitore. Per ciascuno di questi è indicato il valore ed il peso.

Per esempio Il primo oggetto ha valore 50 e peso 31. Se scegliessimo di prenderlo dovremmo dire che la variabile x_1=1 oppure x_1=0 se lo volessimo escludere. Con C=100 indichiamo il peso massimo permesso.

Andiamo quindi ad ordinare i nove elementi rispetto al loro valore ed otteniamo la seguente sequenza: (65, 55, 50, 45, 40, 35, 25,18,16).

In base all'idea dell'algoritmo goloso si prende per primo l'oggetto 2 a cui corrisponde il valore massimo di 65 e quindi si avrà che x_2=1. Scelto il termine verifichiamo che il peso degli elementi scelti sia minore di quello massimo (al primo step la cosa è banale ovviamente). Si procede quindi, in modo iterativo, scegliendo il secondo della lista ordinata ovvero x_6=1. Si verifica che la somma dei primi due termini selezionati non superi 100 (abbiamo, infatti,  39+28<100)  e si ripete di nuovo. Se per caso l'oggetto scelto da aggiungere ha un peso tale da far superare il vincolo  si prova a scegliere il successivo e così via...

A questo punto siamo sicuri che il lettore più attento stara pensando che questo metodo ha un problema. Infatti prendendo via via oggetti di maggiore valore non stiamo tenendo conto del loro peso;  potrebbe, infatti, essere che mettendo due oggetti di minore valore ma di piccolo peso si  riesca ad ottenere  un valore maggiore.

Come possiamo tener conto anche del peso nello scegliere l'oggetto?

La risposta semplice è creare una nuova lista che chiameremo rendimento in cui ogni termine è dato dal rapporto fra il valore ed il peso:

 rendimento =\frac{valore}{peso}.

Questa scelta, tenendo conto non solo del valore ma anche del peso, offre la possibilità di trovare una soluzione migliore.

A questo punto rimane una ultima domanda: "la sequenza trovate  è sempre la migliore soluzione?"

La risposta è "putroppo no!". L'algoritmo greedy fornisce infatti un metodo molto semplice per trovare una "buona" soluzione ma non la migliore. Come vi avevo anticipato il problema sembra semplice e invece non lo è.

In fondo a questo post inserisco una serie di link utili per approfondire in cui sono illustrati anche altri algoritmi risolutivi.

Spunti didattici

Aggiungo uno spunto per una possibile attività didattica da fare condidattica_laboratoriale degli studenti. Prendetelo per quello che è: solo una bozza di attività, senza pretesa di esaustività, che si presta ad essere realizzata praticamente con qualunque età.

Da più parti si parla nella didattica della matematica di inserire, specialmente con gli studenti meno grandi, attività di gruppo che abbiano un "approccio laboratoriale" ovvero, banalizzando un po', che contemplino delle attività sperimentali in cui gli studenti si cimentino con problemi concreti anche "sporcandosi anche le mani" (qui è spiegato meglio e più approfonditamente).

Il problema dello zaino si presta davvero ad una attività di questo tipo. Dividete la classe in n squadre (vedete un po' voi in base al numero degli studenti) Portate (o fate portare) a scuola n valigie/zaini/contenitori  e $$n$ corrispondenti  lista di oggetti uguali ed una bilancia. Su ciascun oggetto attaccate un adesivo con indicato prezzo e peso.

Ogni squadra dovrà proporre la sequenza di oggetti da mettere in valigia formalizzando il ragionamento (algoritmo!) utilizzato per trovare la soluzione (per gli studenti più grandi, una successiva analisi e confronto dei diversi metodi proposti  sarebbe didatticamente molto utile).

Alla termine del tempo dato, ogni squadra dovrà mettere la valigia sulla bilancia per verificare che la soluzione proposta rispetti il vincolo sul peso.

Se volete lasciare nei commenti delle osservazioni per migliorare/criticare questo spunto, fate pure!

Pensiamo sia una cosa utile per tutti.

Link Utili

- Per chi vuole approfondire partendo da solide basi matematiche suggeriamo questo bellissimo libro in cui il problema dello zaino è descritto in modo formale in tutte le sie varianti e sono spiegati praticamente tutti i possibili algoritmi risolutivi.

- Qui delle dispense  di un corso universitario da cui, fra le altre cose, abbiamo preso spunto.

- Qui dispense su alcuni algoritmi detti euristici in cui rientra quello greedy da noi presentato.

- Per chi vuole rispolverare le sue conoscenze di ricerca operativa, invece, suggeriamo questo link

- In questo post trovate una riflessione più informatica dell'algoritmo in cui si sostiene che il mondo è in sostanza un "problema dello zaino"

- Qui un articolo di sintesi sulla didattica laboratoriale

P.S.

Francesco, altro autore del blog con cui mi sono confrontato su questo post, mi faceva notare che sul problema dello zaino si potevano aggiungere anche un altro paio di cose.

Ringrazio Francesco ed  aggiungo per i più "esperti e curiosi" le sue indicazioni qui di seguito:

1) in alcuni casi, laddove c'è esistenza della soluzione, c'è anche unicità al problema dello zaino. Ad esempio per le successioni cosiddette supercrescenti (il termine n-esimo è maggiore o uguale alla somma dei precedenti).

2) esiste il cifrario di Merkle-Hellman che utilizza appunto questo problema nel caso in cui vi è esistenza e unicità

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination