Potatura (informatica)

Nell'ambito degli algoritmi di ricerca su strutture a grafo e loro estensioni la potatura (o pruning) è una tecnica di miglioramento degli algoritmi che prevede l'eliminazione di nodi o interi cammini non necessari dagli alberi di ricerca^[1]. Si possono migliorare gli algoritmi considerando i diversi cammini che possono attraversare un nodo. Non tutti sono utili per cui possono essere eliminati.

Tipologie

Essenzialmente vi sono due tipi di potatura con le relative strategie^[2]:

• potatura dei cicli; fonte di inefficienza
• potatura di cammini molteplici: affinché per ogni nodo si abbia un solo cammino che lo attraversi, eliminando tutti gli altri.

Potatura dei Cicli

Alcuni degli algoritmi di ricerca potrebbero rimanere intrappolati in cicli senza possibilità di uscita anche nel caso di grafi finiti. Per avere la garanzia di trovare una soluzione in caso di grafo finito non andranno presi in considerazione vicini già presenti nel percorso corrente. Nella potatura dei cicli (cycle o loop pruning), si prevede un controllo addizionale preventivo: dato un nodo da aggiungere, va testata l’occorrenza nel cammino. Nello schema-base di algoritmo di ricerca si aggiungono alla frontiera solo cammini ${\displaystyle \langle n_{0},\ldots ,n_{k},n\rangle }$ tali che ${\displaystyle n\notin \{n_{0},\ldots ,n_{k}\}}$, scartando il cammino selezionato; in alternativa si può effettuare il controllo dopo la selezione del nodo.

La complessità dei controlli aggiuntivi per la verifica della presenza di un nodo nel cammino corrente dipende dal metodo di ricerca adottato:

• costante, per metodi (di ricerca in profondità) che memorizzano un unico cammino (in una lista o insieme); si può usare una funzione hash oppure si può associare un bit a ogni nodo (flag booleano), che sarà acceso quando viene aggiunto a un cammino e viene spento in caso di backtracking; per cui basterà non espandere nodi con il bit acceso; tale metodo funziona perché si lavora su un solo cammino;
• lineare, nella lunghezza del cammino corrente per metodi che gestiscono più cammini (esponenziali in spazio, come quelli di ricerca in ampiezza): serve una ricerca per evitare di aggiungere al cammino parziale un nodo già presente.

Potatura di Percorsi Multipli

Spesso più di un cammino porta a uno stesso nodo. Occorre quindi eliminare dalla frontiera ogni cammino che porti a un nodo per il quale ne esista già un altro, specie se di costo inferiore.

Una strategia di multiple-path pruning (MPP) può essere implementata gestendo una lista di nodi terminali di cammini già esplorati, detta lista chiusa o explored set: inizialmente essa è vuota poi, selezionato un cammino ${\displaystyle \langle n_{0},\ldots ,n_{k}\rangle }$ della frontiera, se ${\displaystyle n_{k}}$ è già nella lista esso può essere scartato, altrimenti si aggiunge ${\displaystyle n_{k}}$ alla lista e si prosegue.

Nota questa strategia non garantisce che non venga eliminato il cammino di costo minimo. Per garantire di preservare le soluzioni ottimali vi sono alcune alternative:

• assicurando che il primo percorso trovato per un dato nodo sia ottimale quindi gli altri si possono eliminare;
• se si dovesse inserire nella frontiera un cammino ${\displaystyle p=\langle s,\ldots ,n,\ldots ,m\rangle }$, ma fosse già presente in ${\displaystyle p}$ un cammino ${\displaystyle p'=\langle s,\ldots ,n\rangle }$ meno costoso per la parte fino a ${\displaystyle n}$, si può eliminare ${\displaystyle p}$ oppure oppure sostituire in ${\displaystyle p}$ tale parte con ${\displaystyle p'}$.

Il MPP rappresenta una strategia più generale rispetto alla semplice potatura dei cicli: un ciclo può essere considerato come un percorso alternativo verso un dato nodo, destinato a essere potato. La strategia MPP può essere implementata in modo da richiedere un tempo costante ed è preferibile con algoritmi di ricerca in ampiezza in cui, virtualmente, tutti i nodi considerati vanno memorizzati. La strategia di potatura dei cicli è preferibile in combinazione con metodi di ricerca in profondità, ad esempio con branch and bound in profondità (mentre con MPP ci sarebbe il rischio di crescita esponenziale della lista chiusa).

Argomenti correlati

• potatura alfa-beta: per alberi di ricerca Minimax
• potatura di alberi di decisione
• ottimizzazione