• Non ci sono risultati.

Il piano del traffico

N/A
N/A
Protected

Academic year: 2022

Condividi "Il piano del traffico"

Copied!
26
0
0

Testo completo

(1)

9.

Il piano del traffico

Un modesto contribUto

Ove si discute di città reali e fantastiche, di connessioni stradali e reti di calcolatori, per giungere a una proposta parzialmente demenziale ma scientificamente fondata su come organizzare il traffico cittadino facendo muovere a caso gli automobilisti. È un

modesto contributo che offriamo di buon cuore agli amministratori pubblici più coraggiosi.

La città di Königsberg ha conosciuto uno splendore ormai lontano nel tempo. residenza del Gran maestro dell’ordine dei templari, sede dell’Università fondata nel cinquecento da Alberto di brandeburgo, vi si inco- ronarono per due secoli i re di Prussia in una cattedrale gotica rasa al suolo dai bombardamenti sovietici dell’ulti- ma guerra assieme al castello ducale e ai palazzi più anti- chi. ora, con il nome russo di Kaliningrad, è dominata da insediamenti industriali che hanno trasformato il fa- scino antico in grigiore contemporaneo e il discreto roto- lio dei carri nel rombo dei veicoli a motore. naturalmen- te la stessa trasformazione è avvenuta in moltissime città:

ma a Königsberg dispiace più che altrove per il ruolo particolare che le ha assegnato la storia della matematica.

La città sorge sul fiume Pregel, oggi Pregolja, e si svi- luppa lungo le sue rive in forme inusuali, come si può rilevare da una cartina schematica che ci è giunta attra- verso la più nobile documentazione matematica [fig. 1].

sette ponti collegano i quartieri antichi un tempo cinti di mura, tra cui Kneiphof sull’isola omonima, cuore della vita cittadina; e qui passeggiando si discuteva un grazio- so problema di traffico locale che è doveroso ricordare

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 123

(2)

1 riflettere passeggiando per la città è tipico dei popoli di cultura tede- sca come dimostra un piccolo gioiello, La passeggiata, di robert Walser, Adelphi, milano 1976. il lavoro originale di eulero si può leggere comoda- mente, tradotto in inglese, nel primo volume della raccolta, The World of Mathematics di J.r. newman, tempus books 1988. naturalmente l’interes- se per questo lavoro è solo storico, ma desta profonda ammirazione la sem- plicità con cui alcuni matematici del passato seppero sviluppare teorie fon- damentali.

Fig. 1 - La città di Köngsberg nel disegno di eulero.

con le parole che eulero pronunciò nel 1735 davanti agli Accademici di san Pietroburgo (la cartina è negli atti di quella presentazione)1:

nella città di Königsberg in Prussia vi è un’isola A, chiamata Kneiphof, attorno a cui fluiscono due rami del fiume Pregel, come è mostrato nella figura 1. Vi sono sette ponti a, b, c, d, e, f, g che attra- versano i due rami. La questione è se una persona possa scegliere una passeggiata che la porti a traversare ognuno dei ponti una volta ma non più di una volta. mi è stato detto che alcuni negano questa possibilità e altri sono in dubbio, ma che nessuno sostiene che è cer- tamente possibile. su queste basi ho formulato per me stesso il se- guente problema molto generale: data una qualsiasi configurazione del fiume e dei rami in cui si può dividere, e qualsiasi numero di ponti, determinare se è possibile attraversare ciascun ponte esatta- mente una volta.

indicata la soluzione del problema generale eulero di- mostrò che nel caso dei ponti di Königsberg il percorso

(3)

Il piano del traffico 125

non esiste: questa presentazione segnò la nascita di una importantissima branca della matematica che avrebbe preso il nome di teoria dei grafi.

