Ricerca operativa - algoritmo di Prim

1

L’algoritmo di Prim

Il problema che si pone spesso un progettista di reti é come portare la

corrente elettrica, la connessione ADSL o soltanto la linea telefonica, a costo

minimo a tutti gli abitanti di una cittá, una metropoli o solo un piccolo pae-

sello.

Sviscerando il problema con la teoria dei grafi, si intuisce che si tratta di

un problema di minimo percorso su una rete di nodi che rappresentano le

abitazioni, senza avere una origine definita, sapendo soltanto che bisogna

toccare necessariamente tutti i nodi della rete.

L’Algoritmo di Prim ci viene incontro dandoci la risoluzione al problema;

infatti si tratta di un algoritmo “greedy(ingordo)” che procede per passi suc-

cessivi, quindi iterativo, e ad ogni passo definisce un albero di supporto per il

sottoinsieme di nodi che sono inlcusi nell’insieme di taglio che si analizza alla

specifica iterazione. Adotta un criterio di scelta per gli archi a “costo min-

imo”, ossia confronta i costi degli archi uscenti dal taglio attuale, scegliendo

fra tutti quello che presenta il costo minimo.

Definiamo i seguenti parametri ausiliari all’analisi della rete:

V : Insieme dei nodi della rete in analisi

−

S: Insieme dei nodi appartenenti al k simo taglio

0 −

N : Albero di supporto definito dal taglio k simo

00 −

N : Dato il k simo taglio, é la restante parte della rete

−

V S: I restanti nodi da analizzare

c : Costo dell’arco che congiunge il nodo i−simo appartenente all’insieme

S ,k

i 00

−

di taglio e il nodo k simo di N

l’esempio di fig.1 mostra i parametri descritti sopra.

1 c Paolo Maresca 1

Figure 1: Parametri ultizzati nella analisi della Rete

Una generica rete da analizzare presenta n-nodi, si ha allora che V = n;

n−2

per “A. Cayley(1889)” per una rete con n-nodi si possono avere n -alberi

−

di supporto ad n 1-lati, come viene mostrato nella fig.2.

Figure 2: Alberi di Supporto e Lati per V = n = 3

Si puó operare l’analisi di una rete scandendo in passi la procedura di

Prim, in particolare quando il fine dell’analisi é trovare un percorso tra tutti

i nodi della rete che sia a costo minimo; si puó suddividere la procedura

dell’algoritmo nei seguenti passi:

{0},

Step0: Inizialmente S = non ci sono nodi appartenenti ad S, ne tan-

tomeno esiste un taglio; visto che l’origine non é predefinita, se ne

{r},

sceglie una per esempio r e si produce l’assegnazione r : S = si

ottiene cosı́ un primo taglio per la rete e un primo componente per

0

N . 0

Step1: Ottenuto il primo taglio, si valutano i costi degli archi uscenti da