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 (ingordo)” 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 uscenti dal taglio attuale, scegliendo fra tutti quello che presenta il costo minimo.

Parametri ausiliari

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
• N₀: Albero di supporto definito dal taglio k simo
• N₀₀: Dato il k simo taglio, è la restante parte della rete
• V − S: I restanti nodi da analizzare
• c_i,k: Costo dell’arco che congiunge il nodo i-simo appartenente all’insieme S 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 utilizzati nella analisi della Rete

Una generica rete da analizzare presenta n-nodi, si ha allora che V = n; 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:

Step0: Inizialmente S = {0}, non ci sono nodi appartenenti ad S, né tantomeno esiste un taglio; visto che l’origine non è predefinita, se ne sceglie una per esempio r e si produce l’assegnazione r: S = {r}, si ottiene così un primo taglio per la rete e un primo componente per N₀.

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