Primi elementi della teoria dei grafi

Grafi pesati e il problema del commesso viaggiatore

In molte situazioni reali si utilizzano grafi in cui a ogni spigolo è associato un numero. Ad esempio, in una mappa stradale ad ogni spigolo che rappresenta la strada di collegamento tra due località è associata la distanza tra queste due località.

Ad esempio, a una società di trasporto che vuole minimizzare i tempi o i costi potrebbe costruire grafi in cui ad ogni spigolo è associato il tempo di percorrenza, oppure il costo del trasporto. Quando ad ogni spigolo è associato un numero detto peso, si parla di grafi pesati o ponderati.

Un circuito hamiltoniano rappresenta la soluzione ideale per risolvere alcuni problemi reali detti il problema del commesso viaggiatore che può essere sintetizzato cosí: un rappresentante di commercio parte da casa, e vuole effettuare il percorso più breve che gli consente di visitare uno dopo l'altro alcuni clienti che vivono in luoghi diversi e di tornare a casa. Naturalmente, ha con sè una mappa stradale con le indicazioni delle distanze. Supponiamo che il rappresentante abita nella città A e debba visitare tre clienti che sono rispettivamente nelle città B, C e D e tornare in A avendo a disposizione il seguente grafo pesato.

Qual è il percorso più breve? Il problema richiede quindi, di trovare un circuito hamiltoniano del grafo di peso minimo. Vediamo una possibile strategia. Il rappresentante partendo da A ha tre alternative: andare in B distante 50 km, andare in C distante 35 km, andare in D distante 15 km. Supponiamo che ogni volta che c'è una alternativa scelga sempre la città più vicina che non ha ancora visitato e quindi scelga di andare in D. Dalla città D ha di nuovo tre possibili scelte: andare in C che dista 32 km oppure andare in B con due strade alternative una di 80 km e l'altra di 25 km. Sceglie di andare in B percorrendo la strada più corta di 25 km. Ora, da B deve per forza andare in C percorrendo 20 km e poi tornare in A percorrendo 35 km.

Con questa strategia il rappresentante ha percorso 95 km che è tra tutti i possibili circuiti hamiltoniani quello con il chilometraggio minimo. Questo modo di procedere è detto algoritmo dell'avaro perchè davanti ad ogni alternativa si sceglie sempre quella più economica. Purtroppo questo procedimento non sempre permette di ottenere il percorso minimo anche in situazioni semplici. Ad esempio, applicando questo metodo al seguente grafo non si ottiene il percorso più breve.

Con la scelta del nodo più vicino si hanno due possibili percorsi A-B-D-C-A e A-D-B-C-A entrambi lunghi 90 km. Invece, il percorso più breve è A-B-C-D-A che è lungo 78 km. Se pensate che problemi di questo tipo possono essere risolti impiegando poco tempo, vi sbaglite perchè non è cosí. Il numero dei possibili circuiti hamiltoniani da analizzare cresce vertiginosamente anche con grafi non molto complessi e ciò rende questi problemi non risolvibili in un tempo ragionevole. Ad esempio, analizziamo ancora un caso semplice per poter poi generalizzare sul numero dei possibili circuiti che bisogna confrontare. Supponiamo che il grafo abbia 5 vertici di cui A rappresenta la casa del rappresentante e B, C, D, E i suoi clienti e il grafo sia completo. Calcoliamo il numero dei possibili circuiti hamiltoniani. Uscendo da casa il rappresentante ha quattro possibilità nel scegliere il primo cliente:

A-B, A-C, A-D, A-E

per ognuna ha poi tre possibilità per scegliere il secondo cliente:

A-B-C, A-B-D, A-B-E

A-C-B, A-C-D, A-C-E

A-D-B, A-D-C, A-D-E

A-E-B, A-E-C, A-E-D

e per ognuna ha poi due possibilità per scegliere il terzo cliente:

A-B-C-D, A-B-C-E, A-B-D-C, A-B-D-E,

A-B-E-C, A-B-E-D, A-C-B-D, A-C-B-E

A-C-D-B, A-C-D-E, A-C-E-D, A-C-E-B,

A-D-B-C, A-D-B-E, A-D-C-B, A-D-C-E

A-D-E-B, A-D-E-C, A-E-B-C, A-E-B-D,

A-E-C-D, A-E-C-B, A-E-D-B, A-E-D-C

e infine per ognuna ha poi una sola possibilità per tornare a casa:

A-B-C-D-A, A-B-C-E-A, A-B-D-C-A, A-B-D-E-A,

A-B-E-C-A, A-B-E-D-A, A-C-B-D-A, A-C-B-E-A

A-C-D-B-A, A-C-D-E-A, A-C-E-D-A, A-C-E-B-A,

A-D-B-C-A, A-D-B-E-A,A-D-C-B-A, A-D-C-E-A

A-D-E-B-A, A-D-E-C-A, A-E-B-C-A, A-E-B-D-A,

A-E-C-D-A, A-E-C-B-A,A-E-D-B-A, A-E-D-C-A

In totale ha quindi 24 possibili circuiti hamiltoniani e cioè:

4!=4x3x2x1=24

n!=nx(n-1)x(n-2)x(n-3)...1

Ora, immaginiamo che il nostro rappresentante abbia solo 14 clienti. Quanti sono i possibili circuiti hamiltoniani da analizzare?

14!=14x13x12x11x10x9x8x7x6x5x4x3x2x1=87.178.291.200

Quanto tempo accorrerà al nostro povero rappresentante per trovare tra tutti questi circuiti quello di peso minore? E' come cercare un ago nel pagliaio.

Attualmente si possono utilizzare efficaci algoritmi che implementati su cumputer veloci forniscono in un tempo accettabile una soluzione quasi ottimale di questi problemi. In altre parole, non trovano la soluzione effettiva del problema ma una soluzione ottimale che è quella più vicina possibile alla soluzione effettiva. Questo compromesso permette di ridurre enormemente il tempo di ricerca e quindi di fornire una risposta accettabile in un tempo ragionevole.

L'importanza del problema del commesso viaggiatore deriva dal fatto che molti problemi reali (esplorazione di ambienti, percorsi di pulizia, ottimizzazione di sequenze di lavorazione, ecc.) sono analoghi e possono essere modellati come un problema del commesso viaggiatore o una sua variante.