oggi i pedoni sono rari e le loro riflessioni, per lo più malevole, sono rivolte agli automobilisti che li sfiorano con noncuranza, li intossicano di gas e rumore, li imbrat- tano d’acqua sporca affondando le ruote nelle pozzan- ghere. né gli automobilisti sembrano più felici nella trappola di code infinite che li rendono nervosissimi. Fi- gurarsi cosa accade sugli antichi ponti di Königsberg do- ve, per la ristrettezza della sede, le automobili devono transitare una alla volta in un senso o nell’altro. La matti- na il traffico fluisce principalmente dalla periferia B, C verso il centro A, D, e all’interno del centro tra A e D. È facile rendersi conto che se un giorno molti automobilisti devono spostarsi da C a D può essere conveniente che parte di essi, anziché attraversare il ponte diretto g su cui si formerà una lunga coda, seguano un percorso alterna- tivo attraverso uno dei ponti c, d che conducono ad A, e di qui attraversino il ponte e; questo è ancor più vantag- gioso se molti automobiisti sono diretti quel giorno da D a C rallentando ulteriormente il traffico sul ponte g, ma non molti devono transitare all’interno del centro tra A e D impegnando il ponte e. si possono naturalmente co- struire esempi di ogni sorta che provino o contrastino teorie sul traffico ideale, ma solo conoscendo a priori l’origine e la destinazione di tutti i veicoli si può determi- nare una soluzione ottima giorno per giorno. Per esem- pio le automobili numerate da 1 a 8 nella seguente tabel- la di origini e destinazioni possono completare il loro percorso in due passi complessivi partendo tutte contem- poraneamente: il lettore potrà scoprire la soluzione per proprio conto, notando che due dei quattro veicoli che si

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 125

(4)

spostano tra A e D dovranno impegnare rotte alternative al ponte e, pena ritardare l’ultimo passaggio fino al quar- to passo.

Automobile 1 2 3 4 5 6 7 8

origine A A B B C C D D

destinazione D D A D A B A A

conoscendo le tendenze generali si possono prendere provvedimenti di massima per migliorare il traffico: è quello che fanno molti amministratori comunali sulla ba- se di rilevazioni sui flussi di veicoli e sull’ubicazione delle abitazioni dei membri della giunta. Poiché però i fini de- gli automobilisti sono in gran parte imprevedibili sareb- bero necessari provvedimenti scientifici che nessuno ha avuto finora la spregiudicatezza di adottare. Li proporre- mo qui, dopo una discussione sulla struttura viaria delle città reali e ideali, e un esame delle reti telematiche ove sono stati affrontati gli stessi problemi per la distribuzio- ne dei messaggi. ma occorrono alcune premesse.

La nostra società si sta organizzando attorno a com- plicati grovigli di canali per la trasmissione di informa- zione che prendono genericamente il nome di reti di cal- colatori o semplicemente reti. nella forma più generale esse contengono calcolatori di qualsiasi tipo, connessi in modo arbitrario e disposti in un’area geografica arbitra- riamente grande. Attualmente un’enorme rete detta in- ternet ha catturato, come una ragnatela fittissima, gran parte dei calcolatori e delle reti esistenti al mondo per metterli in comunicazione gli uni con gli altri. Utilizza- tori assolutamente eterogenei discorrono attraverso un insieme di collegamenti che si sviluppa su moltissimi strati e livelli con le modalità più varie, in un assetto

(5)

Il piano del traffico 127

2 ottavia è stata scoperta e descritta da i. cALVino, Le città invisibili, einaudi, torino 1972, p. 81.

strampalato e irregolare che accomuna internet alla città di ottavia2:

ora vi dirò come è fatta ottavia, città-ragnatela. c’è un precipizio tra due montagne scoscese: la città è nel vuoto, legata alle due creste con funi catene e passerelle. si cammina sulle traversine di legno, at- tenti a non mettere il piede negli intervalli, o ci si aggrappa alle maglie di canapa. sotto non c’è niente per centinaia e centinaia di metri:

qualche nuvola scorre; si intravede più in basso il fondo del burrone.

Questa è la base della città: una rete che serve da passaggio e da sostegno. tutto il resto, invece di elevarsi sopra, sta appeso sotto:

scale di corda, amache, case fatte a sacco, attaccapanni, terrazzi co- me navicelle, otri d’acqua, becchi del gas, girarrosti, cesti appesi a spaghi, montacarichi, docce, trapezi e anelli per i giochi, teleferiche, lampadari, vasi con piante dal fogliame pendulo.

sospesa nell’abisso, la vita degli abitanti di ottavia è meno incer- ta che in altre città. sanno che più di tanto la rete non regge.

