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.
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.
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 |
Una volta trovata una formulazione particolare (per un caso specifico) del nostro algoritmo, possiamo cercare di astrarre e ricondurla ad una formulazione generale.
Se indichiamo con A, B, C e D i tempi di percorrenza rispettivi delle 4 persone, il tempo totale di percorrenza può essere calcolato con:
Tempo = A + 3*B + D
Possiamo facilmente verificare come la formula precedente fornisca il risultato trovato prima nel caso sia A=1, B=2, C=3 e D=4 minuti.
E' però importante anche testare l'algoritmo con altri valori, per verificare la sua efficacia. La fase di test è particolarmente importante e critica, in quanto consente di individuare errori logici nella progettazione dell'algoritmo stesso.
Se proviamo ad esempio con A=1, B=4, C=5, D=10, la formula precedente ci fornisce un tempo pari a:
Tempo = A + 3*B + D = 1 + 12 + 10 = 23 minuti
Tuttavia questo tempo non è il più breve che è possibile ottenere. Si consideri infatti quest'altra soluzione in cui A (il più veloce) accompagna sempre tutte le persone dall'altra parte del ponte:
- A accompagna B sul lato 2 (t = 4 min)
- A torna indietro sul lato 1 (t = 1 min)
- A accompagna C sul lato 2 (t = 5 min)
- A torna indietro sul lato 1 (t = 1 min)
- A accompagna D sul lato 2 (t = 10 min)
Il tempo totale in questo caso è 4+1+5+1+10 = 21 minuti, cioè minore del precedente.
Cosa significa questo? Significa che il nostro test ci ha permesso di scoprire che il nostro algoritmo non funziona bene in tutti i casi, cioè non funziona correttamente con tutti i possibili valori di ingresso. Questa è una situazione molto frequente, che richiede la riprogettazione dell'algoritmo stesso.
Senza voler ora approfondire troppo la questione, è possibile dimostrare che se 2B-C > A (come nel nostro ultimo esempio) la soluzione ottimale è la seconda (A accompagna tutti); se la condizione precedente è invece falsa, la soluzione ottimale è la prima proposta.
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
Sito realizzato in base al template offerto da
http://www.graphixmania.it
