Ricerca operativa - algoritmo di Prim

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 paesello.

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" che procede per passi successivi, quindi iterativo, e ad ogni passo definisce un albero di supporto per il sottoinsieme di nodi che sono inclusi nell'insieme di taglio che si analizza alla specifica iterazione. Adotta un criterio di scelta per gli archi a "costo minimo", ossia confronta i costi degli archi e sceglie quello con il costo più basso.

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, ki 00-di taglio e il nodo k-simo di N

L'esempio di fig.1 mostra i parametri descritti sopra.

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.

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:

1. Step 0: Inizialmente S = non ci sono nodi appartenenti ad S, né tanto meno esiste un taglio; visto che l'origine non è predefinita, se ne 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 N.
2. Step 1: Ottenuto il primo taglio, si valutano i costi degli archi uscenti da N diretti ai k-nodi di N; si applica il criterio di scelta min c, che comporta la scelta fra i vari archi di quello a costo minimo e l'inclusione in S del k-esimo nodo terminale, relativo all'arco scelto, con l'assegnazione k : S = k. Attualmente il taglio si è ampliato, si è ampliato S e ovviamente N, che

contengono rispettivamente due nodi. V S diviene−V 2 visto che l’albero di supporto é composto da due nodi della rete,0−si prevedono al piú altre V 2 iterazioni. Il costo totale rispetto a Nviene calcolato mediante la relazione c = c + min c .0tot. k S ,kN i2

Step2: Dopo il primo passo di inizializzazione e il secondo di arricchimentodell’insieme di taglio, la procedura segue quanto fatto nel passo duefacendo attenzione all’insieme di taglio ed al numero di nodi restanti,≡infatti se S V la procedura ha termine in quanto si sono analizzatitutti i nodi e si é giunti ad avere un percorso tra questi a costo minimo.

Come esempio di applicazione dell’algoritmo di Prim, si puó considerarela seguente rete a 7-nodi e 12-archi, la scelta dell’origine ricade sul nodo 1.

Figure 3: Rete con V = 7, r = 1

Di seguito si riportano i passi che svolge l’algoritmo di Prim, prima intabella e poi sulla rete; nelle reti che vengono proposte le frecce

Iterazione	Costi	Assegnazione	N0	S	N
0	{1}	0	S = 1	N = 0	{1,2 8;5(*) S =3 N = 3}
1	0	S = 1	N = 0	{1,3 16;3(*);8;10 S =4 N = 3, 4}
2	0	S = 1	N = 0	{1,4 2*;8;30;14;. . . S =2 N = 3, 4, 2}
3	0	S = 1	N = 0	{1,5 18;16;12(*);14;30 S =5 N = 3, 4, 2, 5}
4	0	S = 1	N = 0	{1,6 4(*);14;30;16 S =7 N = 3, 4, 2, 5, 7}
5	0	S = 1	N = 0	{1,7 16(*);30;26 S =6 N = 3, 4, 2, 5, 7, 6}

Table 1: Tabella dei passi dell'Algoritmo di Prim