Legati gli uni agli altri i calcolatori di una rete comuni- cano tra loro scambiandosi testi, figure, musica, grazie a servizi appositi (come il World Wide Web, familiarmen- te www) che permettono agli utenti più sprovveduti di accedere senza alcuno sforzo alle informazioni che altri hanno deciso di diffondere. ma dietro questa semplicità d’impiego si cela un formidabile lavoro di gestione della rete perché i messaggi ivi immessi devono essere avviati a destinazione disturbandosi tra loro il meno possibile. il traffico è enorme e continuo e l’effettiva utilità del servi- zio dipende dal tempo di risposta che nelle ore di punta può aumentare paurosamente. il problema dell’instrada- mento dei messaggi è dunque di fondamentale importan- za: questi circolano nella rete come veicoli di una metro- poli popolata intensamente e sviluppata in modo selvag-

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 127

(6)

3 Apocalisse, 21, 2. La versione italiana è quella de La Sacra Bibbia, edi- zioni Paoline, roma 1961.

gio, formando code e ingorghi. ma non tutte le città, e non tutte le reti, sono nate senza un piano preciso.

Le civiltà antiche tennero in gran conto i criteri di pia- nificazione urbana. A solidi concetti d’ingegneria si mi- schiavano necessità divine, ma non è improbabile che queste fossero influenzate a loro volta dalla conformazio- ne del suolo. ninive fu costruita sulla forma dell’orsa maggiore; Assur sulla forma di Arturo; cusco sulla for- ma del puma (che era simbolo di potere religioso, ma in quel caso aveva la sua testa naturale sul colle di sac- sahuaman e il dorso lungo il fiume tullumayo). Gli in- diani costruirono le città dei re obbedendo a un modello mitico. Gli ebrei venerarono l’archetipo di città divina annunciato da tutti i profeti e descritto da Giovanni nel- l’Apocalisse: la celeste Gerusalemme, circondata da un muro quadrato su cui si aprivano dodici porte

e scendeva dal cielo, da presso dio, pronta come una sposa abbiglia- ta per il suo sposo3.

i romani, molto più pratici, costruirono città reticolari percorse da un «cardo» e un «decumano» perpendicola- ri tra loro su cui si aprivano strade parallele: ecco così l’impianto romano del centro di Verona con la confluen- za dei due assi principali in Piazza delle erbe, ancora perfettamente riconoscibile nelle fotografie aeree [fig. 2]:

impianto che sarebbe stato ripreso da tanti edificatori con molta fretta e poca fantasia, come in manhattan la cui simmetria è spezzata solo dal preesistente tracciato indiano di broadway, o Washington il cui reticolo è ta- gliato da alcuni viali a 30 e 60 gradi.

(7)

Il piano del traffico 129

Fig. 2 - Verona (a sinistra) e chioggia (a destra).

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 129

(8)

4 Un ottimo testo per uno studio iniziale dell’impianto storico urbani- stico delle città italiane è Capire l’Italia. Le città, edito dal touring club ita- liano nel 1978; di lì sono tratte le fotografie aeree di Verona e chioggia. nu- merosi sono i trattati di urbanistica a carattere tecnico ma godibili anche dai non specialisti. citiamo per esempio la Storia dell’urbanistica di e. Guidoni, Laterza, bari 1979, da cui è tratta la mappa seicentesca di canton; e La pra- tica della progettazione urbana di r. Unwin, il saggiatore, milano 1971, per lo studio strutturale delle città moderne.

La storia riserva in questo campo moltissime sorprese che sarebbe impossibile elencare4. esempi perfetti si trovano in italia. chioggia, non toccata dalle invasioni dei barbari, ha conservato una struttura medievale a spi- na di pesce, solcata da brevi strade parallele che si uni- scono lungo una costola centrale senza comunicare tra loro [fig. 2]. Lucignano in Val di chiana è costruita lun- go una strada medievale che si eleva a spirale verso la sommità del colle, secondo uno schema che sarebbe sta- to riproposto verso la fine del Quattrocento da France- sco di Giorgio martini come ideale di città d’altura [fig. 3]: proposta che nasceva in un’epoca in cui Leonar- do, Filarete, scamozzi delineavano un’urbanistica nuova fondendo arte e scienza in progetti ideali e in realizza- zioni straordinarie. ecco così nascere Palmanova, pro- gettata in forma di ruota poligonale da Giulio savor- gnan [fig. 4].

