PROGRAMMIAMO
Algoritmi - Il problema del ponte
Il problema del ponte

Il problema del ponte è un classico problema di logica. Ci sono quattro persone (per comodità A, B, C e D) che devono attraversare un ponte di assi sospeso su un baratro in piena notte. Il ponte è molto stretto e solo due persone alla volta lo possono attraversare. Inoltre, siccome è notte, coloro che attraversano il ponte hanno bisogno di usare l'unica lanterna a disposizione dei quattro.

A, B, C e D camminano con velocità diverse e dunque attraversano il ponte in tempi diversi: il problema è trovare qual è l'ordine di attraversamento che consente a tutti di attraversare il ponte nel minor tempo possibile.

Il problema del ponte

Si tenga conto che le persone devono attraversare a coppie usando la lanterna e che il più lento di ogni coppia riduce necessariamente la velocità di quello più veloce. Inoltre, una volta arrivati dall'altra parte del ponte, occorre riportare indietro la lanterna, in modo che anche gli altri possano attraversare.

Dal generale al particolare

Una caratteristica della mente umana è quella di ragionare più facilmente in base ad esempi concreti (in cui tutte le variabili e i valori sono stati specificati) che in astratto o in generale. Viceversa, quando si scrive un algoritmo, bisogna proprio cercare una soluzione generale, valida in tutti i casi possibili. Per esempio se vogliamo scrivere un algoritmo per calcolare una media fra numeri, non ci basta che l'algoritmo funzioni con tre numeri ben precisi, ma vogliamo che sia valido con tutte le sequenze possibili di numeri.

Questo contrasto fra la generalità di un problema e la difficoltà della nostra mente di ragionare in termini astratti è uno degli ostacoli maggiori che incontra chi per la prima volta affronta il problema di scrivere algoritmi.

Una possibile soluzione è quella di affrontare e risolvere prima un caso particolare del problema (ovvero, come si dice, conviene partire da un esempio) e poi astrarre la soluzione trovata al caso più generale. Per esempio nel nostro problema del ponte, la difficoltà nel trovare l'algoritmo migliore con quattro tempi di attraversamento non specificati, può essere aggirata facendo un esempio concreto, cioè inventando quattro valori per i tempi di attraversamento di A, B, C e D.

Supponiamo dunque che A sia il più veloce e impieghi 1 solo minuto per attraversare il ponte, che B impieghi 2 minuti, C 3 minuti e D 4 minuti. Siccome le persone devono attraversare a coppie e il tempo di attraversamento è condizionato dal più lento della coppia, la soluzione più sensata è fare attraversare insieme la coppia più veloce (A+B) e quella più lenta (C+D).

Supponiamo che i primi ad attraversare siano A e B. Essi impiegheranno 2 minuti (cioè il tempo di B) per arrivare dall'altra parte del ponte. A questo punto bisogna riportare dall'altra parte la lanterna e questo viene fatto da A, il più veloce della coppia, che impiega 1 minuto per tornare indietro.

A questo punto C e D (i più lenti) attraversano il ponte e impiegano 4 minuti (il tempo di D). Giunti dall'altra parte, cedono la lanterna a B (che era rimasto da solo) e lui la riporta ad A in 2 minuti.

Infine A e B attraversano di nuovo il ponte insieme impiegando 2 minuti. Ci vogliono 11 minuti in totale per completare l'attraversamento, come mostra la tabella seguente:

Tempo trascorsi Lato 1 del ponte Azione Lato 2 del ponte
0 minuti A B C D
2 minuti       C D A e B passano al lato 2 in 2 minuti A B
3 minuti A    C D A torna al lato 1 in 1 minuto    B
7 minuti A C e D attraversano in 4 minuti    B C D
9 minuti A B B torna in 2 minuti       C D
11 minuti A e B attraversano in 2 minuti A B C D

 

Dal particolare al generale

Una volta trovata una formulazione particolare (per un caso specifico) del nostro algoritmo, possiamo cercare di astrarre e ricondurla ad una formulazione generale.

Nel nostro caso la formulazione generale dell'algoritmo del ponte potrebbe essere la seguente:

  1. Le due persone più veloci del gruppo attraversano il ponte insieme e passano al lato 2;
  2. la più veloce fra le persone sul lato 2, torna al lato 1 con la lanterna;
  3. le due persone più lente sul lato 1 attraversano il ponte;
  4. la persona più veloce sul lato 2, torna al lato 1 con la lanterna;
  5. le due persone sul lato1 attraversano il ponte.

Osserviamo che questa formulazione più generale è senz'altro più difficile da comprendere per un essere umano (soprattutto se prima non si è visto un esempio!), ma è sicuramente il modo migliore per istruire una macchina (un computer) all'esecuzione dell'algoritmo.

   

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it