Algoritmi e Strutture dati

Algorithm:

Alberi = struttura dati di nodi collegati con archi secondo una struttura

gerarchica identificando una radice (nodo di partenza) e foglia (nodo

terminale). Il percorso da un nodo ad un altro è unico

Vicino = genitore/figlio di un nodo

● Antenato = nodo raggiungibile attraversando la sua catena madre

● Discendente = nodo nel sottoalbero del nodo

● Grado = numero di figli di un nodo

● Grado di un albero = grado massimo di nodi nell'albero

●

Albero d-ario = ogni nodo ha massimo d figli

– PIENO = ogni nodo ha 0/d figli

– COMPLETO = quasi PERFETTO a meno di nodi in basso a destra

– PERFETTO = PIENO con tutte le foglie allo stesso livello

n = numero di nodi

h = altezza albero

Ricerca

●

– Depth First Search (DFS) = ricerca in profondità O(n) worst case

esploro tutto il grafo

– Breadth First Search (BFS) = ricerca a livelli O(n) worst case esploro

tutto il grafo

Preordine / Ordine / Postordine

Alberi pesati = gli archi hanno un costo

1. Completezza: se la soluzione (non è detto debba essere ottima) esiste

e viene trovata sicuramente

2. Ottimalità: trovo sempre la soluzione ottima

OPEN = lista nodi da visitare

● CLOSED = lista nodi visitati

●

b (branching factor) = massimo numero di figli che un nodo può avere

d (depth) = livello al quale trovo la soluzione

m (massima profondità) = profondità massima dell’albero

Algoritmi di ricerca:

Brute Force = ricerca esaustiva su tutte le possibili soluzioni

● Ricerca NON informata = basati sulla sola conoscenza del problema

●

– BFS = Completa se lo spazio di ricerca è finito. Ottima se il costo di

ogni arco è lo stesso. Tempo e Spazio O(b^d)

– Ricerca a costo uniforme = espando prima il nodo con il costo del

cammino minimo. Completa se il costo di un arco è ≥ di un epsilon

– (se avessi arco a costo 0 rimarrei bloccato in un ciclo). Ottima.

Tempo e Spazio O(b^C*/epsilon): il costo ottimale C* lo posso

raggiungere o con un arco dal costo C* oppure con tanti archi di

costo minimo epsilon)

– DFS = Completa se lo spazio di ricerca è finito. Ottima se ho un albero

(con un grafo esisterebbero diversi percorsi). Tempo O(b^m). Spazio

O(b•m)

– con Backtracking = genero un figlio alla volta. Se arrivo alla fine

dell’albero e non ho trovato la soluzione, torno al fratello

dell’ultimo figlio generato. Se finiscono i figli, vado al fratello del

padre e così via risalgo tutto l’albero. Spazio O(m)

– Limitata = m = l limite di espansione. Ottima solo se la soluzione si

trova entro il limite l

– ID (Iterative deepening) = l è crescente fino a che non trovo la

soluzione (al massimo l = d)

Ricerca informata = conosco altre informazioni oltre al problema (e.g.

● Commesso viaggiatore: so le distanze tra le città, Problema della

bisaccia: so il peso massimo dello zaino)

f(n) = g(n) + h(n)

h(n) = stima euristica: stima per difetto del costo del cammino. 0 ≤ h(n) ≤ h*(n)

costo effettivo. È

Ammissibile: non deve mai sopravvalutare la distanza. In caso

○ contrario, l'algoritmo verrà interrotto e potrebbe restituire percorsi

non ottimali

Consistente: quando seleziono il nodo successivo, sono sicuro che

○ sia l’ottimo

Dominante: la h(n) più grande è quella che si avvicina di più ad h*

○

– Best First = espando il nodo con f(n) minore

– Greedy = f(n) = h(n). Completa se ho albero con spazio di ricerca

finito / se ho un grafo no poichè posso avere cicli. Ottima no. Tempo e

Spazio O(b^m)

– A* = f(n) = g(n) + h(n). h e g sono inversamente proporzionali.

Completa poichè espando i nodi con f(n) ≤ f*(n). Ottima se ho un

albero con h(n) ammissibile / grafo con h(n) consistente

– IDA* (Iterative Deepenning A*) = espando se f(n) ≤ f*(n) (anziché

lavorare con un limite di profondità, lavoro con un limite di costo)

– Best First Ricorsiva = espando l’f(n) più piccolo e tengo traccia del

cammino alternativo migliore (e.g. città della Romania)

– MBA* (Memory Bounded A*) = quando la memoria è satura,

cancella la soluzione con f(n) maggiore. Completa se la soluzione

può essere contenuta in memoria (se il cammino è troppo piccolo).

Ottima se è raggiungibile

Ricerca locale = consulto un intorno. Posso usare una funzione di

● costo (da minimizzare) o obiettivo (da massimizzare)

– Hill climbing = mi muovo nella direzione del gradiente così da trovare

lo stato che massimizza la funzione obiettivo

– Stocastico = tra tutte le mosse che seguono il gradiente, scelgo a

caso

– con Riavvio Casuale = tanti Hill Climbing con stati iniziali casuali.

Ricerche statisticamente indipendenti

– Simulated Annealing = Hill Climbing che accetta mosse peggiorative

per poter uscire da eventuali massimi lovali

– Beam Search = genero casualmente K stati e K successori. Se la

soluzione è tra questi allora ho finito, altrimenti continuo a generare

Alberi binari

1. Il sottoalbero sinistro di un nodo contiene solo nodi con chiavi inferiori

alla chiave del nodo.

2. Il sottoalbero destro di un nodo contiene solo nodi con chiavi maggiori