se questi esempi costituiscono la perfezione, molte città hanno impianti urbani che si avvicinano agli sche- mi ideali o ne sono un miscuglio. Le cittadine distese lungo strade di grande comunicazione hanno forma pre- valente a spina di pesce. importanti centri di pianura hanno forma di stella: come milano, con le grandi strade radiali che confluiscono nella Piazza del duomo, chiusa

(9)

Il piano del traffico 131

Fig. 3 - città ideali d’altura

(dal «trattato di Architettura» di Francesco di Giorgio martini)

Fig. 4 - Palmanova (com’è ancor oggi) 09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 131

(10)

5 La struttura appare già nel codice Atlantico di Leonardo, in uno schizzo di milano.

a ruota nelle cerchie concentriche dei viali che sorgono sui tracciati originali del naviglio e delle mura spa- gnole5. Parigi contiene molte stelle collegate tra loro, per esempio quelle che hanno i centri nell’Étoile, nel trocadéro e nella piazza Victor Hugo. canton è una composizione di spine [fig. 5]. Valparaiso combina un impianto reticolare regolare nella striscia pianeggiante del porto con un’anarchica miriade di stradine nei quar- tieri popolari che si inerpicano sulle colline alle spalle [fig. 6]; e mentre qui la struttura è imposta dalla confor- mazione del suolo, un contrasto simile è nato in città ove diversi quartieri si sono sviluppati in epoche e con finalità diverse: così bari affianca la ruota della città vec- chia al perfetto reticolo della espansione ottocentesca;

ma l’apice è probabilmente Lagos che contrappone l’in- fernale disordine urbanistico delle zone spontanee al preciso reticolo di quelle pianificate. e, fuori da ogni schema, brugge si distende con grazia tra i suoi canali [fig. 6].

ogni città, in sostanza, ha una sua logica e una sua struttura più o meno nascoste: l’importante è scoprirle. e la stessa cosa avviene per le reti cui è il momento di tor- nare.

Un esempio di grande ordine è fornito dal calcolo pa- rallelo di cui ci siamo occupati nel capitolo 6. in questo ambito più calcolatori partecipano alla soluzione di un problema comune e l’organizzazione del calcolo è molto semplificata perché essi sono dello stesso tipo, sono col- legati in modo regolare e sono vicini tra loro: come limi- te, per altro comune, molti calcolatori elementari identici

(11)

Il piano del traffico 133

Fig. 5 - Parigi com’è oggi (a sinistra) e canton nel seicento (a destra).

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 133

(12)

Fig. 6 - Valparaiso com’è oggi (in alto) e brugge nel cinquecento (in basso).

(13)

Il piano del traffico 135

costituiscono i componenti di una stessa grande macchi- na. ma qualunque struttura si scelga non è mai possibile collegare direttamente un calcolatore a tutti gli altri sen- za introdurre un colossale groviglio di collegamenti: le trame, o reti, di connessione assumono così forme sem- plici e regolari come quelle mostrate nella figura 7. i no- mi assegnati alle diverse reti richiamano oggetti comuni, come avviene per le strutture cittadine: il parallelo tra re- ti e città è immediato. nella figura ogni calcolatore (nodo della rete) è rappresentato da un pallino nero ed è unito tramite collegamenti (archi) a un piccolo numero di nodi vicini; è facile immaginare come mutano le diverse confi- gurazioni all’aumentare del numero di nodi della rete.

Fig. 7 - diverse forme di reti di connessione.

Altre due strutture hanno grande importanza nel colle- gamento tra calcolatori ma non hanno equivalenti urbani:

dobbiamo descriverle perché lo sviluppo degli algoritmi

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 135

(14)

6 Questa famosa immagine di sviluppo del Coprinus Sterquilinus è trat- ta dal lavoro di A.H.r. buller: Researches on Fungi, vol. 4, Longmans Green London 1931. A parte il nome la colonia ha sorprendenti affinità strutturali con alcune reti informatiche.

di rete è passato crucialmente attraverso di esse. L’albero binario realizza il concetto di ramificazione sviluppandosi per successive divisioni in due parti [fig. 8]. il nodo di partenza (la radice, R nella figura) ha due vicini; i nodi successivi (interni) ne hanno tre; i nodi terminali (foglie) ne hanno uno. Per qualunque coppia di nodi vi è un per- corso (e uno solo) che li connette. È difficile immaginare che una comunità umana accetti di collegarsi in tal modo, risalendo sempre per vie gerarchiche senza stabilire colle- gamenti trasversali: l’albero binario appare invece nelle colonie di funghi i cui problemi di traffico, probabilmente interessantissimi, esulano dalla nostra discussione6[fig. 8]

