Commessi Viaggiatori VS Piccioni (Parte 2)
Ed eccoci quindi giunti alla seconda parte di questo viaggio. Vediamo subito la domanda che vi avrà certamente fatto perdere il sonno nelle scorse notti.
Nel caso in cui vi foste persi la prima parte, eccola qui sotto!
Ma come risolviamo il problema?
Nella prima puntata siamo andati alla scoperta dei grafi, strutture utili per rappresentare il nostro dilemma. Ma ora vorremmo sapere come trovare una soluzione.
Quando ci si trova davanti a problemi di questo tipo, abbiamo 2 possibilità:
- utilizzare un algoritmo euristico
- utilizzare un algoritmo ottimo
Non fatevi intimidire quando leggete la parola algoritmo. Per semplificare, possiamo dire che un algoritmo è una sequenza finita di passi. Ad esempio, la ricetta di una torta è un algoritmo e voi, mentre la eseguite cercando di preparare il vostro dolce preferito, siete proprio come un computer che esegue un algoritmo.
Certo, gli algoritmi eseguiti dai computer tendono ad essere un po’ più complicati, ma per ora non preoccupiamoci.
Nota (solo per i più pignoli). Diciamo che esisterebbe anche una terza via, quella degli algoritmi approssimati, ma ora non vogliamo complicare troppo le cose.
Di problemi ne abbiamo anche abbastanza e ora infatti faremo bene a chiederci: come scegliere quando usare un algoritmo euristico e uno ottimo? Principalmente in base al tempo e i soldi che abbiamo, come per tutto insomma, ma vediamo un po’ più nel dettaglio queste alternative.
Algoritmi Euristici
Supponiamo di essere nei panni del mercante svizzero: cosa fareste? Se non avete molta voglia di ragionare probabilmente vi recherete alla città più vicina. Dopo averla visitata e aver venduto le vostre merci, nella vostra mappa marcherete tale città con una bella X rossa (cioè, non ci metterete più piede fino al prossimo tour). E ora? Muovete il carretto verso la città più vicina a dove vi trovate. E così via, fino a che non avrete esaurito tutte le città. Semplice, no?
Già, tuttavia questo approccio, basato su di una regola che vi siete inventati (un’euristica, appunto) non vi garantisce affatto di fare il percorso più breve. Diciamo che in media questa soluzione vi farà fare un 25 % di strada in più della soluzione migliore che possiate trovare.
Ma vediamo un esempio pratico. Supponiamo di avere 5 città chiamate, molto fantasiosamente, A, B, C, D, E. Non tutte queste città sono collegate direttamente tra di loro. Ad esempio, non ci è possibile andare da A ad E.
Delle città che invece sono tra loro collegate, possiamo dire:
- per andare da A a B impieghiamo 50 chilometri
- per andare da A a D impieghiamo 75 chilometri
- per andare da B a C impieghiamo 100 chilometri
- per andare da B a E impieghiamo 50 chilometri
- per andare da C a D impieghiamo 25 chilometri
- per andare da C a E impieghiamo 50 chilometri
- per andare da D a E impieghiamo 75 chilometri
Per ciascuno dei punti precedenti possiamo tranquillamente pensare che anche per andare da B ad A impiegheremo 50 chilometri. Quindi, possiamo rappresentare tutte queste informazioni con un grafo non orientato. Proprio come qui sotto (anche se i chilometri non sono riportati).
Come noterete, la rappresentazione che facciamo qui non ha niente a che fare con la geometria: la distanza che separa le città C e D è diversa dalla distanza che separa B da C, ma possiamo rappresentare il collegamento con segmenti della stessa lunghezza.
Ora supponete di vestire i panni del Commesso Viaggiatore a di trovarvi nella città A. Cosa fare? Potete scegliere tra:
- recarvi nella città B e farvi 50 chilometri
- recarvi nella città D e farvi 75 chilometri
Applicando la vostra euristica, andate verso B. Una volta raggiunta, non potete tornare indietro, quindi potete scegliere tra andare in C oppure in E. Insomma, ormai dovreste aver capito come funziona.
Alla fine, una volta tornati nella vostra città A, avrete percorso un totale di 250 chilometri. Bisogna dire che per questo esempio è difficile trovare una soluzione migliore, quindi vi è andata bene.
Ma cosa fareste nel caso in cui anziché 5 città ne aveste 100, o anche 1000? Certo, questo approccio continua a funzionare e vi riporta a casa, ma potrebbe farvi fare molta strada in più di quanta non ne fareste con una soluzione migliore (o magari ottima).
Algoritmi Ottimi
C’è bisogno di aggiungere altro? Mi sembra ovvio che un algoritmo ottimo vi garantisca di trovare la soluzione ottima! E cosa vuol dire soluzione ottima? Semplice, che non esistono soluzioni nelle quali il percorso totale è più corto di quello trovato. Certo, possiamo avere più soluzioni ottime, ma se non abbiamo ulteriori criteri per distinguerle, una vale esattamente come l’altra.
Ora la giusta domanda da porsi sarebbe: e come facciamo a trovare la soluzione ottima? Ma anche qui la risposta dovrebbe balzarvi subito in mente:
LE PROVIAMO TUTTE!
Semplice, no? Beh, più o meno. Torniamo all’esempio con le nostre 5 città A, B, C, D, E e ora supponiamo che tutte le città siano direttamente connesse tra di loro (cioè A è connessa con B, C, D, E — B è connessa con A, C, D, E — e così via…). Ora cerchiamo di contare le soluzioni.
Partendo da A adesso abbiamo 4 possibili scelte: B, C, D, E. Scegliamo C (a caso). Adesso possiamo scegliere tra B, D, E (3 scelte). Prendiamo D. Adesso ci restano B ed E (2 scelte). Prendiamo B e quindi la nostra ultima tappa sarà E.
La nostra soluzione sarà quindi il percorso A, C, D, B, E. Ma questa è solo una.
Se ora torniamo indietro e proviamo ogni possibile scelta vedremo che il numero delle soluzioni possibili sarà:
4 * 3 * 2 * 1 = 24
Niente male! In un’oretta potete provarle tutte e trovare la migliore! Tuttavia, 5 città non sono molte e nella realtà potremmo trovarci a dover risolvere questo problema con 1000 città. Questo vuol dire che le possibili soluzioni sono
999 * 998 * 997 * 996 * … * 3 * 2 * 1
Abbiamo un modo più conveniente per scrivere questo numero e cioè 999! (si legge 999 fattoriale). Ecco questo numero è molto grande e per questo non mi va di scriverlo qua (però lo trovate nelle note). Pensate che ha 2565 cifre ed è un numero che supera di gran lunga il numero di atomi nell’universo.
Eppure ci sono dei software che ci permettono di risolvere anche problemi così grandi. E il bello è che non serve il computer più potente del mondo per farlo, spesso basta anche solo il vostro pc.
Certo, questi programmi sono molto furbi e non devono veramente provare tutte le soluzioni. Inoltre, nel casi reali del problema del Commesso Viaggiatore, non capita spesso che tutte le città siano connesse tra di loro (quindi le soluzioni possibili sono un po’ meno). Ma il ragionamento precedente dovrebbe servire a darvi un’idea della complessità del problema.
Ah, ma ora mi chiedete qual’è il prezzo. Questo è un altro discorso. Ecco, dipende. Avete molti soldi? Bene, potete acquistare la licenza di un software che vi permette di trovare soluzioni ottime per il Problema del Commesso Viaggiatore (e per molti altri problemi simili a questo). Parliamo di cifre a 4 zeri. Per un anno e poi scade. Diciamo che non è proprio la licenza di WinRAR, è qualcosa di un po’ più sofisticato.
Cosa?! Non avete neanche un centesimo?! Ok, forse qualche alternativa magari c’è. In effetti esiste Concorde, un software che vi permette di risolvere proprio questo problema ed è anche open source (sì, vuol dire che è gratis in pratica).
Ma perché una soluzione ottenuta con un algoritmo euristico non va bene? In realtà può andare bene in alcuni casi, ma a volte questo può costare molte risorse. E se queste risorse sono limitate (come ad esempio il tempo) o costano molto (pensate al carburante che serve ad un camion per fare 1000 chilometri) allora si cerca di ottimizzarle al meglio.
Per questo esiste una disciplina che si occupa di studiare e risolvere al meglio problemi come quello del nostro commesso viaggiatore. Questa disciplina è la Ricerca Operativa e probabilmente ne sentirete ancora parlare se continuerete a seguirci.
E gli animali?
Il problema ha sempre affascinato moltissimi scienziati, e non è passato molto tempo prima che anche qualche biologo si industriasse per cercare di farlo risolvere ad altri animali: qualcuno ha dunque speso preziose energie (e denaro) per far procedere lungo una serie di punti, primati, volatili e addirittura organismi unicellulari.
Uno studio particolarmente originale ha cercato di capire infatti come un’ameba, priva di cellule nervose e dunque di qualsiasi capacità di ragionamento, avrebbe potuto risolvere il problema.
Gli scienziati hanno applicato in una ventina di punti di una piastra di coltura alcune sostanze chemiotattiche, capaci cioè di attirare l’organismo unicellulare come una sorta di nutrimento, per vedere come l’organismo avrebbe agito per inglobarle tutte. L’organismo veniva dunque adagiato sulla piastra di coltura: i nostri amici al microscopio hanno potuto vederlo coprire tutte le zone dove si trovava la sostanza chemiotattica ed abbandonare invece quelle dove non era presente, creando dunque con il suo corpo una connessione tra i vari punti (come nelle immagini qui in basso).
Confrontando la disposizione con il miglior pattern di connessione tra i punti, gli scienziati hanno riscontrato uno scostamento del 6% in più, scostamento tra l’altro probabilmente dovuto all’accomodamento della tensione superficiale.
Tenendo conto che l’approccio euristico descritto in precedenza permette di ottenere risultati del 25% più lunghi rispetto al pattern ottimale, questo è certamente un risultato impressionante. Niente male per una bestia senza cervello!
Un altro studio ha avuto come oggetto degli animali forse più intelligenti ma non certo meno repellenti delle amebe: i piccioni.
Gli studiosi hanno collocato alcuni esemplari di questi maledetti volatili in una gabbia collegata ad una camera contenente 3 distributori di cibo (in particolare, piselli).
Liberati ad un angolo della stanza i piccioni si sono mossi nella stanza spostandosi da un distributore ad un altro seguendo un pattern basato sulla prossimità, ovvero spostandosi di volta in volta verso il distributore più vicino. In un secondo esperimento inoltre gli studiosi hanno collocato la gabbia al centro della stanza, disponendo i distributori ad eguale distanza attorno a questa in modo da non incorrere in bias relativi alla posizione della partenza. In questa seconda fase si è osservato come i volatili continuassero a preferire itinerari basati sui distributori più vicini tra loro, ma seguendo comunque pattern improntati sul minor consumo di energie possibile, fatto che sembra suggerire la presenza in loro di una consapevolezza spaziale e di una capacità di previsione per quanto riguarda i viaggi successivi.
Sono stati ovviamente scartati dalle analisi tutte le sessioni in cui i piccioni non hanno visitato tutti i distributori o quelle in cui sono ritornati ad un distributore già visitato in precedenza. Ogni volta che qualcuna di queste situazioni si presentava le luci della stanza venivano spente e l’esperimento fermato. Le sessioni escluse, incredibilmente, sono state soltanto il 25% del totale.
Questi risultati sono stati rafforzati anche da un altro studio che ha osservato come i piccioni, se riesposti al medesimo scenario, siano in grado di scegliere dei percorsi ancora più efficaci rispetto alla prima esposizione. In breve, sono capaci di imparare, forse meglio di quanto non sia in grado di fare tu!
Ovviamente scherziamo, però non vogliamo attirarci le ire di quelli che potrebbero essere i nostri futuri dominatori (Douglas Adams sbagliava riguardo ai topi, non aveva considerato la suprema intelligenza dei piccioni).
Link utili
Note
999! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
