Tecniche di Programmazione - Appunti di immediata comprensione

A A G G

G D D

D

Ritorna poi l’esecuzione a C, che va al suo terzo adiacente, F, da marcare:

F

B C

A G

D

L’esecuzione passa ad F, che ha G come adiacente, che verrà marcato:

F

B

A C G

D

Segue quindi poi che: F

F B

B A C

A C G

D

G

D

In questo caso l’albero di copertura di visita in profondità sarà il seguente:

B

C

A F

D G

PSEUDOCODICE

def Algoritmo Visita in Profondità Ricorsivo dfs (vertice v, albero T):

marca e visita v

for each arco (v,w):

if (w non è marcato):

aggiungi arco (v,w) all'albero T

Algoritmo Visita in Profondità Ricorsivo dfs (vertice w, albero T)

def Visita DFS (vertice s):

T=albero vuoto

Algoritmo Visita in Profondità Ricorsivo dfs (vertice s, albero T)

return T

CODICE ALGORITMO ITERATIVO

#Mentre nell’algoritmo di visita in ampiezza si sfruttava la coda (in quel caso il

primo nodo ad essere visitato era anche quello che per primo usciva dalla coda), in

questa visita in profondità si sfrutta la pila: il nuovo nodo visitato ha la

priorità su tutti gli altri. Non appena il nodo non ha più adiacenti, si deve

ricordare chi ha chiamato chi.

def DFV(G,s):

n=size(G) #numero di nodi

pila=[s]

visited = [False]*n #Visited ha sempre lo stesso scopo

pred = [-1] * n #Modella quale nodo ha visitato ogni nodo(come prima)

while (pila!=[]):

next = pila.pop()

#Da qui in poi l'algoritmo farà le stesse identiche cose dell'algoritmo precedente

con la differenza che si avrà una logica stack invece che con una logica della coda

if visited[next]==False: #Se non hai visitato il nodo...

visited[next]=True #...marcalo come visitato

print(next) #e stampalo

for v in neighbors(G,next): #considerando tutti i vicini di v

if visited[v]==False:#se il nodo non è stato visitato...

pila.append(v) #...appendilo allo stack

pred[v]=next #e metti pred[v]=node

return edges(pred)

def edges(pred):

E=[]

for i in range(len(pred)):

if pred[i] != -1:

E.append([pred[i],i])

return E

CODICE ALGORITMO RICORSIVO

def dfrs(s, visited, G): #s: nodo di partenza da cui deve partire la visita

visited[s]=True

for v in neighbors(G,s):

if not visited[v]:

print("("+str(s)+","+str(v)+")")

dfsr(v,visited,G)

dfsr(0,[False]*size(G),G)

#Mi visiti nel grafo G, a partire dal nodo 0, dove tutti i nodi sono non visitati?

#A ogni nodo, per ogni passo della ricorsione, prendo il nodo, lo visito e per ogni

suo vicino,se non l'ho visitato allora lo stampo e vai a visitare a partire da

questo nodo

#E' un algoritmo di visita preorder: stampo prima il padre e poi il figlio

CHIUSURA TRANSITIVA

Per comprendere il concetto, partiamo da un esempio: consideriamo il seguente grafo G:

D E

B

A C

In una situazione reale potrebbe significare che B è follower di D, C è follower di D ecc…

L’obiettivo è sapere quali sono i legami indiretti (o transitivi) del tipo: se B è amico di D e D è

amico di E, si suppone che anche B è amico di E

Per comprendere ciò si crea un nuovo grafo G* che è la chiusura transitiva di G:

D E

B

A C

Formalmente:

Dato un grafo orientato G, la chiusura transitiva crea un nuovo grafo G* tale che, se G ha un

≠ ):