Fig. 8 - strutture ramificate: albero binario (a sinistra) e colonia di funghi (a destra).

e veniamo ora a una struttura fondamentale per cui vi sarà bisogno di qualche spiegazione [fig. 9]. L’ipercubo, o semplicemente cubo, cresce con una regola sua. La fi- gura lo rappresenta in quattro dimensioni, con 24 = 16 nodi (i «vertici») e quattro archi partenti da ogni nodo (gli «spigoli»); il ruolo dei «nomi» scritti in codice bina-

R

(15)

Il piano del traffico 137

rio all’interno di ogni nodo sarà chiaro tra breve. Questo ipercubo può essere considerato l’unione di due ipercubi in tre dimensioni, cioè due usuali cubi posti a sinistra e a destra nel disegno; ciascuno di questi contiene 23= 8 no- di e tre archi per nodo, e ogni nodo è collegato con uno corrispondente nell’altro cubo. i nomi dei nodi identifi- cano i due cubi: in uno di essi iniziano con la cifra 0, nell’altro con la cifra 1. ogni cubo in tre dimensioni è a sua volta l’unione di due cubi in due dimensioni, cioè due quadrati di 22 = 4 nodi collegati tra loro, che si di- stinguono per il valore della seconda cifra dei nomi; e ogni quadrato è l’unione di due cubi in una dimensione, cioè due segmenti, distinti dalla terza cifra dei nomi.

Fig. 9 - L’ipercubo in quattro dimensioni.

individuata la regola possiamo far crescere la struttura verso dimensioni arbitrariamente grandi: un ipercubo in cinque dimensioni è l’unione di due ipercubi come quel- lo della figura, con ogni nodo dell’uno connesso a un corrispondente nodo dell’altro: i nodi divengono com-

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 137

(16)

7 La distanza tra due nodi dell’ipercubo è dunque al più k = log2n, contro il valore √n della maglia o n/2 dell’anello.

plessivamente 25 = 32 e ciascuno ha cinque vicini. La rappresentazione grafica si complica parecchio. Ai nomi dei nodi si premette una nuova cifra: 0 in un ipercubo componente, 1 nell’altro. in conclusione un ipercubo in k dimensioni contiene n = 2knodi con k vicini ciascuno, ma lo svantaggio di un vicinato che cresce con k è limita- to perché tale valore è molto piccolo rispetto a n. cia- scun nodo ha un nome di k cifre binarie che indicano or- dinatamente la scomposizione della struttura in cubi via via più piccoli.

notiamo ora che due nodi vicini hanno nomi che diffe- riscono esattamente in una cifra; quindi se due nodi han- no nomi che differiscono in d cifre essi si possono colle- gare con un percorso di d archi transitando attraverso una sequenza di altri nodi i cui nomi differiscono via via in una cifra. così dal nodo 0001 si può spedire un mes- saggio al nodo 1111 attraverso vari percorsi di tre archi, uno dei quali attraversa ordinatamente i nodi 0001-1001- 1101-1111: questo percorso è costruito con la regola standard che prevede di operare sulle cifre che devono essere cambiate scandendo il nome da sinistra a destra.

si occupano dell’istradamento i nodi (calcolatori) rag- giunti a ogni passo esaminando il nome della destinazio- ne che è incluso nel messaggio. in conclusione da cia- scun nodo se ne può raggiungere ogni altro percorrendo al più k archi, poiché questo è il massimo numero di ci- fre per cui due nomi possono differire. Quindi i percorsi sono sempre brevi, caratteristica questa molto importan- te in una rete7. tuttavia il tempo di percorrenza di un messaggio può essere grande a causa degli ingorghi che

(17)

Il piano del traffico 139

8 Uno studio di qualche serietà in questo campo richiede conoscenze non banali di informatica, tecnica delle trasmissioni e calcolo delle probabi- lità. sarebbe fuori luogo indicare qui le numerosissime fonti di riferimento.

si verificano sui nodi e sugli archi quando più messaggi transitano nella rete, anche se le origini e le destinazioni di essi sono tutte distinte.

