Potatura logica

La potatura logica è l'eliminazione di uno o più ramificazioni di un albero logico ( albero di ricerca ) da parte di un algoritmo di ricerca. Per ridurre il tempo di esecuzione un algoritmo di ricerca può eliminare le ramificazioni giudicate poco interessanti e concentrarsi sull'analisi delle ramificazioni utili. La potatura logica consiste nell'eliminazione dell'intero sottoalbero dal processo di elaborazione.

Il ricorso alla potatura logica è frequente, in particolar modo, negli algoritmi di ricerca informata, i quali sono in grado di stimare empiricamente l'utilità di ogni ramificazione sulla base di una determinata regola o ipotesi e nelle applicazioni informatiche particolarmente complesse ( intelligenza artificiale ). Alcuni esempi di potatura logica di un albero di ricerca sono i seguenti:

• Potatura alfa-beta. La potatura alfa-beta è una tecnica utilizzata per migliorare l'efficienza degli algoritmi di ricerca minimax. La potatura alfa-beta elimina dalla lista dei nodi da esplorare tutte le ramificazioni e i nodi che seguono alle scelte strategiche non razionali.
• Tabella delle trasposizioni. La tabella della trasposizione elimina dalla lista della ricerca tutte le sequenze di scelta ( ramificazioni ) dell'albero di ricerca che conducono a un medesimo risultato finale.
• Ricerca con taglio in avanti. La ricerca con taglio in avanti seleziona i nodi da eliminare, senza ulteriori approfondimenti, sulla base di una funzione di valutazione o dell'esperienza probabilistica maturata dall'algoritmo nel corso della ricerca stessa.