Los algoritmos de búsqueda de problemas de satisfacción de restricciones al final del día tienen una interpretación bastante intuitiva. Esencialmente, todo lo que está intentando hacer es buscar alguna asignación de variables hasta que se cumplan todas las restricciones del problema.
Veamos algunos algoritmos que resuelven este problema:
- DFS / BFS / A * La búsqueda se puede utilizar técnicamente para resolver estos problemas, pero no son particularmente eficientes. ¿Por qué? Bueno, lo que termina sucediendo si prueba este tipo de algoritmos de búsqueda es que termina expandiendo estados que ya han violado una restricción en su problema. En el ejemplo clásico de coloración de mapas en CSP, lo que termina sucediendo es que continúa tratando de encontrar una solución en estados que ya tienen dos nodos adyacentes con el mismo color, lo cual es una búsqueda inútil, ya que ya violó una restricción. Entonces haces mucho trabajo innecesario. Estos métodos no terminan siendo realmente mejores que la búsqueda de fuerza bruta.
- Búsqueda de retroceso: este algoritmo es el algoritmo de búsqueda desinformado más básico para los CSP. Primero apuntamos a resolver el problema que tienen DFS / BFS / A * básicamente verificando las restricciones a medida que avanzamos en nuestra búsqueda. Entonces, en el momento en que nos encontramos con un estado que viola una restricción, no expandimos más y “retrocedemos”. En términos de un ejemplo, al resolver el ejemplo de coloreado del mapa, podría encontrarse con un estado con dos nodos adyacentes con el mismo color, pero luego irá a otra rama del árbol de búsqueda en lugar de continuar expandiendo este nodo.
- Verificación de avance / Consistencia de arco: la búsqueda de retroceso tiene la propiedad de que continuará expandiendo nodos, hasta que alcance un estado que viole una restricción o satisfaga todas las restricciones, pero ¿qué pasaría si pudiéramos detectar la falla antes? Por ejemplo, en el siguiente mapa, sabemos que ya fallará, pero la búsqueda de retroceso podría expandir algunos nodos más. La verificación directa y los algoritmos de consistencia de arco esencialmente detectan conflictos antes y ahorran algo de tiempo de búsqueda. Tenga en cuenta que la consistencia del arco y la verificación hacia adelante aún usan el retroceso, pero permiten que el retroceso retroceda antes.
- ¿Cuánto tiempo se necesita para leer Introducción a Algoritmos de TH Cormen, para un principiante?
- ¿Dónde puedo obtener el algoritmo de 'Biblioteca de Babel'?
- Cómo encontrar la longitud máxima de la cadena que forma palíndromo en Java
- ¿En qué se diferencia la programación dinámica del seguimiento hacia atrás?
- ¿Cómo se determina la mejor, la media y la peor información dada sobre lo que devuelve un método después del bucle?
- Valor restante mínimo / Valor mínimo de restricción: estas optimizaciones consideran el orden de los nodos que expandimos en nuestra búsqueda. El orden de valor restante mínimo elegirá una variable con la cantidad mínima de valores que quedan en su dominio. Puede pensar en esto como una ordenación que parece esencialmente “fallar rápidamente”. La ordenación de menor valor de restricción elige un valor para una variable que descarta la menor cantidad de valores en las variables restantes. Puede pensar en esto como un pedido que tiene mucho cuidado para evitar futuras violaciones de restricciones. Es importante no saber que resolver esto requiere algún cálculo.
Cuando realmente se resuelven CSP, la mayoría de las veces todos estos algoritmos (excepto DFS, A * y BFS porque son simplemente malos para este tipo de problema) se usan juntos. De hecho, al reunir todos estos algoritmos, los CSP como 1000 reinas se vuelven factibles.