supponiamo che vengano inviati contemporaneamente due messaggi, uno da 0000 a 1010, l’altro da 1100 a 1011.

La regola standard genera i percorsi indicati rispettiva- mente con linee punteggiata e tratteggiata nella figura 9:

0000 1000 1010

1100 1000 1010 1011

che interferiscono nel nodo 1000 e nell’arco (1000- 1010). naturalmente se si adottasse una regola di istra- damento diversa dalla standard questi ingorghi potreb- bero essere evitati, ma ne nascerebbero altri per messag- gi diversi: l’esempio può essere esteso a altre regole, a molti messaggi e a code assai più lunghe. Lo studio ma- tematico del traffico in queste condizioni è molto com- plesso, e solo alcuni brillanti risultati dell’inizio degli an- ni ottanta hanno permesso alle reti di raggiungere l’effi- cienza di oggi: li ricorderemo nel modo più semplice e informale possibile8.

tutto cominciò con l’ipercubo in k dimensioni che per le sue proprietà ben si prestava al calcolo parallelo di importanti funzioni matematiche. erano bensì noti alcu- ni casi sfavorevolissimi in cui la lunghezza delle code cre- sce in modo esponenziale con k pur se tutte le destina- zioni dei messaggi sono diverse tra loro; ma uno studio probabilistico dimostrava che, scegliendo le destinazioni

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 139

(18)

a caso e inviando i messaggi con l’algoritmo standard, si formano code non più lunghe di k. e questo si pensava dovesse accadere nella normalità dei casi, quando si pre- sentò un probema inaspettato che ci invita a riflettere an- che sul traffico urbano.

il motivo principale per cui si formano code inutili è che molti viaggiatori seguono gli stessi percorsi pur diri- gendosi verso destinazioni differenti (ché se la destina- zione fosse la stessa per tutti la coda sarebbe ivi inevita- bile). Gli automobilisti tendono a agglomerarsi per certe loro necessità o gusti o ragionamenti comuni che li por- tano a prediligere sempre alcune strade, salvo maledire i loro simili che hanno scelto le stesse strade nello stesso tempo. inaspettatamente il calcolo parallelo invita allo stesso comportamento: i progettisti di algoritmi hanno la radicata tendenza a far eseguire operazioni simili da tutti i calcolatori che partecipano al gioco, e a fargli inviare messaggi sugli stessi percorsi. così gli algoritmi esistenti creano in genere ingorghi di traffico ben superiori a quelli che nascerebbero se i messaggi viaggiassero a caso:

ciò avviene in particolare nell’ipercubo.

nacque allora un’idea che avrebbe inciso profonda- mente sul modo di utilizzare le reti di interconnessione:

la si accredita giustamente a Valiant, brillante professore di Harvard, anche se era ormai maturata nell’intera co- munità sientifica. se nell’esecuzione di un calcolo un messaggio deve spostarsi da un nodo a un’altro dell’iper- cubo, lo si invii prima a una destinazione scelta a caso e di qui alla destinazione reale. Pur impiegando l’algorit- mo standard l’istradamento del messaggio avrà carattere di casualità in entrambe le fasi, poiché nella prima è casuale la destinazione e nella seconda l’origine: dunque dovrebbero formarsi code di lunghezza massima k.

(19)

Il piano del traffico 141

Valiant dimostrò che in effetti ciò avviene con altissima probabilità, affermazione che va presa nel senso già di- scusso nel capitolo 7: operando sui parametri della rete la probabilità che si formino code più lunghe di k può essere resa arbitrariamente inferiore a quella che l’intero sistema si guasti per qualsiasi altra causa. in breve questa tecnica fu estesa a reti di tutte le forme, ciascuna delle quali ammette un istradamento efficiente se in una prima fase si dirigono i messaggi verso destinazioni intermedie scelte a caso: l’ostinata tendenza dei progettisti di algorit- mi paralleli (ma forse potremmo dire degli stessi proble- mi da risolvere) a creare ingorghi nel traffico viene così sconfitta da un’allegra anarchia di percorsi casuali.

