En informática , B* (pronunciado "B estrella") es un algoritmo de búsqueda de gráfico mejor primero que encuentra la ruta de menor costo desde un nodo inicial dado a 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 de un solo punto. Luego, los nodos hoja del árbol pueden buscarse hasta que uno de los nodos de nivel superior tenga un intervalo que sea claramente "mejor".
Los nodos hoja de un árbol B* reciben evaluaciones que son intervalos en lugar de números únicos. Se supone que el intervalo contiene el verdadero valor de ese nodo. Si todos los intervalos adjuntos a los nodos hoja satisfacen esta propiedad, entonces B* identificará un camino óptimo hacia el estado objetivo.
Para hacer 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 niños pueden proporcionar estos límites.
B* expande sistemáticamente los nodos para crear una "separación", que ocurre cuando el límite inferior de un elemento secundario directo de la raíz es al menos tan grande como el límite superior de cualquier otro elemento secundario directo de la raíz. Un árbol que crea separación en la raíz contiene una prueba de que el mejor niño es al menos tan bueno como cualquier otro niño.
En la práctica, es posible que las búsquedas complejas no terminen dentro de los límites prácticos de recursos. Por lo tanto, el algoritmo normalmente se aumenta con criterios de terminación artificial, como límites de tiempo o memoria. Cuando se alcanza un límite artificial, debe hacer un juicio heurístico sobre qué movimiento seleccionar. Normalmente, el árbol le proporcionaría una amplia evidencia, como los intervalos de los nodos raíz.