Ricerca di quiescenza
La ricerca di quiescenza è un tipo di ricerca informata. L'algoritmo di ricerca di quiescenza si basa sulla tecnica del taglio di ricerca, ossia non scandaglia l'intero albero della ricerca bensì si blocca al raggiungimento di determinate condizioni. Mentre gli altri algoritmi di ricerca in profondità si limitano a bloccare la ricerca a un determinato livello di profondità dell'albero logico o di tempo di ricerca, l'algoritmo basato sulla ricerca di quiescenza sospende la ricerca soltanto nel momento in cui raggiunge un nodo caratterizzato da uno stato di quiescenza ( nodo di quiescenza ). Nel nodo di quiescenza è improbabile che la ramificazione successiva ( nodi figli ) portino a radicali sconvolgimenti della situazione corrente. I nodi figli sono caratterizzati da valori simili a quelli del nodo di quiescenza. In tali caso l'algoritmo sospende di scandagliare la ramificazione e si limita a valutare l'intera ramificazione successiva mediante una funzione di valutazione. Un esempio di ricerca di quiescenza è il seguente.
L'albero di ricerca è caratterizzato da otto nodi terminali. Non è necessario però scandagliare l'albero per intero. I nodi di colore verde C e D sono due nodi di quiescenza poiché i valori dei rispettivi nodi figli non si discostano eccessivamente dal valore del nodo genitore. È quindi possibile evitare di scandagliare i nodi figli, affidandosi eventualmente a una funzione di valutazione. Viceversa, i nodi di colore rosso A e B non sono nodi di quiescenza poiché i valori dei rispettivi nodi figli divergono notevolmente dal valore del nodo genitore. In questi casi è preferibile continuare la ricerca e scandagliare per intero la ramificazione.
Taglio della ricerca a profondità variabile. La ricerca di quiescenza consente di evitare il taglio della ricerca e di utilizzare la funzione di valutazione nei casi in cui le ramificazioni successive comportano un range di variazione molto ampio del risultato finale. Ad esempio, se nell'esempio precedente fosse una ricerca in profondità con taglio di ricerca al 3° livello per tutti i nodi, la funzione di valutazione potrebbe non essere in grado di valutare con efficacia i possibili esiti finali dell'albero di ricerca. Ad esempio, apparentemente il nodo A e il nodo C sembrerebbero uguali in quanto hanno il medesimo valore medio atteso ( 6 ). In realtà, a parità di valore medio atteso ( rendimento ) il nodo C è associato a un livello di rischio inferiore rispetto al nodo A.
