Abbiamo visto fin'ora svariati algoritmi di ricerca, i quali però possono essere migliorati prendendo in considerazione più percorsi verso un nodo. Introduciamo quindi una tecnica che si chiama potatura. In questo articolo vedremo due strategie di potatura che agiscono in maniera diversa in base all'obiettivo.
La prima strategia che vedremo è denominata ciclo di potatura o cycle pruning. Un grafo che rappresenta uno spazio di ricerca può includere cicli. In questa strategia per eliminare il ciclo si controlla se l'ultimo nodo sul percorso appare già prima sul percorso del nodo iniziale. Questi percorsi vengono scartati quando vengono aggiunti alla frontiera o non vengono aggiunti affatto.
La complessità computazionale della potatura del ciclo dipende dal metodo di ricerca utilizzato. Per i metodi depth-first, l'overhead può essere basso come un fattore costante, memorizzando gli elementi del percorso corrente come un set (ad esempio, mantenendo un bit impostato quando il nodo è nel percorso o utilizzando una funzione hash). Per le strategie di ricerca che mantengono percorsi multipli il ciclo di potatura richiede un tempo lineare rispetto alla lunghezza del percorso cercato.
Top comments (0)