Dominazione euristica

La dominazione euristica è una relazione di preferenza tra due o più euristiche che consente di ordinarle per efficienza. È un termine utilizzato in informatica per la comparazione degli algoritmi di ricerca informata che utilizzano una funzione euristica. Date due euristiche A e B, si dice che A domina B quando l'euristica A consente di raggiungere il medesimo risultato di B con un minore costo/tempo della ricerca. Ad esempio, una strategia di ricerca informata è più efficiente quando consente di giungere al risultato espandendo un minore numero di nodi in un albero di ricerca oppure, nel caso di costi di passo variabili, quando riduce il costo complessivo della ricerca. Per comparare l'efficienza di ricerca delle funzioni euristiche si ricorre al calcolo del fattore di ramificazione effettivo o di un computo statistico ad hoc.