Osserviamo una carta stradale o una mappa dei trasporti pubblici. La si può descrivere come un insieme di tratti stradali che collegano dei punti: questi punti sono tutti snodi, come incroci o interconnessioni. Il tempo di percorrenza di ciascun tratto non è proporzionale alla sua lunghezza: può trattarsi di un’autostrada o di una strada di montagna, e si possono alternare spostamenti a piedi, in treno, in auto, in metropolitana…
Può quindi capitare di dirigersi verso est per prendere un treno veloce che ci porterà più a ovest. Nella carta qui sopra, il percorso più rapido da A a B consiste nel prendere la strada provinciale rossa che li collega oppure l’autostrada blu?
Enumerazione dei percorsi ------------------------
Più in generale, consideriamo i percorsi possibili tra un punto di partenza A e un punto di arrivo B. Per trovare un percorso rapido, una prima idea consiste nell’enumerare tutti i percorsi possibili che partono da A. Si tratta quindi di individuare quelli che conducono a B e, tra questi, uno che sia il più rapido. Per stabilire se questa enumerazione sia possibile, bisogna chiedersi quanti percorsi diversi partano da A (ossia percorsi che differiscano per almeno un tratto). In ogni punto della carta confluiscono almeno 3 tratti. Si parte dall’origine con 3 possibilità, poi in ogni punto incontrato restano almeno 2 tratti possibili per proseguire il percorso. Così, i percorsi che passano per k punti sono almeno 2 *k, e ciascuno può potenzialmente essere il più rapido per raggiungere la destinazione B. Il numero k è sconosciuto. Occorre dunque esplorare i percorsi di 2, 3, 4… tappe. Sebbene sia raro che un percorso con un gran numero di punti sia il più rapido, ciò non è teoricamente impossibile: bisogna quindi considerare tutti i possibili numeri di punti compresi tra 1 e n – 2, dove n* è il numero totale di punti della carta. Questa quantità esponenziale di percorsi è dunque pari a: