Home > master > Algoritmi e struttura dati

Algoritmi e struttura dati

23 novembre 2013

Problemi computazionali
L’informatica è la scienza che studia la risoluzione di problemi per mezzo di algoritmi, ossia una sequenza di passi che consentono di risolvere il problema.

Questo comporta che:

  • il soggetto che dovrà eseguirli dovrà essere in grado di comprenderli ed eseguirli
  • i dati in ingresso devono essere usati dagli algoritmi per ottenere il risultato
  • l’algoritmo è composto da un insieme di passi finiti, altrimenti non si tratta di un algoritmo di risoluzione.
  • l’esecuzione deve prevedere un tempo finito


Possiamo definire un algoritmo come una funzione che in base a dei dati in ingresso ottiene dei dati in uscita f:I -> O
Abbiamo diversi tipi di problemi:

  • Problemi di decisione: sono quei problemi per cui la soluzione è di 2 tipi: vero(True) o falso (False), quindi abbiamo I->{T,F}
  • Problemi di ricerca: sono quei problemi che cercano di risolvere un problema in base a delle condizioni, per esempio un ordinamento di numeri
  • Problemi di ottimizzazione: sono quei problemi che cercano di trovare una soluzione migliore rispetto a quella esistente (in base a delle metriche), per esempio calcolare il percorso più breve tra 2 punti.

Le domande da porci a fronte di un problema sono:

  1. esiste un algoritmo che possa risolverlo?
  2. a fronte di più algoritmi in grado di risolverlo, qual’è l’algoritmo migliore?
  3. e’ possibile ottimizzarlo?

Supponendo di avere limiti in termini di tempo e di memoria, è importante che un algoritmo abbia un termine e non entri in un ciclo infinito ma ciò non è semplice e non è sempre possibile stabilire a priori che l’esecuzione avrà una fine pertanto si parla di problemi indecidibili.
Tra i problemi decidibili, ossia quei problemi che presentano una soluzione, si presentano anche quelli per i quali esistono delle soluzioni ma che richiedono troppo tempo e memoria, per esempio nel problema delle Torre di Hanoi, il numero delle mosse al fine di ottenere la soluzione è rappresentata da una formula esponenziale: 2^(numero di piatti da spostare) e ciò richiede un tempo decisamente insostenibile se abbiamo molti piatti.
In questo caso l’eventuale miglioramento dell’algoritmo dovrà seguire lo stesso fattore del problema, nel senso che essendo di fronte ad un problema esponenziale un miglioramento moltiplicativo sarà facilmente vanificato e non porterà alcun beneficio mentre invece un miglioramento polinomiale determina una soluzione sostenibile e praticabile.
Questo determina che i problemi decidibili possono essere distinti in:

  • problemi trattabili: se esiste almeno un algoritmo risolutivo polinomiale
  • problemi intrattabili: se non esiste un algoritmo polinomiale.

Rappresentazione e dimensione dei dati
I dati possono essere rappresentati utilizzando delle sequenze di bit (per esempio 8 o 16 bit) che consentono di esprimere numeri, caratteri ed altri simboli e segni speciali. Per codificare un numero in base ad una sequenza di bit, è possibile seguire la regola di moltiplicare ogni bit per una potenza crescente di 2 partendo dal bit meno significativo.
Quindi per rappresentare un numero utilizzando la sequenza binaria

  • 0101 =
  • 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 =
  • 0*8 + 1*4 + 0*2 + 1*1 =
  • 0 + 4 + 0 + 1 = 5

Mentre invece per rappresentare un numero razionale si utilizza:

  • il primo bit: per indicare il segno
  • un certo numero di bit per indicare l’esponente
  • il resto dei bit per indicare la mantissa

La dimensione dei dati è costituita dalla quantità di bit che si utilizzano per indicare il dato

