En informática , B* (pronunciado "B estrella") es un algoritmo de búsqueda de grafos que busca el mejor primero y que encuentra la ruta de menor costo desde un nodo inicial dado hasta cualquier nodo objetivo (de uno o más objetivos posibles). Publicado por primera vez por Hans Berliner en 1979, está relacionado con el algoritmo de búsqueda A* .
El algoritmo almacena intervalos para los nodos del árbol en lugar de estimaciones puntuales. Luego, se pueden buscar los nodos de hoja del árbol hasta que uno de los nodos de nivel superior tenga un intervalo que sea claramente "mejor".
A los nodos de hoja de un árbol B* se les asignan evaluaciones que son intervalos en lugar de números individuales. Se supone que el intervalo contiene el valor verdadero de ese nodo. Si todos los intervalos asociados a los nodos de hoja satisfacen esta propiedad, entonces B* identificará una ruta óptima hacia el estado objetivo.
Para realizar una copia de seguridad de los intervalos dentro del árbol, el límite superior de un padre se establece en el máximo de los límites superiores de los hijos. El límite inferior de un padre se establece en el máximo del límite inferior de los hijos. Tenga en cuenta que diferentes hijos pueden proporcionar estos límites.
B* expande sistemáticamente los nodos para crear "separación", lo que ocurre cuando el límite inferior de un hijo directo de la raíz es al menos tan grande como el límite superior de cualquier otro hijo directo de la raíz. Un árbol que crea separación en la raíz contiene una prueba de que el mejor hijo es al menos tan bueno como cualquier otro hijo.
En la práctica, las búsquedas complejas pueden no terminar dentro de los límites prácticos de recursos. Por lo tanto, el algoritmo normalmente se complementa con criterios de terminación artificiales, como límites de tiempo o de memoria. Cuando se alcanza un límite artificial, entonces debe realizar un juicio heurístico sobre qué movimiento seleccionar. Normalmente, el árbol le proporcionará evidencia extensa, como los intervalos de los nodos raíz.
B* es un proceso que prioriza lo mejor, lo que significa que es muy eficiente recorrer el árbol, descendiendo repetidamente para encontrar una hoja que expandir. Esta sección describe cómo elegir el nodo que se expandirá. (Nota: el hecho de que el árbol resida o no en la memoria es una función de la eficiencia general de la implementación, incluida la forma en que se puede mapear y/o administrar a través de la memoria real o virtual).
En la raíz del árbol, el algoritmo aplica una de dos estrategias, llamadas probar-mejor y refutar-resto. En la estrategia probar-mejor, el algoritmo selecciona el nodo asociado con el límite superior más alto. La esperanza es que al expandir ese nodo, su límite inferior aumente más que el límite superior de cualquier otro nodo.
La estrategia de refutación y descanso selecciona el hijo de la raíz que tiene el segundo límite superior más alto. La esperanza es que al expandir ese nodo, se pueda reducir el límite superior a un valor menor que el límite inferior del mejor hijo.
Tenga en cuenta que aplicar la estrategia de refutación-resto no tiene sentido hasta que el límite inferior del nodo secundario que tiene el límite superior más alto sea el más alto entre todos los límites inferiores.
La descripción del algoritmo original no brindaba más orientación sobre qué estrategia elegir. Existen varias alternativas razonables, como ampliar la opción que tiene el árbol más pequeño.
Una vez que se ha seleccionado un hijo de la raíz (usando prove-best o disprove-rest), el algoritmo desciende a un nodo hoja seleccionando repetidamente al hijo que tiene el límite superior más alto.
Cuando se alcanza un nodo de hoja, el algoritmo genera todos los nodos sucesores y les asigna intervalos mediante la función de evaluación. Luego, se deben realizar copias de seguridad de los intervalos de todos los nodos mediante la operación de copia de seguridad.
Cuando las transposiciones son posibles, la operación de copia de seguridad puede necesitar modificar los valores de los nodos que no se encuentran en la ruta de selección. En este caso, el algoritmo necesita punteros de los hijos a todos los padres para que los cambios se puedan propagar. Tenga en cuenta que la propagación puede cesar cuando una operación de copia de seguridad no cambia el intervalo asociado con un nodo.
Si los intervalos son incorrectos (en el sentido de que el valor teórico de juegos del nodo no está contenido dentro del intervalo), entonces B* podría no ser capaz de identificar la ruta correcta. Sin embargo, el algoritmo es bastante resistente a los errores en la práctica.
El programa Maven (Scrabble) tiene una innovación que mejora la robustez de B* cuando es posible que se produzcan errores de evaluación. Si una búsqueda finaliza debido a una separación, Maven reinicia la búsqueda después de ampliar todos los intervalos de evaluación en una pequeña cantidad. Esta política amplía progresivamente el árbol y, finalmente, borra todos los errores.
El algoritmo B* se aplica a juegos de suma cero deterministas de dos jugadores. De hecho, el único cambio es interpretar "mejor" con respecto al lado que se mueve en ese nodo. Por lo tanto, tomaría el máximo si su lado se mueve y el mínimo si el oponente se mueve. De manera equivalente, puede representar todos los intervalos desde la perspectiva del lado que se mueve y luego negar los valores durante la operación de copia de seguridad.
Andrew Palay aplicó B* al ajedrez. Las evaluaciones de puntos finales se asignaron realizando búsquedas de movimientos nulos. No hay informes sobre el rendimiento de este sistema en comparación con los motores de búsqueda de poda alfa-beta que se ejecutan en el mismo hardware.
El programa Maven (Scrabble) aplicó la búsqueda B* a los finales. Las evaluaciones de los puntos finales se asignaron utilizando un sistema de planificación heurística.
El algoritmo de búsqueda B* se ha utilizado para calcular la estrategia óptima en un juego de suma de un conjunto de juegos combinatorios.