Mi serve un esempio per calcolare la penetranza e fattore di ramificazione dellalbero di ricerca nella ricerca euristica nello spazio degli stati. Le definizioni sono le seguenti. Penetranza $ P $ è definita da
$ \ qquad \ displaystyle P = \ frac {L} {T} $
e fattore di ramificazione $ B $ è definito da
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
dove $ L $ è la lunghezza del percorso dalla radice alla soluzione e $ T $ il numero totale di nodi espansi.
Risposta
Considera il seguente albero di ricerca. Il tuo algoritmo di ricerca euristica avvia la ricerca dal nodo radice. I nodi non espansi sono contrassegnati in grigio.
Per qualche motivo, leuristica viene guidata verso la sottostruttura più a sinistra, quando in effetti il nodo obiettivo si trova nella sottostruttura più a destra, contrassegnata in verde.
I nodi che hanno sono state espanse sono contrassegnate in rosso. Dopo che laccattivante sottostruttura più a sinistra si è rivelata un vicolo cieco, leuristica ora viene fortunatamente guidata direttamente verso lobiettivo. Dalla situazione della figura precedente, espanderemo un totale di tre nuovi nodi prima di arrivare allobiettivo.
Dalla figura sopra, la lunghezza del percorso verso lobiettivo è $ 3 $. Sono presenti $ 17 $ nodi espansi. Pertanto, la penetranza è $ 3/17 \ circa 0,43 $.
Il fattore di diramazione è il numero massimo di successori di qualsiasi nodo. Ad esempio, il fattore di ramificazione di un albero binario è $ 2 $ poiché ogni nodo ha al massimo due figli. Allo stesso modo, nellalbero di ricerca sopra il fattore di ramificazione è $ 3 $.
Cosa sembra che ti interessi non è il fattore di ramificazione, ma il fattore di ramificazione effettivo $ B ^ * $ che è un modo per caratterizzare la qualità di uneuristica. Se il numero totale di nodi espansi è $ T $ e la lunghezza del percorso verso lobiettivo è $ L $ (questo è più comunemente noto come s profondità ), quindi $ B ^ * $ è il fattore di ramificazione che un albero uniforme di profondità $ L $ avrebbe per contenere $ T + 1 $ nodi. Pertanto,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Se inserisci i valori che abbiamo ottenuto nella ricerca, ovvero $ T = 17 $ e $ L = 3 $, ottieni $ B ^ * \ circa 2,165 $. Questo è esattamente lo stesso valore che ottieni usando la tua equazione; è semplicemente una rappresentazione diversa per la stessa cosa.
Il fattore di ramificazione effettivo può variare tra le istanze, ma è in qualche modo costante per problemi abbastanza complessi. Uneuristica ben progettata avrebbe un valore di $ B ^ * $ vicino a $ 1 $, che consente di risolvere problemi abbastanza grandi a un prezzo ragionevole.
Commenti
- Risolvendo la formula per $ B $, tu ottieni $ B \ circa 2,165 $. Mi chiedo quale sia linterpretazione di quel valore. ' è vicino al fattore di ramificazione medio di tutti i nodi interni, ma non è lo stesso.
- @MAcad In effetti, ciò che ti interessa non è il fattore di ramificazione, ma il fattore di ramificazione efficace che è lontano per caratterizzare la qualità di uneuristica. I ' aggiornerò la mia risposta.
- @Juho Penso che se uso la formula del fattore di ramificazione testerò molti numeri nellLHS e li calcolerò e verificherò uguale a RHS come segue: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 non uguale a T = 17 quindi dobbiamo testare B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 risultato vicino a T quindi possiamo testare B = 2.1 e così via fino a raggiungere il risultato T !!!! Penso che questa formula possa essere utilizzata in questo modo :))))