Necesito un ejemplo de cómo calcular la penetrancia y factor de ramificación del árbol de búsqueda en la búsqueda heurística en el espacio de estados. Las definiciones son las siguientes. Penetrancia $ P $ se define por
$ \ qquad \ displaystyle P = \ frac {L} {T} $
y factor de ramificación $ B $ está definido por
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
donde $ L $ es la longitud de la ruta desde la raíz hasta la solución y $ T $ el número total de nodos expandidos.
Respuesta
Considere el siguiente árbol de búsqueda. Su algoritmo de búsqueda heurística inicia la búsqueda en el nodo raíz. Los nodos no expandidos están marcados en gris.
Por alguna razón, la heurística se guía hacia el subárbol más a la izquierda, cuando, de hecho, el nodo objetivo está en el subárbol más a la derecha, marcado con verde.
Los nodos que tienen expandidos están marcados en rojo. Después de que el atractivo subárbol situado más a la izquierda resultó ser un callejón sin salida, ahora, afortunadamente, la heurística se dirige directamente hacia la meta. De la situación de la figura anterior, expandiremos un total de tres nuevos nodos antes de llegar a la meta.
De la figura anterior, la longitud de la ruta hacia el objetivo es $ 3 $. Hay $ 17 $ nodos expandidos. Por lo tanto, la penetrance es $ 3/17 \ approx 0.43 $.
El factor de ramificación es el número máximo de sucesores de cualquier nodo. Por ejemplo, el factor de ramificación de un árbol binario es $ 2 $ ya que cada nodo tiene como máximo dos hijos. Asimismo, en el árbol de búsqueda anterior el factor de ramificación es $ 3 $.
¿Qué lo que parece interesarle no es el factor de ramificación, sino el factor de ramificación efectivo $ B ^ * $ que es una forma para caracterizar la calidad de una heurística. Si el número total de nodos expandidos es $ T $, y la longitud del camino hacia la meta es $ L $ (esto se conoce más comúnmente como s profundidad ), entonces $ B ^ * $ es el factor de ramificación que tendría un árbol uniforme de profundidad $ L $ para contener $ T + 1 $ nodos. Por lo tanto,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Si si conecta los valores que obtuvimos en la búsqueda, es decir, $ T = 17 $ y $ L = 3 $, obtiene $ B ^ * \ approx 2.165 $. Este es exactamente el mismo valor que obtienes al usar tu ecuación; es simplemente una representación diferente para lo mismo.
El factor de ramificación efectivo puede variar entre instancias, pero es algo constante para problemas bastante difíciles. Una heurística bien diseñada tendría un valor de $ B ^ * $ cerca de $ 1 $, lo que permite resolver problemas bastante grandes a un precio razonable.
Comentarios
- Al resolver la fórmula para $ B $, get $ B \ approx 2.165 $. Me pregunto cuál es la interpretación de ese valor. Está ' cerca del factor de ramificación promedio de todos los nodos internos, pero no es el mismo.
- @MAcad De hecho, lo que le interesa no es el factor de ramificación, sino el factor de ramificación efectivo que está lejos de caracterizar la calidad de una heurística. I ' actualizaré mi respuesta.
- @Juho Creo que si uso la fórmula del factor de ramificación, probaré muchos números en el LHS y lo calcularé y verificaré que sea igual con el RHS de la siguiente manera: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 no es igual a T = 17, por lo que debemos probar B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 el resultado cerca de T para que podamos probar B = 2.1 y así sucesivamente hasta alcanzar el resultado T !!!! Creo que esta fórmula puede usarse así :))))