En informática , B* (pronunciado "Bee Star" ) es un algoritmo de búsqueda de gráficos que utiliza la búsqueda de la mejor primera coincidencia que encuentra la ruta menos costosa desde un nodo de inicio dado a cualquier nodo de destino (de uno o más destinos posibles) . Publicado por primera vez por Hans Berliner en 1979, está relacionado con el algoritmo de búsqueda A* .
El algoritmo conserva los intervalos para los nodos del árbol , en contraste con las estimaciones de un solo valor. Los nodos de hoja del árbol se pueden buscar hasta que uno de los nodos de nivel superior tenga un intervalo que sea claramente el mejor .
Los nodos hoja del árbol B* reciben puntuaciones que son intervalos en lugar de números individuales. Se supone que el intervalo contiene el valor verdadero de este nodo. Si todos los intervalos adjuntos a los nodos hoja satisfacen esta propiedad, entonces B* determinará la ruta óptima hacia el estado objetivo.
Para realizar una copia de seguridad de los intervalos en un árbol, el límite superior del ancestro se establece en los límites superiores máximos de los descendientes. El límite inferior del antepasado se establece igual al máximo del límite inferior de los descendientes. Tenga en cuenta que estos límites pueden ser proporcionados por diferentes niños.
B* expande los nodos sistemáticamente para crear una división , que ocurre cuando el límite inferior del descendiente directo de la raíz no es menor que el límite superior de cualquier otro descendiente directo de la raíz. El árbol que crea una división en la raíz contiene la 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 se completen dentro de las limitaciones prácticas de recursos. Por lo tanto, el algoritmo generalmente se aumenta con criterios de terminación artificial, como restricciones de tiempo o memoria. Cuando se alcanza un límite artificial, se debe hacer un juicio heurístico sobre qué movimiento tomar. Por lo general, el árbol proporciona evidencia amplia, como intervalos de nodo raíz.
B* es un proceso de búsqueda de la primera mejor coincidencia , lo que significa que es muy eficiente para atravesar el árbol, bajando muchas veces para encontrar la hoja para expandir. Esta sección describe cómo seleccionar un nodo para expandir. ( Nota : si un árbol reside en la memoria depende de la eficiencia general de la implementación, incluida la forma en que se puede mapear y/o manipular a través de la memoria real o virtual ).
En la raíz del árbol, el algoritmo aplica una de dos estrategias: probar lo mejor y refutar el resto . En la estrategia probar mejor , el algoritmo selecciona el nodo asociado con el límite superior más alto. Se espera que la expansión de este nodo eleve su límite inferior más alto que el límite superior de cualquier otro nodo.
La estrategia de refute rest selecciona el hijo de la raíz que tiene el segundo límite superior más alto. Se espera que al expandir este nodo, se pueda reducir el límite superior a un valor que sea menor que el límite inferior del mejor hijo.
Elección de la estrategiaCabe señalar que la estrategia de refutar el resto no tiene sentido hasta que el límite inferior del nodo descendiente con el límite superior más alto se convierte en el más alto entre todos los límites inferiores.
En la descripción original del algoritmo, no había más orientación sobre qué estrategia elegir. Existen algunas alternativas razonables, como ampliar la selección con un árbol más pequeño.
Elección de estrategia en nodos no raízUna vez que se ha elegido un hijo de la raíz (utilizando el método de probar mejor o refutar el resto ), el algoritmo desciende hasta el nodo final, eligiendo repetidamente el hijo que tiene el límite superior más alto.
Cuando se alcanza un nodo hoja, el algoritmo genera todos los nodos posteriores y les asigna intervalos mediante la función de puntuación. Luego, debe realizar una copia de seguridad de los intervalos de todos los nodos mediante la operación de copia de seguridad.
Cuando las transposiciones son posibles, es posible que se requiera una operación de respaldo para cambiar los valores de los nodos que no se encuentran en la ruta de selección. En este caso, el algoritmo necesita punteros de los descendientes a todos los ancestros para que los cambios puedan propagarse. Tenga en cuenta que la propagación puede detenerse si la operación de respaldo no cambia el intervalo asociado con el nodo.
Si los intervalos son incorrectos (en el sentido de que el valor teórico del juego del nodo no está contenido en el intervalo), es posible que B* no pueda determinar la ruta correcta. Sin embargo, en la práctica, el algoritmo es bastante robusto a los errores.
Hay una innovación en el programa Maven que mejora la confiabilidad de B* cuando los errores de evaluación son posibles. Si la búsqueda se detiene debido a una división, Maven reinicia la búsqueda después de una ligera expansión de todos los intervalos de evaluación. Esta política expande gradualmente el árbol y eventualmente borra todos los errores.
El algoritmo B* se aplica a juegos deterministas de suma cero para dos jugadores. De hecho, el único cambio es la interpretación de lo mejor en relación con el lado que se mueve en este nodo. Por lo tanto, debes tomar el máximo si tu lado se está moviendo y el mínimo si el oponente se está moviendo. De manera similar, puede representar todos los intervalos en términos del lado que se moverá y luego invertir los valores durante la operación de copia de seguridad.
Andrew Palai aplicó B* al ajedrez . Las puntuaciones finales se asignaron realizando una búsqueda de desplazamiento cero. No hay ningún informe 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 aplicó la búsqueda B* al final del juego . Las puntuaciones finales se asignaron utilizando un sistema de programación heurística.
Se utilizó el algoritmo de búsqueda B* para calcular la estrategia óptima en el juego de suma de un conjunto de juegos combinatorios.