Complessità computazionale
I moderni calcolatori sono basati sull’idea dello scienziato ungherese John Von Neumann che negli anni 50 propose di mantenere nella memoria del computer sia i programmi che i dati da analizzare, espressi come sequenza binaria.
Il processore contiene una unita centrale e 2 registri, il primo registro serve per mantenere l’istruzione da eseguire mentre il secondo registro contiene il risultato ottenuto, frutto di una serie di operazioni (aritmetiche, confronto, logiche, trasferimento, controllo).
La valutazione di un algoritmo è effettuata in termini di tempo (quantità di istruzioni eseguite) e di spazio (celle di memoria impiegate). Solitamente si cerca di minimizzare il tempo di esecuzione poichè lo spazio è riutilizzabile mentre il tempo è irreversibile.
Il costo necessario (tempo e spazio) per l’esecuzione di un’operazione è costituita dal costo delle istruzioni sommato al costo del costrutto.
Si può schematizzare in:

  • costrutto decisionale: il costo computazionale è dovuto al costo della condizione + il costo del blocco che verrà eseguito ma non potendolo sapere in anticipo allora si considera il maggiore dei costi dei 2 blocchi:

if(condizione){blocco1} else {blocco2}
costo(condizione) + costo(max{costo(blocco1) or costo(blocco2)}

  • costrutto iterativo: il costo computazionale è dovuto alla sommatoria dei costi del blocco per tutte le volte che viene eseguito.

for(i=0;i<m;i++){blocco}
sommatoria i=0->m-1 di costo(blocco)

  • In generale il costo di una funzione è dato dal costo degli argomenti più quello del corpo della funzione

funzione(argomento){blocco}
costo(argomento) + costo(blocco)

Limiti superiori e inferiori
Dato un problema decidibile e trattabile per il quale è stata individuata almeno una soluzione, questa viene definita come limite superiore, poichè esiste un algoritmo che risolve il problema questi non potrà essere più complesso dell’algoritmo ed il costo di esecuzione sarà O(g(n))
Mentre invece il limite inferiore è dato dalla complessità minima che ogni algoritmo deve presentare per risolvere il problema ed avrà un costo di esecuzione W(g(n))

Sequenze lineari
Una sequenze lineare è un insieme finito di elementi disposti consecutivamente in cui ognuno ha associato un indice di posizione in modo univoco. Per esempio in una sequenza di n elementi di tipo A abbiamo: a1, a2,… a(n-1) in cui l’indice è rappresentato da j e risulta compreso tra (0<j<n-1). L’indice consente di indicare l’elemento di interesse.

L’accesso all’elemento può avvenire in 2 modalità: accesso diretto ed accesso sequenziale.

  1. con l’accesso diretto: l’accesso ad un elemento avviene in modo diretto senza dover attraversare la sequenza, pertanto il tempo è identico per accedere a qualunque elemento, per esempio un array.
  2. con l’accesso sequenziale: l’accesso ad un elemento richiede l’attraversamento della sequenza partendo da un estremo, pertanto il tempo dipende dall’elemento interessato, per esempio una lista.

Differenze:

  • nel caso di un array: questi è costituito da una sequenza di elementi contigui. Per l’accesso all’indice dell’elemento di interesse occorre semplicemente sommare all’indirizzo di memoria del primo elemento tanti byte corrispondente all’indice dell’elemento.
  • nel caso di una lista: gli elementi vengono collezionati a run-time pertanto non sono contigui quindi ogni elemento mantiene la referenza all’elemento successivo. Per l’accesso all’indice dell’elemento di interesse occorre effettuare tanti passi corrispondenti all’indice dell’elemento.

Nelle liste semplici:

  • le liste semplici mantengono un riferimento solo all’elemento successivo
  • la cancellazione di un elemento comporta la modifica della referenza dell’elemento precedente
  • nel caso di inserimento occorre modificare il riferimento dell’elemento precedente ed aggiungere il nuovo riferimento nell’elemento inserito

Nelle liste doppie:

  • le liste doppie mantengono un riferimento anche all’elemento precedente.
  • la cancellazione di un elemento comporta la modifica della referenza nell’elemento precedente e successivo, ma il vantaggio consiste nel fatto che è possibile navigare la lista in entrambe le direzioni.
  • nel caso di inserimento occorre memorizzare nel nuovo elemento da inserire, i riferimenti anteriori e posteriori dell’elemento sostituito.

Nelle liste circolari:

  • l’ultimo elemento mantiene una referenza al primo elemento, ma a parte questa particolarità, si comportano come delle liste semplici.

Le pile rappresentano delle liste che consentono l’accesso a partire dall’ultimo elemento, come i vassoi di un self-service con modalita LIFO. Le operazioni possibili sono 3: inserimento(push), estrazione(pop) e restituzione(top). In alcuni casi abbiamo l’operazione empty per verificare se la lista è vuota.

Le code rappresentano delle liste che consentono l’accesso a partire dal primo e dall’ultimo elemento, come la fila alla posta con modalità FIFO. Le operazioni possobili sono: inserimento(enqueue) alla fine della coda, estrazione(dequeue) all’inizio della coda, restituzione(first) del primo elemento. Anche in questo caso abbiamo l’operazione empty per verificare se la coda è vuota.

Ricerca
La ricerca consiste nel cercare in una sequenza di n elementi, l’esistenza di un elemento che abbia il valore uguale alla chiave k cercata. Se gli elementi non sono ordinati allora occorrerà effettuare una ricerca sequenziale per scorrerli tutti O(n).

  • Nel caso di un array, se viene trovata la chiave, la ricerca ritornerà l’indice dell’elemento che contiene la chiave altrimenti ritornerà un indice -1, ossia una convenzione per definire nessun risultato.
  • Nel caso di una lista, se viene trovata la chiave, la ricerca ritornerà l’elemento che contiene la chiave.

Ricerca binaria
Se la sequenza degli elementi è ordinata sarà possibile eseguire una ricerca binaria o dicotomica che presenta un tempo di esecuzione ridotto O(log n).
Per cercare una chiave,si effettua una ricerca partendo dall’indice centrale, ed a seconda che il valore riscontrato sia inferiore o superiore, si effettuerà una nuova ricerca nel blocco precedente o successivo e cosi via fino a completamento.
Ad ogni iterazione “i” di ricerca il blocco viene dimezzato: n/2, n/4, n/8, n/16 pertanto in questo modo n/2^i, quindi la ricerca richiede O(log n) passi.

Quindi O(log n) rappresenta il limite superiore della ricerca binaria.

A fronte di ogni iterazione di ricerca, abbiamo 3 possibilità, ossia che la chiave sia < = > al valore, quindi con “t” iterazioni abbiamo 3^t situazioni.
Poichè dobbiamo garantire n+1 iterazioni per completare la ricerca, abbiamo che

3^t >= n+1

quindi

t >= log base3(n+1) iterazioni (confronti) ossia W(log n)

che rappresenta il nostro limite inferiore quindi ricaviamo che l’algoritmo di ricerca binaria è ottimo in quanto il limite superiore ed inferiore corrispondono.

Usando il paradigma del Divide et impera, è possibile suddividere un problema complesso in problemi semplici e provare a risolverli. Le fasi sono:

  • Decomposizione: suddividere il problema in sotto-problemi che utilizzino meno dati.
  • Ricorsione:risolvere i sotto-problemi
  • Ricombinazione: combinare le soluzione dei sotto-problemi per ottenere la soluzione complessiva.

Secondo questo paradigma dobbiamo considerare che:

  • la decomposizione e la ricombinazione richiedono un costo c in termini di tempo che indichiamo con f(n)
  • la ricorsione comporta l’invocazione di n/beta gruppi che richiedono alfa chiamate

L’equazione di ricorrenza ci indica la funzione che determina la ricerca.
Se abbiamo solo 1 elemento nella sequenza allora le operazioni da effettuare sono:
T(n)=c se n=1
T(n)=T(n/2)+c
ossia per una ricerca su un array di n elementi:
T(n)=O(1) se n<=0
T(n)=alfa T(n/beta)+f(n)

Ordinamento
Ordinamento per selezione
Composto da 2 cicli, esterno ed interno con costo = n^2. Algoritmo cieco con doppio ciclo.

  1. alla prima iterazione dell’algoritmo verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione;
  2. alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme ossia l’elemento più piccolo dell’insieme “ridotto” costituito dagli elementi {a2,a3, . . . ,an} e sarà scambiato con l’elemento che occupa la seconda posizione
  3. e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.


1. A = (4, 2,1,3)! A = (1 | 2, 4,3)
2. A = (1 | 2, 4,3)! A = (1,2 | 4,3)
3. A = (1, 2, | 4,3)! A = (1, 2,3 | 4)
4. A = (1, 2,3 | 4)! A = (1, 2, 3,4)

La complessità migliore, media e migliore sarà sempre O(n2)

Ordinamento per inserimento
Composto da 2 cicli, esterno ed interno con costo = n^2. Algoritmo NON cieco che sfrutta eventuali ordinamenti con doppio ciclo.
Consiste nel collocare uno dopo l’altro gli elementi dell’insieme nella posizione corretta del sottoinsieme già ordinato costituito dagli elementi a1,a2, . . . ,ai-1. Molto simile al modo in cui ordiniamo un mazzo di carte.

  1. partiamo da una carta e la inseriamo prima o dopo un blocco iniziale
  2. proseguimo in questo modo per tutte le altre carte

1. A = {5 | 2,3,1,4}! A = {2,5 | 3, 1,4}
2. A = {2,5 | 3, 1,4}! A = {2,3,5 | 1,4}
3. A = {2,3,5 | 1,4}! A = {1, 2,3,5 | 4}
4. A = {1,2, 3,5 | 4}! A = {1,2, 3,4,5}

La complessità migliore sarà O(n) mentre quella media e peggiore sarà O(n2)

Ordinamento per fusione
In questo algoritmo il costo non è esponenziale ma logaritmico, pertanto è più efficente. L’ordinamento della sequenza viene realizzato applicando il principio del Divide et impera. Tutti gli elementi vengono separati e confrontati con l’elemento contiguo al fine di determinare il minore. Il confronto di blocchi di elementi avviene confrontando parallelamente gli elementi sulla sinistra.

  • Decomposizione: un blocco di numeri viene diviso 2 parti, poi ognuno di esse in altre 2 parti ecc fino ad ottenere n blocchi di 2 elementi
  • Ricorsione: gli elementi vengono confrontati per determinare il più piccolo
  • Ricombinazione: gli elementi sulla sinistra vengono confrontati per determinare il più piccolo


1. A0 = {3, 7,15} A00 = {2, 4,6}!B = {2}
2. A0 = {3,7,15} A00 = {4,6}!B = {2,3}
3. A0 = {7,15} A00 = {4,6}!B = {2, 3,4}
4. A0 = {7,15} A00 = {6}!B = {2,3, 4,6}
5. A0 = {7,15} A00 =;!B = {2,3, 4, 6, 7,15}

La complessità migliore, media e peggiore sarà sempre O(n log n)

Ordinamento per distribuzione
L’ordinamento della sequenza viene realizzato applicando il principio del Divide et impera, viene scelto un numero a caso tra quelli presenti nella sequenza e vengono separati gli elementi in 2 gruppi, quelli più piccoli e quelli più grandi. A loro volta questi gruppi vengono suddivisi fino ad ottenere un unico gruppo con un numero.
Concatenando tutti i gruppi composti da 1 numero si ottiene la sequenza ordinata.

1.{3,7,15,2,4,6}
2.{3, 2,4,[6],7,15}
3.{2,[3],4,[6],7,15}
4.{2,3,4,6,7,15}

Alberi binari
Negli alberi, a differenza delle liste, ogni elemento può contenere più successori, per esempio in un albero genealogico. Si parla di albero binario quando un nodo padre può avere solo 2 figli, necessari e sufficiente.
Un parametro dell’albero è la dimensione n, dato dal numero dei nodi contenuti. Gli archi sono n-1. La dimensione può essere calcolata sommando i nodi del sotto-albero destro e sinistro e sommando il nodo radice.
Un parametro dell’albero è la profondità che indica la distanza tra una foglia e la radice e si calcola partendo dalla foglie a salire.
Un altro paramentro dell’albero è l’altezza che indica la distanza massima ossia quanto nodi ci sono a partire dalla radice. Per calcolarlo si applica un algoritmo ricorsivo che calcola l’altezza dei 2 sottoalberi sotto root.
Un albero è bilanciato quando i due rami hanno la stella altezza, altrimenti viene detto sbilanciato.
Un albero è completo quando ogni nodo ha 2 figli.
Questi ha (2^h)-1 nodi interni e 2^h foglie, 2^(h+1)-1 i nodi complessivi e h=log(n+1)-1

Nelle liste doppie, per inserire un elemento figlio v dopo l’elemento padre u, dobbiamo aggiornare i riferimenti di u indicando che v è il figlio(u.sn=v), ed i riferimenti di v indicando che u è il padre (v.padre=u)
Per inserire un nuovo padre occorre assegnare il suo figlio e definire il nonno che punta al padre.
Per cancellare il padre u dobbiamo individuare il nonno di u ed assegnarlo e dobbiamo assegnare al nonno il figlio.

Nelle code con priorità viene assegnato ad ogni elemento un peso (valore di insieme ordinato) che indica la priorità. In fase di estrazione first e dequeue viene estratto l’elemento con la priorità piu alta.
Se la coda non è ordinata, in sede di inserimento occorre scorrere tutta la lista per capire dove inserire. Ma se la coda p ordinata allora l’inserimento è molto più veloce.

Nell’heaptree ogno nodo padre contiene dei nodi figli, in cui il padre ha il valore minore pertanto è ordinato e pesato. Nell’heap un padre può contente solo 2 figli, come l’albero binario.

Grafi
Sono una generalizzazione di liste e alberi in cui il legame è indicato in entrambi i versi, padre-figlio e figlio-padre.
Il grafo è composto da nodi e coppie di nodi, in cui i nodi n indicano l’ordine o vertice mentre le coppie m indicano gli archi.
La dimensione è data dalla loro somma n+m, pertanto la complessità lineare viene definita O(n+m).
Un grafo è sparso se O(n) mentre è denso se O(n^2). Un nodo viene rappresentato graficamente come un punto o cerchio mentre un arco come una linea che collega due nodi indicati come (u, v).

  • Un grafo G è composto da vertici V e archi E: G=(V,E).
  • Un grafo viene detto pesato se ad ogni arco viene associato un valore.
  • Dato un arco (u, v) diremo che i nodi (u, v) sono adiacenti.
  • L’arco (u,v) è incidente per il nodo x SE x=v oppure x=v, ossia se l’arco tocca il nodo.
  • Il grado di un nodo indica quanti archi sono incidenti.
  • Se non vi sono archi incidenti per un nodo, allora si dice che il nodo è isolato.

La somma dei gradi di un grafo è uguale al doppio degli archi, quindi n=2m se abbiamo 3 archi avremo 6 nodi.
Un cammino di un grafo indica la sequenza di nodi che occorre attraversare per passare da un nodo u ad un nodo z. La somma dei salti, ossia dei nodi, indica la lunghezza del grafo.
Un cammino si dice ciclo se il punto di partenza e di arrivo coincidono.
Il cammino minimo o distanza indica la lunghezza minima per percorrere da u a z.
Il peso di un cammino o distanza pesata indica la somma dei pesi degli archi attraversati.
Il cammino minimo pesato indica il cammino con il peso minore.
Non è detto che il cammino minimo pesato debba essere anche un cammino minimo in quanto un cammino minimo pesato potrebbe passare per più nodi con bassi pesi a differenza di un cammino pesato che invece passa per pochi nodi senza dare valore al loro peso. In questo caso abbiamo una disuguaglianza triangolare.
Un sottografo G1 è un grado composto da un sottoinsieme di nodi ed archi di G. Se il sottografo G1 è composto da tutti gli archi di G, allora si tratta di un sottografo indotto. Inoltre si parla di sottografo connesso e massimale di G se tutti i nodi sono connessi e non può essere esteso. Un grafo è completo se tutti i nodi sono collegati gli uni con gli altri, in questo caso si parla di cricca o clique per indicare un grafo completo e massimale. In questo caso, se tutti i nodi sono connessi tra di loro, per calcolare il numero si archi per un numero di nodi si utilizza questa formula: numero_archi = numero_nodi ( numero_nodi -1 ) /2
Due nodi sono connessi se esiste un cammino in grado di connetterli.
I grafi sono non orientati se non distinguiamo tra un arco (u,v) e (v,u) mentre invece sono orientati quando indichiamo anche il verso, da/a. In questo caso parliamo di nodi iniziale o di partenza e nodo finale o di destinazione.
In un grafo orientato il numero degli archi m, indica anche il grado del grafo. Mentre invece in un grafo non orientato il grado del grafo può essere anche il doppio.
Inoltre il nodo u è fortemente connesso al nodo z se tutti gli archi del cammino sono orientati e non vale il contrario. Un ciclo orientato avviene quando un nodo iniziale è orientato e si congiunge con se stesso.

Problemi su grafi

Problema 1: Immaginiamo che delle persone debbano andare ad una gita e che vogliano essere disposte nel pullman con il loro amico. In questo caso definiamo un grafo composto da i nodi costituiti dalle persone e gli archi rappresentati dal legame con l’amico. In questo caso l’arco (x, y) sarà possibile solo se le persone x ed y si conoscono. Il grafo da realizzare deve prevedere che un nodo possa essere connesso solo ad 1 nodo. In base all’abbinamento o accoppiamento perfetto si determinano da 0 a n possibili coppie di abbinamento.

Problema 2: Supponiamo che adesso i partecipanti debbano effettuare una escursione e che debbano disporsi in fila indiana, ma loro esigono di essere disposti prima e dopo la persona che conoscono. In questo caso si cerca un cammino hamiltoniano ossia un cammino che passi per tutti i nodi 1 sola volta.

Problame 3: Supponiamo adesso che i partecipanti debbano andare a cena e vogliano essere disposti in un tavolo rotondo in modo tale da essere seduti affianco alla persona che conoscono. In questo caso abbiamo un ciclo hamiltoniano ossia un cammino in cui l’ultimo nodo sia collegato con il primo.

Problema 4: adesso i nostri partecipanti vogliono fare un giro per il parco passando per tutti i ponti esistenti ma 1 sola volta. In questo caso ci troviamo di fronte ad un cammino euleriano, da Euler, ossia un cammino che passi per tutti gli archi 1 sola volta. Tale cammino prevede un multigrafo, ossia un gruppo di grafo connessi, che possano essere connessi a vicenda in un ciclo, cosidetto ciclo euleriano. In questo caso Euler dimostrò che il ciclo euleriano è possibile solo se tutti i nodi siano connessi ed abbiano grado pari, ossia sia possibile entrare ed uscire in un nodo. In caso contrario possiamo trovare un cammino euleriano.

Per i primi 2 problemi sono noti algoritmi polinomiali mentre non esistono negli altri 2 casi.

Colorazione dei grafi
Immaginiamo il caso in cui dobbiamo colorare una cartina geografica e vogliamo colorare le nazioni adiacenti con colori diversi, per non confonderci. In questo caso non abbiamo a nostra disposizione una algoritmo polinomiale per determinare il numero minimo di colori K da utilizzare. Nel nostro caso ipotizziamo che il grafo sia composto da una cricca,  ossia un gruppo di nodi tutti interconnessi. In questo caso è necessario utilizzare almeno 4 colori, pertanto possiamo utilizzare la teoria dei 4 colori che

Visita di grafi
Spesso siamo interessati a visitare un grafo per determinare il cammino necessario al fine di raggiungere un vertice a partire da un altro vertice.
Questa operazione può essere effettuata utilizzando:

  1. un ricerca per ampiezza (Breadth-first search)
  2. una ricerca per proforndità (Depth-first search).

La principale differenza tra di esse consiste nel fatto che la prima utilizza una coda per mantenere traccia dei vertici visitati mentre la seconda utilizza una pila. Questo comporta che nel primo caso vengono visitati prima i vertici “fratelli” dopodichè si accede ai vertici “figli” e cosi via. Mentre nel secondo caso viene effettuata una visita ricorsiva pertanto vengono visitati i vertici “figli” in profondità.

Visita per ampiezza
In questo caso i vertici sono visitati 1 sola volta, quindi tutti i vertici adiacenti “figli” vengono memorizzati in una coda dopodichè viene ripreso il primo vertice in coda e vengono visitati i loro vertici adiacenti “figli”. Prima di accedere ai vertici “nipoti” si visitano prima i vertici “figli” di tutti i vertici in coda secondo l’ordine in cui sono presenti nella coda stessa. Quindi vengono prima visitati i vertici che si trovano a distanza 1 poi quelli a distanza 2. Gli archi che non sono visualizzati nell’albero BFS sono definiti “all’indietro” “back”.
Le strutture da considerare relativamente ad un vertice u sono:

  • lista di adiacenza: i vertici adiacenti al vertice u
  • lo stato del vertice: “visitato”, “non visitato”, “in corso di visita”
  • la distanza dal vertice sorgente
  • predecessore del vertice
  • la coda dei vertici in esame

Il tempo di esecuzione totale di questo algoritmo è O(V+E) dove V è l’insieme dei vertici del grafo ed E è l’insieme degli archi che collegano i vertici.

Visita per profondità
In questo caso gli archi vengono visitati 1 sola volta, in particolare si tratta di una funzione ricorsiva che dato un vertice di partenza accede ai figli e nipoti ancor prima di accedere agli altri fratelli. Se sostituiamo alla coda del BFS una pila, abbiamo questa situazione, ossia vengono visitati gli ultimi elementi trovati, ossia i figli, invece dei fratelli. Si viene a creare una vera e propria chiamata ricorsiva.

Cammino minimo
Il cammino che impiega meno archi che portino da un vertice ad un altro. La percorrenza da u a v può presentare diversi cammini.
Si può procedere prevedendo un cammino BFS che utilizza una coda con priorità, ossia per ogni passo viene estratto il vertice che presenta il peso minore.

Minimo albero di ricoprimento
Si tratta di un albero con un sottoinsieme di archi dai pesi minimi.
L’algoritmo di base cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa ad ogni passo locale. Pertanto a distanza 1 dal nodo sorgente verrà considerato il cammino che presenta il costo d’arco più basso, e così via per le altre distanze.
Il taglio rappresenta una sezione di un grafo che lo scinde in 2 grafi.

Algoritmo di Kruskal
Ordiniamo gli archi per costi e poi li esaminiamo in questo ordine e li inseriamo man mano nella soluzione che stiamo costruendo, se non formiamo cicli con archi precedentemente selezionati. Occorre creare una coda con priorità da cui estraiamo gli archi con peso minore per connettere dei nodi che non formino un ciclo. In questo modo si vengono a formare un insieme di alberi che vengono pian piano connessi come se fosse una foresta
Il costo computazionale dell’algoritmo è nel caso peggiore O(V*E) dove E è il numero di archi ed V il numero di vertici.

Algoritmo di Prim
A partire da un nodo u, viene scelto l’arco adiacente con costo minore. Anche in questo caso viene utilizzata una coda di priorità e partendo da un nodo sorgente viene estratto dalla coda l’arco con peso minore.

 

Categorie:master
%d blogger cliccano Mi Piace per questo: