Ricerca con taglio in avanti

La ricerca con taglio in avanti è una tipologia di algoritmo di ricerca. In questa categoria di algoritmi la ricerca si interrompe a priori, senza alcun approfondimento o verifica, su determinati nodi figli. Ciò consente di approfondire la conoscenza soltanto sui nodi figli considerati più promettenti, accorciando i tempi di elaborazione. Il termine "taglio in avanti" deriva dal fatto che intere ramificazioni dell'albero di ricerca sono eliminate ( potatura logica ). Ogni nodo-figlio eliminato è, infatti, a sua volta un nodo-genitore e così via.

Il vero e proprio punto cruciale della ricerca con taglio in avanti è il criterio di selezione dei nodi da tagliare e da approfondire. La selezione può essere effettuata mediante due distinti criteri:

• Funzione di valutazione. Una funzione di valutazione potrebbe ordinare i nodi-figli in base a un indicatore di utilità attesa, eliminando quelli meno interessanti. Un semplice esempio di ricerca con taglio in avanti è la ricerca beam search. Non è però detto che sia sempre un metodo di selezione efficiente. Per funzionare è necessario che la funzione di valutazione sia sufficientemente perfezionata. Ad esempio, il semplice criterio a fascio della ricerca beam search non assicura di prendere sempre la strada migliore. La soluzione ottimale potrebbe trovarsi nelle ramificazioni scartate a priori dall'algoritmo.
• Taglio probabilistico. La selezione probabilistica si basa sull'esperienza maturata dall'algoritmo nel corso della ricerca stessa. Nel corso dell'elaborazione l'algoritmo con taglio probabilistico ( probabilistic cut ) potrebbe scorgere delle regolarità probabilisitche. L'esperienza è alla base del criterio stesso di selezione. Ad esempio una particolare combinazione di valori dei nodi figli potrebbe essere associata a un numero elevato di fallimenti. Quando l'algoritmo si trova in condizioni di ricerca simili su un nodo, potrebbe decidere di non scandagliarlo in profondità e di tagliare tout-court la sua sotto-ramificazione di nodi dal processo di ricerca. L'esperienza maturata dall'algoritmo può, inoltre, essere memorizzata in un database ( sistema esperto ) per migliorare le ricerche future. Essendo slegata dall'esperienza del programmatore, l'algoritmo con taglio probabilistico potrebbe individuare delle regolarità non ancora conosciute dall'utente umano.