e allora perché non applicare la stessa tecnica al traffi- co automobilistico? ogni città richiederebbe un suo al- goritmo che dipende dalla forma del tessuto urbano, ma in tutte si dovrebbe osservare la stessa regola fondamen- tale: ogni automobilista inizi il suo viaggio dirigendosi verso una destinazione a caso e di lì proceda verso la de- stinazione finale. Le due fasi verrebbero eseguite con l’algoritmo più adatto alla città o con qualunque strategia il guidatore abbia in mente, e la casualità introdotta nel percorso renderebbe questo diverso da tutti gli altri. Lo studio delle reti indica anche la lunghezza che deve avere il tratto casuale di percorso in relazione alla forma dei collegamenti: nell’ipercubo si devono percorrere k archi, risultato di scarsa utilità per gli automobilisti poiché non si conoscono città organizzate in questo modo; ma per le reti somiglianti a tessuti urbani i risultati divengono inte- ressanti. non vogliamo entrare in dettagli matematici che saranno approfonditi quando la nuova tecnica sarà adot- tata da qualche amministrazione comunale: chiariremo però come sia possibile metterla in pratica.

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 141

(20)

9 conoscere la destinazione casuale prima di iniziare a muoversi, o sce- gliere mosse casuali in successione, conduce in alcune reti a risultati proba- bilistici diversi ma comunque paragonabili.

il problema principale è quello di dotare l’automobili- sta di un mezzo attraente e pratico per procedere a caso.

Valiant lo risolse sull’ipercubo impiegando un program- ma noto come «generatore di numeri casuali» che co- struisce per ogni messaggio un pacchetto di k cifre bina- rie da utilizzare come indirizzo intermedio: il messaggio prendeva questa direzione, accompagnato dal nome del nodo finale verso cui completare il percorso. mentre nel- la rete l’istradamento del messaggio è curato dai nodi via via raggiunti, l’automobilista dovrà dirigersi personal- mente lungo il percorso che gli è imposto dal caso. È prevedibile che le ditte giapponesi istallino un computer di bordo collegato alla messa in moto, che indichi la de- stinazione casuale da raggiungere su una mappa della città proiettata sul cruscotto. A noi sembra più attraente assaporare la sorpresa poco a poco seguendo a ogni in- crocio una direzione sconosciuta9.

La soluzione naturale di inserire nei semafori un indi- catore casuale che dirotti a caso i veicoli in direzioni sempre mutevoli è francamente sconsigliabile, perché obbligherebbe i guidatori a rallentare per recepire il se- gnale imprevedibile fino all’ultimo istante e causerebbe un certo malumore per l’imposizione arbitraria. È dun- que preferibile che la scelta parta dall’interno del veicolo con sufficiente anticipo. A tale scopo tutte le auto do- vranno essere dotate di «casualizzatore», dispositivo in grado di indicare a caso una delle possibili direzioni da intraprendere in corrispondenza di incroci, rotatorie e snodi. La realizzazione del casualizzatore potrebbe in-

(21)

Il piano del traffico 143

10 Per esempio i guidatori della sierra peruviana non accetterebbero mai di prendere una direzione a caso in un incrocio di tre vie ove giacesse ab- bandonato un mazzetto di foglie di coca. spiega infatti Jorge Lira in un sag- gio di antropologia (El cambio de la suerte, edizioni del centro bartolomé de Las casas, cusco 1995) che questo è un segno del destino lasciato da uno sconosciuto e foriero di gravissime conseguenze se non si affronta in

contrare qualche difficoltà perché le direzioni variano in numero e angolazione da incrocio a incrocio richiedendo all’apparenza costosi apparati di tipo elettronico-compu- terizzato; ma in realtà il dispositivo può essere costruito in modo semplicissimo adeguandosi sia alla conforma- zione stradale che alle preferenze dei conducenti. ecco la nostra proposta.

il casualizzatore sarà costruito a mo’ di banderuola e istallato sul cruscotto della vettura. in prossimità di un in- crocio sarà posto manualmente in rotazione da una spinta più o meno decisa secondo l’estro momentaneo del con- ducente, che seguirà poi la direzione più vicina a quella as- sunta dall’indicatore. ci saranno casualizzatori di serie con banderuole ispirate al simbolo della casa automobilistica e casualizzatori personalizzati in accordo alle inclinazioni dei proprietari (la banderuola potrebbe assumere le sem- bianze del calciatore del cuore nell’atto di tirare il rigore risolutivo, o del santo protettore che dispensa la benedi- zione mostrando la via, o di una «pin-up girl» in posa pla- stica nel modello per camion). risolte le questioni tecni- che si porrano alcuni problemi comportamentali. Per rea- lizzare il piano è necessario che ogni automobilista segua le istruzioni con disciplina abbandonando la via preferita per prendere alcune decisioni apparentemente assurde.

