En ciencias de la computación , B * (pronunciado "B estrella") es un algoritmo de búsqueda de gráfico del mejor primero 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 * .
Resumen
El algoritmo almacena intervalos para los nodos del árbol en contraposición a las estimaciones valoradas en un solo punto. 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".
Detalles
Evaluaciones de intervalo en lugar de estimaciones
Los nodos de hoja de un árbol B * reciben evaluaciones que son intervalos en lugar de números únicos. Se supone que el intervalo contiene el valor real de ese nodo. Si todos los intervalos adjuntos a los nodos hoja satisfacen esta propiedad, entonces B * identificará una ruta óptima al estado objetivo.
Proceso de copia de seguridad
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.
Terminación de la búsqueda
B * expande sistemáticamente los nodos para crear una "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 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 los recursos. Por lo tanto, el algoritmo normalmente se aumenta con criterios de terminación artificiales, como límites de tiempo o memoria. Cuando se alcanza un límite artificial, debe realizar 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.
Expansión
B * es un proceso del mejor primero, lo que significa que es muy eficiente atravesar el árbol, descendiendo repetidamente para encontrar una hoja para expandir. Esta sección describe cómo elegir el nodo para expandir. (Nota: si el árbol es residente en memoria o no, es una función de la eficiencia general de la implementación, incluida la forma en que se puede asignar 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 demostrar lo mejor y refutar-descansar. En la estrategia de demostrar mejor, el algoritmo selecciona el nodo asociado con el límite superior más alto. La esperanza es que la expansión de ese nodo eleve su límite inferior más alto que el límite superior de cualquier otro nodo.
La estrategia refutar-reposo selecciona al hijo de la raíz que tiene el segundo límite superior más alto. La esperanza es que al expandir ese nodo pueda reducir el límite superior a menos que el límite inferior del mejor hijo.
Selección de estrategia
Tenga en cuenta que aplicar la estrategia refutar-reposo 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 brindó más orientación sobre qué estrategia seleccionar. Hay varias alternativas razonables, como ampliar la opción que tiene el árbol más pequeño.
Selección de estrategia en nodos no raíz
Una vez que se ha seleccionado un hijo de la raíz (usando probar-mejor o refutar-descansar), el algoritmo desciende a un nodo hoja seleccionando repetidamente el hijo que tiene el límite superior más alto.
Cuando se alcanza un nodo hoja, el algoritmo genera todos los nodos sucesores y les asigna intervalos utilizando la función de evaluación. Luego, los intervalos de todos los nodos deben respaldarse mediante la operación de respaldo.
Cuando las transposiciones son posibles, es posible que la operación de respaldo deba alterar los valores de los nodos que no se encontraban en la ruta de selección. En este caso, el algoritmo necesita indicadores de los niños 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 respaldo no cambia el intervalo asociado con un nodo.
Robustez
Si los intervalos son incorrectos (en el sentido de que el valor teórico del juego 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 robusto 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 termina 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, borrando eventualmente todos los errores.
Extensión a juegos de dos jugadores
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 está moviendo y el mínimo si el oponente se está moviendo. De manera equivalente, puede representar todos los intervalos desde la perspectiva del lado que se moverá y luego negar los valores durante la operación de respaldo.
Aplicaciones
Andrew Palay aplicó B * al ajedrez. Las evaluaciones de los puntos finales se asignaron mediante la realización de búsquedas de movimiento nulo. 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 (Scrabble) aplicó la búsqueda B * a los finales. Las evaluaciones de los puntos finales se asignaron mediante 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.
Ver también
Referencias
- Berliner, Hans (1979). "El algoritmo de búsqueda de árbol B *. Un procedimiento de prueba mejor-primero" . Inteligencia artificial . 12 (1): 23–40. doi : 10.1016 / 0004-3702 (79) 90003-1 .
- Russell, SJ; Norvig, P. (2003). Inteligencia artificial: un enfoque moderno . Upper Saddle River, Nueva Jersey: Prentice Hall. pag. 188. ISBN 0-13-790395-2.
- Sheppard, Brian (2002). "Scrabble de calibre de campeonato mundial" . Inteligencia artificial . 134 (1–2): 241–275. doi : 10.1016 / S0004-3702 (01) 00166-7 .