Algoritmo di Prim: differenze tra le versioni

Versione delle 13:41, 28 nov 2013

Versione attuale delle 22:28, 17 mar 2025

(29 versioni intermedie di 21 utenti non mostrate)

Riga 1:

{{Algoritmo

L''''algoritmo di Pime''' è un [[algoritmo]] ottimo utilizzato in [[teoria dei grafi]], [[informatica]] e [[ricerca operativa]] per determinare gli [[Albero_ricoprente#Albero_ricoprente_minimo|alberi di supporto minimi]] di un grafo non orientato e con pesi non negativi.

|classe = [[Albero ricoprente minimo]]

|immagine = PrimAlgDemo.gif

|didascalia = Esecuzione dell'algoritmo di Prim

|struttura dati = [[Grafo]]

|tempo = <math>O(|E| + |V| \log|V|)</math>

}}

L''''algoritmo di PimePrim''' è un [[algoritmo]] ottimo utilizzato in [[teoria dei grafi]], [[informatica]] e [[ricerca operativa]] per determinare gli [[Albero_ricoprente#Albero_ricoprente_minimoAlbero ricoprente minimo|alberi di supporto minimi]] di un grafo non orientato e con pesi non negativi.

== Storia ==

Fu originariamente sviluppato nel 1930 dal matematico ceco [[Vojtěch Jarník]] e successivamente, nel 1957, fu indipendentemente sviluppato dall'informatico [[Robert C. PimePrim]]. Nel 1959 venne riscoperto da [[Edsger Dijkstra]]. A causa dei contributi di questi studiosi lo si trova spesso citato come algoritmo DJP (Dijkstra, Jarnìk, PimePrim), Algoritmo di Jarnik o algoritmo di PimePrim-Jarnik.

== Caratteristiche ==

Le caratteristiche dell'algoritmo di PimePrim possono essere sintetizzate nei seguenti punti:

* [[Algoritmo greedy]]: perché valuta di volta in volta le soluzioni localmente migliori senza mettere in discussione le scelte precedenti.

* [[Algoritmo esatto]]: perché fornisce una soluzione precisa per ogni istanza del problema senza effettuare arrotondamenti o imprecisioni di altra natura.

* [[Algoritmo ottimo]]: perché presenta la soluzione migliore (o, a parità di qualità di soluzioni, una tra le soluzioni migliori).

== Descrizione ==

Per la descrizione dell'algoritmo si assume che il grafo sia rappresentato utilizzando una [[struttura dati]] detta [[Grafo#Implementazioni_dei_grafiLista di adiacenza|lista delle adiacenze]] che è solitamente realizzata con un [[array]] cui ogni posizione corrisponde un vertice. Ogni elemento dell'array punta ad una generica [[lista concatenata]] che conterrà tutti i vertici adiacenti al vertice considerato. Inoltre si assume che ogni vertice ''v'' abbia i campi dato ''chiave[v]'' e ''π[v]'', rispettivamente il valore associato al vertice e il puntatore al padre di quest'ultimo all'interno dell'MST.

#Inizialmente si pongono tutti i campi ''chiave[v]'' a +∞ e tutti i campi ''π[v]'' a NIL.

Line 26 ⟶ 33:

Effettuata la scelta del ramo dal passo precedente includerò in S il vertice collegato al vertice di partenza dal ramo appena scelto.

Ad ogni vertice che includo in S anche i rami incidenti di quel vertice si aggiungeranno ai rami tra cui sceglierò quello meno costoso che collega ad un vertice non appartenente ad S.

L'algoritmo termina quando la [[cardinalità]] (numerosità) di S è pari a quella di GV (ciò vale solo se il grafo è connesso).

==Analisi della complessità==

La complessità dell'algoritmo di PimePrim dipende dall'implementazione della struttura dati ausiliaria utilizzata per contenere i nodi al passo (3).

Se implementata con una [[coda di priorità]] e assumendo di complessità costante il test di presenza o meno nella coda il tempo totale di esecuzione dell'algoritmo è di <math>O(V\cdot\log{V} + E\cdot\log{V})</math> dove <math>V\cdot\log{V}</math> è il tempo necessario per le operazioni di estrazione dalla coda ed <math>E\cdot\log{V}</math> è il tempo necessario per scorrere le liste delle adiacenze e compiere l'assegnazione di cui al passo (6).

Quindi il tempo totale di esecuzione dell'algoritmo di PimePrim è <math>O(E\cdot\log{V})</math>.

Se la coda con priorità è realizzata con [[Heap di Fibonacci]] il tempo di esecuzione può essere ulteriormente migliorato. Infatti, il tempo di insert e decreaseKey si riduce <math>O(1)</math>, ammortizzato dalle deleteKey con costo <math>O(\log{V})</math>.

L'implementazione dell'algoritmo di Prim con Fibonacci Heap è la più efficiente ottenibile, infatti il costo di esecuzione è <math>O(E + V\cdot\log{V})</math>. Per averne conferma, si consideri un grafo completamente connesso (<math>E = O(V^2)</math>) e si confrontino i tempi di esecuzione.

L'algoritmo di Prim è un perfetto esempio di come strutture dati efficienti consentano di risolvere efficientemente un problema.

== Esempio ==

Line 38 ⟶ 51:

{| border=1 cellspacing=2 cellpadding=5 class="wikitable"

! | Immagine

! | UNodi processati

! width="100" | Lati Disponibili

! | VNodi \nella Ucoda

! | Descrizione

|-

Line 52 ⟶ 65:

*in azzurro verrà indicata la scelta corrente da aggiungere alla soluzione parziale.

*in nero verranno indicati i lati che non rientrano nella soluzione o che non vengono considerati in quanto collegati a nodi non ancora raggiungibili dall'attuale soluzione o in quanto collegati a nodi già raggiunti da altri lati con costo inferiore.

|-

Line 83 ⟶ 95:

|Tutti i vertici sono stati selezionati e l'albero di supporto a costo minimo è mostrato in verde. In questo caso, il costo è 39.

|}

== Pseudo-codice ==

Di seguito una rappresentazione in pseudo-codice dell'algoritmo di Prim.<ref>{{Cita web|lingua=en|url=https://www.freecodecamp.org/news/prims-algorithm-explained-with-pseudocode/|titolo=Prim's Algorithm – Explained with a Pseudocode Example|sito=freeCodeCamp.org|data=2023-02-14|accesso=2025-02-25}}</ref><ref>{{Cita web|url=https://www.programiz.com/dsa/prim-algorithm|titolo=Prim's Algorithm|sito=www.programiz.com|accesso=2025-02-25}}</ref><syntaxhighlight line="1">

Algoritmo Prim(G, s):

// G = (V, E) è un grafo non orientato pesato

// s è il nodo di partenza

// Inizializza: per ogni nodo v in V, setta una chiave (costo minimo di collegamento) e un genitore

per ogni v in V:

key[v] ← ∞

parent[v] ← NIL

key[s] ← 0

// Q è l'insieme dei nodi non ancora inclusi nell'albero MST

Q ← V

mentre Q non è vuoto:

// Estrae il nodo u in Q con chiave minima

u ← estrai_minimo(Q)

// Per ogni nodo adiacente v a u

per ogni v in adiacenti(u):

// Se v è ancora in Q e il peso dell'arco (u, v) è minore della chiave attuale di v

se v ∈ Q e peso(u, v) < key[v]:

parent[v] ← u

key[v] ← peso(u, v)

// Alla fine parent[] definisce l'albero ricoprente minimo (MST)

ritorna parent

</syntaxhighlight>

==Applicazioni==

Line 88 ⟶ 131:

== Varie ==

* Può essere utilizzato anche su grafi orientati e con peso non negativo ma in questa situazione perde la caratteristica di essere un algoritmo ottimo. Per queste tipologie di grafi, l'algoritmo di PimePrim presenta una soluzione ma non è quella ottima.

==Note==

<references/>

==Bibliografia==

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald Rivest|Ronald L. Rivest]], [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Seconda Edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sezione 23.2: The algorithms of Kruskal and PimePrim, pp.567–574. Edizione Italiana da pag. 480 a pag. 490.

* {{Cita libro

| cognome = Tarjan

| nome = Robert E.

| titolo = Data structures and network algorithms

| url = https://archive.org/details/datastructuresne0000tarj

| editore = Society for Industrial and Applied Mathematics

| città = Philadelphia

| anno = 1983

| idisbn =ISBN 978-08987118750-89871-187-5

| oclc = 10120539

}}

Line 109 ⟶ 154:

== Altri progetti ==

{{interprogetto|commonspreposizione=Category:Primsull's Algorithm}}

{{Portale|informatica|matematica}}

[[Categoria:Algoritmi di ottimizzazione|Prim]]

[[Categoria:Ottimizzazione|PrimAlberi ricoprenti]]

[[Categoria:Teoria dei grafi]]

[[Categoria:Ricerca operativa]]

[[Categoria:TeoriaAlgoritmi deisui grafi|Prim]]