confidiamo che nel tempo ciò possa avvenire, pur senza pretendere che siano del tutto abbandonate certe convin- zioni personali10; le quali d’altra parte non danneggeranno

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 143

(22)

modo corretto: «se ci si imbatte in tale ritrovamento conviene girare tre vol- te a sinistra, retrocedere e proseguire in altra direzione. così si contrasta la sfortuna nascosta nella coca. si deve inoltre recitare un credo».

11 il moto dei batteri è stato studiato molto attentamente sia dal punto di vista biologico che da quello matematico. con le parole di Giovanni Pro- di, che ha promosso con passione irriducibile l’incontro tra studiosi di disci- pline diverse: «il batterio come calcolatore deve preferire le soluzioni proba- bilistiche alle soluzioni esatte».

il piano complessivo purché siano distribuite a caso.

ma è mai possibile che nessuno abbia pensato una so- luzione tanto semplice? ebbene, se non l’hanno fatto gli amministratori del traffico l’idea è in uso da tempo im- memorabie presso alcune colonie di viventi che potreb- bero a buon diritto rivendicare interessenze economiche sulla gestione delle reti di calcolatori. si tratta di intere famiglie di batteri che si incontrano di solito nel putridu- me e sono pertanto pochissimo considerati sul piano so- ciale. essi si muovono in un ambiente liquido seguendo tratti rettilinei alternati a giravolte casuali, per dirigersi in media verso zone in cui si concentrano sostanze nutrien- ti; non diversamente da un turista in una città sconosciu- ta che prende direzioni casuali agli incroci, insistendo in una direzione se la zona raggiunta è gradevole11.

Avremmo dovuto cercare un insegnamento nella natu- ra che ha avuto molto più tempo di noi per risolvere i suoi problemi.

(23)

Indice

Prefazione

LA scienzA ALGoritmicA 9

1. La crescita esponenziale

LA VoLPe e iL GAtto 13

2. L’intrattabilità

Le briGAte mULticoLori 25

3. La numerazione

LA bibLiotecA di bAbeLe 39

4. L’autoriferimento

eco e nArciso 51

5. L’indecidibilità

mArtin 61

6. il calcolo parallelo

iL Presidente 75

7. La casualità

iL Processo 89

8. La divinazione

LA bAttAGLiA nAVALe 105

9. il piano del traffico

Un modesto contribUto 123

09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 145

(24)
(25)

edizioni ets

Piazza carrara, 16-19, i-56126 Pisa info@edizioniets.com - www.edizioniets.com Finito di stampare nel mese di ottobre 2010 09 cap. 9_09 cap. 9 14/10/10 17.15 Pagina 147

(26)

Riferimenti

Documenti correlati

 Per gestire un segnale un processo deve dire al kernel che cosa intende fare nel caso riceva tale segnale.  Tipicamente

Annunziato, DIPMAT Universit `a di Salerno - Queste note non sono esaustive ai fini del corso – p.. Annunziato, DIPMAT Universit `a di Salerno - Queste note non sono esaustive ai

Sia dato un grafo completo con 2n + 1 nodi ed archi aventi tutti peso positivo. Si consideri il problema di matching pesato su tale grafo. Dire, MOTIVANDO LE RISPOSTE, se `e vero

Per gli archi forward il valore α ij rappresenta quanto flusso posso ancora inviare lungo l’arco (i, j) ∈ A della rete originaria;. per gli archi backward il valore α ij

guardando l'asse delle ascisse, da destra significa provenendo da destra, e cioè prendendo valori di poco superiori a quelli del punto considerato; da sinistra significa

Si assegnino costi arbitrari a ciascuno dei 6 circuiti della figura 1.26 e si risolva il corrispondente problema di set covering.. Si assegni ad esempio il costo di ogni circuito pari

L’intensità del campo magnetico è uguale al rapporto tra la forza magnetica e l’intensità della corrente per la lunghezza del filo.. L’intensità del campo magnetico si misura

Scrivi il nome delle parti di un poligono:.. Definisci la