della chiave del nodo.

3. Anche il sottoalbero sinistro e quello destro devono essere un albero

di ricerca binario.

– Inserimento O(n) = se l’elemento da inserire è maggiore del nodo in

– esame, vado a destra, altrimenti a sinistra

– Ricerca O(h) = se l’elemento da cercare è maggiore del nodo in esame,

vado a destra, altrimenti a sinistra

Best case: Albero perfetto con h = log2 n

Worst case: Albero lista con h = n

– Eliminazione O(h) = Ricerca dell’elemento.

Se è foglia lo elimino

Ha un figlio, collego questo al padre del nodo da eliminare

Ha due figli, trovo il minimo nel sottoalbero destro, lo copio nell’elemento da

eliminare, elimino il minimo nel sottoalbero destro che ho trovato

Alberi da gioco

Rappresentare gli stati di un gioco a interazione strategica. I nodi dell'albero

identificano i diversi stati del gioco mentre gli archi le possibili scelte/decisioni

(mosse) che gli agenti possono effettuare a partire da un determinato nodo

(situazione di gioco).

– Algoritmo min-max = algoritmo ricorsivo per la ricerca della mossa

migliore in un gioco a somma zero che si svolge tra due giocatori

potatura alfa-beta = “se ho un idea non buona, non perdere tempo a

● capire quanto sia cattiva”. Variante dell'algoritmo minimax che

consente di ridurre il numero dei nodi e delle ramificazioni da

analizzare per giungere al risultato minimax ottimale. Consiste

nell'interrompere l'esplorazione in profondità dei nodi quando non

sarebbero comunque selezionati dai giocatori perché peggiori rispetto

alle alternative possibili. Ciò consente di effettuare una potatura logica

dell'albero di gioco e ridurre la complessità dell’algoritmo

Alpha = miglior valore trovato per max

Beta = miglior valore trovato per min

Best case: O(b^d/2) scarto subito metà albero

Medium case: O(b^3d/4)

Worst case: O(b^d) calcolo altezza albero

Grafi = configurazione formata da un insieme di punti (vertici o nodi) e un

insieme di linee (archi) che uniscono coppie di nodi. Il percorso da un nodo ad

un altro NON è unico.

n = nodi

m = archi

– NON orientato

– Orientato

– Pesato

– Completo = esiste un arco per ogni coppia di nodi

Rappresentazioni:

Lista archi = lista di tutti gli archi

● Lista incidenza = lista con tutti i nodi, per ogni nodo la lista dei suoi

●

● vicini

Lista adiacenza = lista con tutti i nodi, per ogni nodo la lista dei suoi

● archi

Matrice incidenza = matrice n x n con 1 se i nodi sono collegati, 0

● altrimenti

Matrice adiacenza = matrice n x m con 1 se il nodo appartiene all’arco,

● 0 altrimenti

Ricerca

●

– Depth First Search (DFS) O(n+m)

– Breadth First Search (BFS) O(n+m)

Heap = alberi per estrarre rapidamente minimo/massimo. Soddisfa la "proprietà

di heap": se A è un genitore di B, allora la chiave (il valore) di A è ordinata

rispetto alla chiave di B conformemente alla relazione d'ordine applicata

all'intero heap (massimo o minimo)

Heap binari = Heap sviluppato su alberi binari. Il massimo (heap-max) / minimo

(heap-min) è nella radice. h = O(log2 n)

– Inserimento O(log2 n) = inserisco l’elemento come foglia e ripristino la

proprietà di ordinamento

– Estrazione massimo O(log2 n) = copio nella radice il valore della foglia

più a destra, elimino questa foglia e ripristino la proprietà di

ordinamento

– Massimo/Minimo O(1) = è l’elemento nella radice

d-Heap = generalizzazione degli heap binari

Heap binomiali = Heap che segue le seguenti regole:

B è un nodo

1. 0

Per i>0, B è ottenuto fondendo due alberi binomiali B , ponendo la

2. i+1 i

radice di un B come figlia della radice dell’altro B

i i

È cioè una foresta di al massimo un numero di alberi binomiali pari a parte intera

di log2 n

n = 2^h

h = log2 n

Proprietà di unicità = per ogni intero i≥0, esiste al più un Bi nella foresta

Heap binomia rilassato = Heap binomiale per cui non vale la proprietà di

unicità

Heap di Fibonacci = Heap binomiale rilassato per cui rilassiamo anche la

proprietà di struttura: accettiamo che i Bi possano avere meno nodi.

Cammini minimi = cammino con costo minore

Disuguaglianza triangolare

– Algoritmo di Bellman-Ford O(m x n) = Brute Force. Dalla sorgente,

valuto 2 passaggi alla volta. Se trovo un percorso con costo minore,

aggiorno il peso. SOLO per grafi a sorgente singola senza cicli a costo

negativo

– Algoritmo di Dijkstra O(m + n•log2 n) = dal nodo corrente scelgo l’arco

a costo minore sulla frontiera (archi verso i nodi raggiungibili). SOLO

per grafi a sorgente singola senza archi a costo negativo. Worst case:

O(m x n) poichè devo vedere tutti gli archi e i nodi, ma posso fare di

meglio:

Posso migliorarlo se mantengo gli archi incidenti ordinati in una coda di priorità

tramite heap. Il costo dipende da come è implementata la coda di priorità:

d-heap = O(n•d•logd n + m•logd n)

● Heap binomiali = O(m•log2 n)

● Heap rilassati = O(m•log2 n)

● Heap Fibonacci = O(m + n•log2 n)

●

– Algoritmo di Floyd Warshall O(n^3) = Brute Force con

Programmazione dinamica, trova il cammino minimo t