Don't take life too seriously: it's just a temporary situation

Bellman (problema di)

Geometria  Problemi 

Nel 1955 Richard E. Bellman propose il seguente problema: vi siete persi in un bosco, di forma e dimensione note; qual è il percorso più breve che vi dia la certezza di uscirne?

 

Il problema è stato risolto solo in alcuni casi particolari.

 

Nel caso di un bosco circolare, il percorso migliore è estremamente semplice: scegliete una direzione a caso e camminate senza mai cambiare direzione: uscirete dal bosco dopo aver percorso, al più, una distanza pari al diametro.

La dimostrazione che non si può far di meglio è elementare: supponiamo che esista un percorso migliore e disegniamolo, ponendo il suo punto di mezzo al centro del cerchio, come mostrato nella figura.

 

Percorso in un cerchio

 

Ogni estremo del percorso, punto di partenza e punto di uscita dal bosco, deve trovarsi nel caso peggiore sul bordo o all’esterno, quindi la parte dal punto centrale a ogni estremo è almeno lunga quanto il raggio e il percorso stesso è almeno lungo quanto il diametro.

Come conseguenza, per ogni figura limitata il percorso non è mai maggiore della massima distanza tra due punti della figura, ma in molti casi è minore.

 

Nel caso di un bosco quadrato, la strategia migliore è la stessa: camminate sempre in linea retta e uscirete dal bosco, nel caso peggiore, dopo aver percorso un’intera diagonale, cioè sqrt(2) volte il lato.

La dimostrazione che questo percorso non è migliorabile è appena più complessa del caso del cerchio.

Per prima cosa osserviamo che il percorso deve toccare due lati adiacenti del quadrato, senza uscirne, come mostrato nella figura seguente, e deve intersecarne almeno un altro.

 

Percorso in un quadrato

 

Infatti, se così non fosse, sarebbe possibile traslare leggermente il percorso stesso, verso destra e in basso, in modo da non fargli intersecare alcun lato e avremmo un punto di partenza dal quale il percorso non porterebbe fuori dal bosco.

In questo caso “toccare” un lato significa arrivare arbitrariamente vicino, ma senza accorgersi d’essere al limitare del bosco, proseguendo quindi nella ricerca di una via d’uscita.

Supponiamo che il percorso intersechi il lato BC; lo si può ruotare lentamente, sempre mantenendolo a contatto con i lati AB e AD, di 90º: al termine dell’operazione dovrà intersecare il lato DC, ma dato che durante tutto lo spostamento deve intersecare BC o CD, che lo spostamento è effettuabile con continuità e che il percorso interseca all’inizio BC e alla fine CD, deve esistere una posizione intermedia nella quale interseca entrambi i lati, non necessariamente in C. In tale posizione il percorso ha un punto in comune con ogni lato e non è difficile dimostrare che qualsiasi linea con tale proprietà deve essere lunga almeno quanto la diagonale. La diagonale è il percorso più breve con questa proprietà.

 

Nel caso di poligoni regolari con un numero pari di lati, la soluzione è sempre un percorso rettilineo: ogni percorso di uscita da un poligono del genere, infatti, porta anche fuori da un rettangolo inscritto, con 4 vertici in comune, quindi deve essere almeno lungo quanto la diagonale di un rettangolo avente per vertici quattro vertici del poligono, che coincide col diametro del cerchio circoscritto, come si vede nella figura seguente, riferita al decagono.

 

Percorso in un decagono regolare

 

Nel caso di poligoni regolari con n lati unitari il percorso migliore, sempre rettilineo, è lungo 1 / sin(π / n) per n pari e 1 / (2 * sin(π / (2 * n))) per n dispari e maggiore di 3.

Sembrerebbe quindi che procedere in linea retta sia sempre la strategia migliore, almeno per figure convesse, ma non è così; in particolare nel caso del il triangolo equilatero A.S. Besicovitch trovò nel 1965 il percorso mostrato in azzurro nella figura seguente.

 

Percorso ottimale in un triangolo regolare

 

I due angoli indicati con αsono uguali e pari a arccos(13 / 14), mentre i tre segmenti hanno la stessa lunghezza, pari a sqrt(21) / 14, in un triangolo di lato unitario. La lunghezza totale del percorso è quindi 3 * sqrt(21) / 14, lievemente inferiore al lato del triangolo, che rappresenta invece il caso peggiore di percorso rettilineo. Non è stato dimostrato che questo sia il percorso migliore.

 

