B * (pronunciado "estrella B") es el mejor algoritmo de búsqueda de gráficos 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 * .
Resumen [ editar ]
El algoritmo almacena intervalos para los nodos del árbol en lugar de las estimaciones con valores 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 "el mejor".
Detalles [ editar ]
Evaluaciones de intervalo en lugar de estimaciones [ editar ]
Los nodos de hoja de un árbol B * reciben evaluaciones que son intervalos en lugar de números individuales. Se supone que el intervalo contiene el verdadero valor de ese nodo. Si todos los intervalos adjuntos a los nodos hoja satisfacen esta propiedad, B * identificará una ruta óptima hacia el estado objetivo.
Proceso de copia de seguridad [ editar ]
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 elementos secundarios pueden proporcionar estos límites.
Terminación de la búsqueda [ editar ]
B * expande sistemáticamente los nodos para crear una "separación", 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 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 pruebas exhaustivas, como los intervalos de los nodos raíz.
Expansión [ editar ]
B * es el mejor proceso, lo que significa que es muy eficiente atravesar el árbol, descendiendo repetidamente para encontrar una hoja para expandirse. Esta sección describe cómo elegir el nodo para expandir. (Nota: si el árbol reside 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-descansar. En la estrategia de probar mejor, el algoritmo selecciona el nodo asociado con el límite superior más alto. La esperanza es que expandir ese nodo elevará su límite inferior más alto que el límite superior de cualquier otro nodo.
La estrategia de refutar-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 podría reducir el límite superior a menos que el límite inferior del mejor hijo.
Selección de estrategia [ editar ]
Tenga en cuenta que aplicar la estrategia de refutar-descansar no tiene sentido hasta que el límite inferior del nodo secundario que tiene el límite superior más alto es el más alto entre todos los límites inferiores.
La descripción original del algoritmo no dio ninguna guía adicional sobre qué estrategia seleccionar. Hay varias alternativas razonables, como expandir la opción que tiene el árbol más pequeño.
Selección de estrategia en nodos no raíz [ editar ]
Una vez que se ha seleccionado un elemento secundario de la raíz (utilizando probar-mejor o refutar-mejor), el algoritmo desciende a un nodo hoja seleccionando repetidamente el elemento secundario 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 mediante la función de evaluación. Luego, los intervalos de todos los nodos deben ser respaldados usando la operación de respaldo.
Cuando son posibles las transposiciones, entonces la operación de respaldo puede necesitar alterar los valores de los nodos que no se encuentran en la ruta de selección. En este caso, el algoritmo necesita punteros de los niños a todos los padres para que los cambios puedan propagarse. Tenga en cuenta que la propagación puede cesar cuando una operación de respaldo no cambia el intervalo asociado con un nodo.
Robustez [ editar ]
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 son posibles errores de evaluación. Si una búsqueda termina debido a la 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 [ editar ]
El algoritmo B * se aplica a los juegos deterministas de suma cero de dos jugadores. De hecho, el único cambio es interpretar "mejor" con respecto al lado que se mueve en ese nodo. Entonces tomarías el máximo si tu 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 a mover, y luego negar los valores durante la operación de respaldo.
Aplicaciones [ editar ]
Andrew Palay aplicó B * al ajedrez. Las evaluaciones de punto final se asignaron realizando búsquedas de movimiento nulo. No se informa qué tan bien funcionó 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 punto final 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.
Backtracking es un algoritmo general para encontrar todas (o algunas) soluciones a algunos problemas computacionales , en particular problemas de satisfacción de restricciones , que aumenta gradualmente a los candidatos a las soluciones y abandona a un candidato ("backtracks") tan pronto como determina que el candidato no puede ser completado a una solución válida. [1] [2]
El ejemplo clásico de libros de texto del uso del retroceso es el rompecabezas de las ocho reinas , que pide todos los arreglos de ocho reinas de ajedrez en un tablero de ajedrez estándar para que ninguna reina ataque a ningún otro. En el enfoque común de retroceso, los candidatos parciales son arreglos de k reinas en las primeras k filas del tablero, todas en diferentes filas y columnas. Cualquier solución parcial que contenga dos reinas que se ataquen mutuamente puede ser abandonada.
El retroceso se puede aplicar solo para problemas que admiten el concepto de una "solución candidata parcial" y una prueba relativamente rápida de si posiblemente se puede completar con una solución válida. Es inútil, por ejemplo, para localizar un valor dado en una tabla desordenada. Sin embargo, cuando es aplicable, el retroceso es a menudo mucho más rápido que la enumeración de la fuerza bruta de todos los candidatos completos, ya que puede eliminar una gran cantidad de candidatos con una sola prueba.
El retroceso es una herramienta importante para resolver problemas de satisfacción de restricciones , [3] como crucigramas , aritmética verbal , sudoku y muchos otros acertijos. A menudo es la técnica más conveniente (si no la más eficiente [ cita requerida ] ) para analizar , [4] para el problema de la mochila y otros problemas de optimización combinatoria . También es la base de los llamados lenguajes de programación lógica , como Icon , Planner y Prolog .
El seguimiento depende de los " procedimientos de recuadro negro " proporcionados por el usuario que definen el problema a resolver, la naturaleza de los candidatos parciales y cómo se extienden a candidatos completos. Por lo tanto, es un algoritmo metaheurístico en lugar de específico, aunque, a diferencia de muchas otras metaheurísticas, está garantizado que encontrará todas las soluciones a un problema finito en un período de tiempo limitado.
El término "retroceso" fue acuñado por el matemático estadounidense DH Lehmer en la década de 1950. [5] El lenguaje pionero de procesamiento de cadenas SNOBOL (1962) puede haber sido el primero en proporcionar una función de retroceso general incorporada.
Descripción del método [ editar ]
El algoritmo de retroceso enumera un conjunto de candidatos parciales que, en principio, podrían completarse de varias maneras para dar todas las soluciones posibles al problema dado. La finalización se realiza de forma incremental, mediante una secuencia de pasos de extensión candidatos.
Conceptualmente, los candidatos parciales se representan como los nodos de una estructura de árbol , el árbol de búsqueda potencial. Cada candidato parcial es el padre de los candidatos que difieren de él en un solo paso de extensión; Las hojas del árbol son los candidatos parciales que no se pueden extender más.
El algoritmo de retroceso atraviesa este árbol de búsqueda de forma recursiva , desde la raíz hacia abajo, en primer orden de profundidad . En cada nodo c , el algoritmo verifica si c puede completarse con una solución válida. Si no puede, se omite ( poda ) todo el subárbol enraizado en c . De lo contrario, el algoritmo (1) verifica si c es una solución válida y, de ser así, lo informa al usuario; y (2) enumera recursivamente todos los subárboles de c . Las dos pruebas y los elementos secundarios de cada nodo se definen mediante procedimientos proporcionados por el usuario.
Por lo tanto, el árbol de búsqueda real que atraviesa el algoritmo es solo una parte del árbol potencial. El costo total del algoritmo es el número de nodos del árbol real multiplicado por el costo de obtener y procesar cada nodo. Este hecho debe considerarse al elegir el árbol de búsqueda potencial e implementar la prueba de poda.
Pseudocódigo [ editar ]
Para aplicar el seguimiento a una clase específica de problemas, uno debe proporcionar los datos P para la instancia particular del problema que se va a resolver, y seis parámetros de procedimiento , raíz , rechazar , aceptar , primero , siguiente y salida . Estos procedimientos deben tomar los datos de instancia P como parámetro y deben hacer lo siguiente:
- root ( P ): devuelve el candidato parcial en la raíz del árbol de búsqueda.
- rechazar ( P , c ): devuelve verdadero solo si no vale la pena completar el candidato parcial c .
- aceptar ( P , c ): devuelve verdadero si c es una solución de P , y falso de lo contrario.
- primero ( P , c ): genera la primera extensión del candidato c .
- next ( P , s ): genera la próxima extensión alternativa de un candidato, después de la extensión s .
- salida ( P , c ): use la solución c de P , según corresponda a la aplicación.
El algoritmo de retroceso reduce el problema a la llamada bt ( raíz ( P )), donde bt es el siguiente procedimiento recursivo:
Consideraciones de uso [ editar ]
El rechazar procedimiento debe ser una función booleana de valor que devuelve verdadero si bien es cierto que no es posible la extensión de c es una solución válida para P . Si el procedimiento no puede llegar a una conclusión definitiva, debe devolver falso . Un resultado verdadero incorrecto puede hacer que el procedimiento bt pierda algunas soluciones válidas. El procedimiento puede suponer que el rechazo ( P , t ) devuelve falso para cada antecesor t de c en el árbol de búsqueda.
Por otro lado, la eficiencia del algoritmo de retroceso depende de que el rechazo devuelva verdadero para los candidatos que estén lo más cerca posible de la raíz. Si el rechazo siempre devuelve falso , el algoritmo aún encontrará todas las soluciones, pero será equivalente a una búsqueda de fuerza bruta.
El procedimiento de aceptación debe devolver verdadero si c es una solución completa y válida para la instancia de problema P , y falso de lo contrario. Se puede suponer que el candidato parcial c y todos sus antepasados en el árbol han pasado la prueba de rechazo .
El pseudocódigo general anterior no supone que las soluciones válidas sean siempre hojas del árbol de búsqueda potencial. En otras palabras, admite la posibilidad de que una solución válida para P pueda extenderse aún más para producir otras soluciones válidas.
El algoritmo de retroceso utiliza el primer y el siguiente procedimiento para enumerar los elementos secundarios de un nodo c del árbol, es decir, los candidatos que difieren de c en un solo paso de extensión. La llamada primero ( P , c ) debería producir el primer hijo de c , en algún orden; y la siguiente llamada ( P , s ) debería devolver el siguiente hermano del nodo s , en ese orden. Ambas funciones deben devolver un candidato distintivo "NULL", si el niño solicitado no existe.
Juntas, las funciones raíz , primera y siguiente definen el conjunto de candidatos parciales y el árbol de búsqueda potencial. Deben elegirse de modo que cada solución de P ocurra en algún lugar del árbol, y no se presente un candidato parcial más de una vez. Además, deben admitir un predicado de rechazo eficiente y efectivo .
Variantes de parada temprana [ editar ]
El pseudocódigo anterior llamará a la salida para todos los candidatos que sean una solución para la instancia P dada . El algoritmo puede modificarse para detenerse después de encontrar la primera solución, o un número específico de soluciones; o después de probar un número específico de candidatos parciales, o después de pasar una cantidad determinada de tiempo de CPU .
Ejemplos [ editar ]
Los ejemplos en los que se puede utilizar el seguimiento para resolver acertijos o problemas incluyen:
- Rompecabezas como el de ocho reinas , crucigramas , aritmética verbal , Sudoku [nb 1] y Solitario Peg .
- Problemas de optimización combinatoria , como el análisis y el problema de la mochila .
- Lenguajes de programación lógicos como Icon , Planner y Prolog , que utilizan backtracking internamente para generar respuestas.
El siguiente es un ejemplo en el que se utiliza el retroceso para el problema de satisfacción de restricciones :
Restricción de satisfacción [ editar ]
El problema general de satisfacción de restricciones consiste en encontrar una lista de enteros x = ( x [1], x [2], ..., x [ n ]) , cada uno en un rango {1, 2, ..., m }, que satisfaga algunos restricción arbitraria (función booleana) F .
Para esta clase de problemas, el de datos de instancia P sería los números enteros m y n , y el predicado F . En una solución de retroceso típica para este problema, se podría definir un candidato parcial como una lista de enteros c = ( c [1], c [2], ..., c [k]) , para cualquier k entre 0 y n , que deben asignarse a las primeras k variables x [1], x [2], ..., x [ k ] . El candidato raíz sería la lista vacía (). El primero ylos siguientes procedimientos serían entonces
Aquí la longitud ( c ) es el número de elementos en la lista c .
El rechazo de llamada ( P , c ) debería devolver verdadero si la restricción F no puede ser satisfecha por ninguna lista de n enteros que comience con los k elementos de c . Para que el seguimiento sea efectivo, debe haber una forma de detectar esta situación, al menos para algunos candidatos c , sin enumerar todos esos m n - k n -tuplas.
Por ejemplo, si F es la conjunción de varios predicados booleanos, F = F [1] ∧ F [2] ∧… ∧ F [ p ] , y cada F [ i ] depende solo de un pequeño subconjunto de las variables x [1 ], ..., x [ n ] , entonces el procedimiento de rechazo podría simplemente verificar los términos F [ i ] que dependen solo de las variables x [1], ..., x [ k ] , y devolver verdaderosi alguno de esos términos devuelve falso . De hecho, rechazar solo necesita verificar aquellos términos que dependen de x [ k ], ya que los términos que dependen solo de x [1], ..., x [ k - 1] se habrán probado más arriba en el árbol de búsqueda.
Suponiendo que el rechazo se implemente como se indicó anteriormente, entonces aceptar ( P , c ) solo necesita verificar si c está completo, es decir, si tiene n elementos.
En general, es mejor ordenar la lista de variables para que comience con las más críticas (es decir, las que tienen menos opciones de valor o que tienen un mayor impacto en las elecciones posteriores).
También se podría permitir que la siguiente función elija qué variable se debe asignar al extender un candidato parcial, en función de los valores de las variables que ya ha asignado. Se pueden obtener mejoras adicionales mediante la técnica de propagación de restricciones .
Además de retener los valores mínimos de recuperación utilizados en la copia de seguridad, las implementaciones de seguimiento normalmente mantienen un rastro variable para registrar el historial de cambios de valor. Una implementación eficiente evitará crear una entrada de camino variable entre dos cambios sucesivos cuando no haya un punto de elección, ya que el retroceso borrará todos los cambios como una sola operación.
Una alternativa al rastro variable es mantener una marca de tiempo de cuándo se realizó el último cambio en la variable. La marca de tiempo se compara con la marca de tiempo de un punto de elección. Si el punto de elección tiene un tiempo asociado posterior al de la variable, no es necesario revertir la variable cuando el punto de elección se retrocede, ya que se cambió antes de que ocurriera el punto de elección.
No hay comentarios:
Publicar un comentario