cammino da un nodo ad un nodo (con

• G* ha gli stessi nodi di G

•

G* ha un arco da a

def closure(G):

for k in nodes(G):

for i in nodes (G):

for j in nodes (G):

if (is_edge(G,i,k) and is_edge(G,k,j)):

insert_edge(G,i,j)

(, )

“Prendi tutti i nodi (nodi intermedi); per ogni coppia di nodo vai a vedere se

:

contiene un collegamento a e se contiene un collegamento a se avviene ciò vai a

”

inserire l’arco da a 3

() = ( )

GRAFO PESATO

DEFINIZIONE

Con peso si intende un qualsiasi contenuto informativo (numero intero, decimale, booleano,

lista ecc…)

Un Grafo è detto Pesato se esiste una funzione che mappa i suoi archi o i suoi nodi (o

entrambi) se rispettivamente il grafo è pesato sugli archi, sui nodi o su entrambi.

IMPLEMENTAZIONE TRAMITE MATRICE DI ADIACENZA DI UN GRAFO PESATO SUGLI ARCHI

In questo caso, invece di inserire 1 nella posizione della matrice che indica la presenza

dell’arco da a si inserisce direttamente il peso (contenuto informativo).

Ad esempio:

5

5

∞

Si stabilisce che l’arco inesistente si indica con un peso

Con questa implementazione, viene da se che si assume di considerare pesi non nulli.

Si inserisce peso 0 nell’arco che va da ad (cioè l’arco esiste e ha peso 0)

CREAZIONE DI UN GRAFO TRAMITE MATRICE DI ADIACENZA

#In questo caso bisogna creare una matrice di tutti infiniti tranne il

posizionamento di 0 negli archi che vanno da i ad i

def create_graph(n):

M=[]

for i in range(n):

l=[]

for j in range(n):

if(i==j):

l.append(0)

else:

l.append(float('inf'))

M.append(l)

return M

METODO SIZE: RESTITUZIONE DEL NUMERO DI NODI DEL GRAFO

def size(G):

return len(G) () = (1)

In questo caso si intuisce che

METODO SIZE-EDGE: RESTITUZIONE DEL NUMERO DI ARCHI DEL GRAFO

def size_edge(G):

c=0

n=size(G)

for i in range(n):

for j in range(n):

if G[i][j]!=float('inf'):

c=c+1

return c

METODO NODES: RESTITUZIONE DELLA LISTA DEI NODI DEL GRAFO

def nodes(G):

n = size(G)

L = []

for i in range(n):

L.append(i)

return L () = ()

In questo caso si intuisce che

METODO IS-EDGE: VERIFICA PRESENZA DELL’ARCO CHE VA DA A

def is_edge(G, i, j):

return G[i][j] != float('inf')

() = (1)

In questo caso si intuisce che

METODO INSERT-EDGE: AGGIUNTA DELL’ARCO PESATO CHE VA DA A

def insert_edge(G, i, j, w):

G[i][j] = w () = (1)

In questo caso si intuisce che

METODO DELETE-EDGE: ELIMINAZIONE DELL’ARCO CHE VA DA A

def delete_edge(G, i, j):

G[i][j] = float('inf') () = (1)

In questo caso si intuisce che

METODO OUT-DEGREE: NUMERO DI VICINI USCENTI (ADIACENTI) AL NODO

def out_degree(G, i):

return len(neighbors(G,i))

METODO IN-DEGREE: NUMERO DI ARCHI ENTRANTI AL NODO

def in_degree(G, j):

s = 0;

for i in range(len(G)):

if(is_edge(G,i,j)):

s=s+1

return s

METODO NEIGHBORS: RESTITUISCE LISTA DEI NODI ADIACENTI AL NODO

def neighbors(G, i):

L = []

for j in range(len(G[i])):

if is_edge(G,i,j):

L.append(j)

return L

METODO PRINT_GRAPH: STAMPA A VIDEO DEL GRAFO (SI STAMPANO I PESI)

def print_graph(G):

for i in range(len(G)):

print(G[i])

METODO WEIGHT: CAPIRE QUAL E’ IL PESO DELL’ARCO CHE VA DA A

def weight(G, i, j):

return G[i][j]

6.5-TECNICA GOLOSA

CAMMINI MINIMI

= (, ) ( , )

Sia un Grafo Orientato con pesi dati da costi del tipo sugli archi.

=< , , … , >

Il costo di un cammino è dato da:

0 1

() = ( , )

∑ −1

=1 (, )

Un Cammino Minimo tra una coppia di vertici è un cammino di costo minore o

uguale a quello di ogni altro cammino tra gli stessi vertici.

I cammini minimi da un vertice a tutti gli altri vertici del grafo possono essere

rappresentati mediante un albero la cui radice è (Albero dei Cammini Minimi).

Segue un esempio di albero dei cammini minimi fra 1 e tutti gli altri nodi: si tratta di un

albero perché non contiene cicli; inoltre non è un albero binario (ad esempio il nodo 6 ha tre

figli).

A volte non si riesce ad avere sempre l’albero dei cammini minimi da un certo nodo

sorgente, ma si può avere il cammino minimo in termini locali, cioè osservando passo dopo

passo.

La Distanza Minima tra due vertici e è il costo di un cammino minimo da a

+∞

oppure a se i due vertici non sono connessi.

TECNICA GOLOSA (O GREEDY)

La Tecnica Golosa è un approccio usato principalmente per risolvere problemi di

ottimizzazione (come trovare il cammino minimo in un grafo).

In sostanza, funziona scegliendo passo dopo passo l'opzione che sembra essere la migliore

in base a un criterio specifico. Questo approccio è utile quando trovare la soluzione

ottimale richiede troppo tempo, quindi la soluzione generata dalla tecnica golosa può

essere una buona approssimazione dell'ottimo.

Un Algoritmo Greedy è un tipo di algoritmo che cerca una soluzione accettabile da un

punto di vista globale, facendo scelte locali che sembrano le più vantaggiose in base a

criteri definiti in precedenza.

In particolare, gli algoritmi greedy cercano di mantenere una proprietà chiamata

"sottostruttura ottima", risolvendo i sottoproblemi in modo avido (o goloso) considerando

la parte migliore dell'input per risolvere l'intero problema.

Quindi, in definitiva, la Tecnica Greedy permette di poter arrivare alla soluzione locale

ottima, ma non sempre permette di arrivare alla soluzione ottima globale.

Un esempio è l’Algoritmo di Dijkstra (segue).

ALGORITMO DI DIJKSTRA

SPIEGAZIONE

L’Algoritmo di Dijkstra è un algoritmo utilizzato per la ricerca dei cammini minimi tra un

punto di partenza e di arrivo (o anche l’albero dei cammini minimi, cioè tutti i cammini

minimi tra un punto di partenza e tutti gli altri) di un grafo che rispecchia queste tre

caratteristiche:

• Con o senza ordinamento

• Ciclico

• Con pesi non negativi sugli archi

Si propone un esempio di un problema in cui si vuole calcolare il percorso minimo tra Casa e

Ufficio passando tramite diversi nodi (diverse cittadine tramite le quali è possibile passare):

6

A B 5

2 2

CASA UFFICIO

C

8 2 9 1

3

D E

Bisogna ora associare ad ogni nodo un valore, detto “potenziale”, seguendo alcune regole:

• Inizialmente ogni nodo ha un potenziale pari ad infinito, tranne il nodo di partenza

(Casa) ha potenziale 0 (dista 0 da se stesso)

• Ad ogni passo si sceglie il nodo con potenziale minore e lo si rende definitivo (il

potenziale definitivo indica la distanza da quel nodo a quello di partenza e non si può

più aggiornare), e si aggiornano i potenziali dei n