Se il bosco ha la forma di una striscia infinita e non importa da quale parte se ne esce, V.A. Zalgaller dimostrò nel 1961 che il percorso ottimale è quello mostrato in azzurro nella figura seguente.

 

Percorso ottimale in una striscia

 

Il percorso è formato da due parti simmetriche, ciascuna costituita da due segmenti e un arco di cerchio, di raggio pari alla distanza tra C e il segmento AB.

Se la striscia ha larghezza unitaria, la distanza tra A e B è la radice positiva dell’equazione 3x6 + 36x4 + 16x2 – 64 = 0, cioè circa 1.0435901096; e gli angoli φ e ψ sono dati dalle formule Formula per φ e Formula per ψ.

La lunghezza della curva risultante, Formula per la lunghezza della curva, è probabilmente un numero trascendente, ma nessuno l’ha dimostrato.

 

Da questa soluzione e da quella per il quadrato si ricava il percorso migliore per il rettangolo: è il minimo tra la diagonale del rettangolo e il percorso ottimale nel caso della striscia, ovvero, se il rettangolo ha un lato unitario e l’altro di lunghezza r > 1, è un percorso rettilineo, con lunghezza, nel caso peggiore, uguale alla diagonale del rettangolo ossia sqrt(1 + r^2), se r < sqrt(z^2 – 1), col percorso utilizzato per la striscia infinita altrimenti. La prima dimostrazione completa si deve a J. Schaer e J.E. Wetzel a nel 1972.

 

Se si sa di essere esattamente al centro della striscia, sempre di larghezza unitaria, il percorso migliore è probabilmente quello mostrato in azzurro nella figura seguente, formato da un segmento di lunghezza sqrt(3) / 3, seguito, dopo una svolta di 120°, da un altro di lunghezza sqrt(3) / 6, poi da un arco di cerchio di 30º con raggio 1 / 2, centrato sul punto di partenza, e infine da un altro segmento di lunghezza 1 / 2, per una lunghezza totale pari a sqrt(3) / 2 + π / 6 + 1 / 2.

 

Percorso ottimale in una striscia, partendo dal centro

 

 

A prima vista il fatto che quando ci si trova nella posizione peggiore, cioè lungo la metà della striscia, il percorso sia più corto può essere sorprendente. La spiegazione sta nel fatto che si sa di trovarsi al centro e questa preziosa informazione può essere sfruttata per ridurre la lunghezza del percorso. Il percorso migliore nel caso generale, dopotutto, porta fuori dai guai a partire da qualsiasi punto, incluso il centro.

 

Nel caso di un semipiano, supponendo unitaria (e nota) la distanza dal margine, ma non la direzione, il percorso migliore, dimostrato tale da H. Joris nel 1980, è costituito da un tratto rettilineo lungo 2 * sqrt(3) / 3, in una direzione qualsiasi, seguito da una svolta di 120º, percorrendo per sqrt(3) / 3 una tangente alla circonferenza di raggio 1, centrata sul punto di partenza. Si procede quindi lungo questa circonferenza per 210º e si termina con un percorso rettilineo unitario lungo la tangente alla circonferenza, per raggiungere il margine, indicato in rosso nella figura seguente, dopo un percorso lungo nel caso peggiore sqrt(3) + 7 * π / 6 + 1, ben poco di più della lunghezza della circonferenza di raggio 1.

 

Percorso ottimale in un semipiano

 

Se la distanza iniziale dal margine non è nota, il percorso migliore è molto probabilmente una spirale logaritmica, secondo la congettura di Baeza-Yates, Culberson e Rawlins (1988). Finch ha recentemente ricavato l’equazione (approssimata) r(θ) = e0.212469559θ, con lunghezza circa 13.811135179 se la distanza iniziale dal margine del bosco è 1.

 

La ricerca del percorso per uscire dal bosco nel minor tempo in media è in generale molto più complessa; sono note soluzioni approssimate nel caso del bosco infinito, con distanza dal margine nota, e della striscia.

Bibliografia

  • Bellman, R.;  "Minimization Problem" in Bulletin of American Mathematical Society, n. 62, 1956.
  • Bellman, R.;  Dynamic Programming, Princeton University Press, 1957.
  • Besicovitch, A.S.;  "On arcs that cannot be covered by an open equilateral triangle of side 1" in Mathematical Gazette, n. 49, 1965.
  • Tóth, G.;  "Bellman’s Problem" in Középiskolai Matematikai Lapok, n. 65, 1982.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.