OKPEDIA RICERCA SOLUZIONI

Taglio di ricerca

Il taglio di ricerca è una tecnica utilizzata negli algoritmi di ricerca per interrompere l'elaborazione al raggiungimento di una determinata profondità dell'albero logico ( albero di ricerca ). Viene detta "taglio" in quanto l'albero di ricerca è scandagliato fino a una determinata profondità. Tutti i nodi e le ramificazioni al di sotto del limite di profondità sono esclusi dall'elaborazione.

TAGLIO DI RICERCA

Il taglio di ricerca consente di analizzare soltanto una minima parte dell'albero di ricerca È una tecnica efficace per trovare una soluzione sub-ottimale in tempi rapidi, purché la soluzione si trovi entro il limite di profondità del taglio. Il taglio di ricerca è utilizzato nelle tecniche di ricerca in profondità limitata.

Soluzioni in profondità. Il taglio della ricerca evita di scandagliare tutte le ramificazioni dell'albero logico. Tuttavia, quando le migliori soluzioni si trovano al di sotto del limite di profondità, l'algoritmo non riesce a trovale.

Funzione di valutazione. È utile abbinare il taglio della ricerca con una funzione di valutazione in grado di stimare l'esito delle ramificazioni che seguono ai nodi di taglio. La funzione di valutazione stima un valore potenziale delle ramificazioni per ciascun nodo situato al limite di taglio. Ciò consente di scegliere il ramo più promettente senza averlo scandagliato in profondità fino al nodo terminale.

Approssimazione. La funzione di valutazione è una tecnica molto approssimativa. L'esito delle ramificazioni successive ai nodi di taglio potrebbe essere soggetta a forti variazioni, la stima del valore medio atteso potrebbe non riflettere il valore del cammino. Una soluzione potrebbe essere fornita dagli algoritmi di ricerca di quiescenza che interrompono la ricerca soltanto quando rilevano uno stato di quiescenza ossia una situazione ( nodo ) a partire dal quale il valore dei nodi figli non varia eccessivamente rispetto al nodo genitore.

https://www.okpedia.it/taglio_di_ricerca



Ricerca soluzioni

Problemi