En satisfacción de restricciones , unos híbridos algoritmo resuelve un problema de satisfacción de restricciones por la combinación de dos métodos diferentes, por ejemplo variable de acondicionado ( backtracking , backjumping , etc.) y la inferencia restricción ( consistencia de arco , eliminación variables , etc.)
Los algoritmos híbridos explotan las buenas propiedades de diferentes métodos aplicándolos a problemas que pueden resolver de manera eficiente. Por ejemplo, la búsqueda es eficiente cuando el problema tiene muchas soluciones, mientras que la inferencia es eficiente para demostrar la insatisfacción de problemas con restricciones excesivas.
Inferencia de conjunto de ciclos / algoritmo de búsqueda
Este algoritmo híbrido se basa en ejecutar la búsqueda sobre un conjunto de variables y la inferencia sobre las demás. En particular, el retroceso o alguna otra forma de búsqueda se ejecuta sobre una serie de variables; siempre que se encuentra una asignación parcial consistente sobre estas variables, se ejecuta una inferencia sobre las variables restantes para verificar si esta asignación parcial se puede extender para formar una solución.
En algunos tipos de problemas, existen algoritmos de inferencia completos y eficientes. Por ejemplo, los problemas cuyos gráficos primarios o duales son árboles o bosques pueden resolverse en tiempo polinomial. Esto afecta la elección de las variables evaluadas por búsqueda. De hecho, una vez que se evalúa una variable, se puede eliminar de manera efectiva del gráfico, restringiendo todas las restricciones que está involucrada con su valor. Alternativamente, una variable evaluada puede ser reemplazada por varias variables distintas, una para cada restricción, todas con un dominio de valor único.
Este algoritmo mixto es eficiente si las variables de búsqueda se eligen de modo que duplicarlas o eliminarlas convierta el problema en uno que pueda resolverse eficientemente por inferencia. En particular, si estas variables forman un corte cíclico de la gráfica del problema, la inferencia es eficiente porque tiene que resolver un problema cuya gráfica es un árbol o, más generalmente, un bosque . Dicho algoritmo es el siguiente:
encontrar un corte de ciclo de la gráfica del problemaejecutar la búsqueda en las variables del cutset cuando se encuentra una asignación parcial consistente a todas las variables, reemplace cada variable del cutset con una nueva variable para cada restricción; establecer los dominios de estas nuevas variables al valor de la antigua variable en la asignación parcial resolver el problema usando inferencia
La eficiencia de este algoritmo depende de dos factores contrastantes. Por un lado, cuanto menor sea el cutset, menor será el subproblema a resolver mediante la búsqueda; dado que la inferencia es eficiente en árboles, la búsqueda es la parte que afecta principalmente a la eficiencia. Por otro lado, encontrar un cutset de tamaño mínimo es un problema difícil. Como resultado, se puede usar un conjunto de corte de ciclo pequeño en lugar de uno mínimo.
Otra alternativa para reducir el tiempo de ejecución de la búsqueda es colocar más carga en la parte de inferencia. En particular, la inferencia puede ser relativamente eficiente incluso si el gráfico del problema no es un bosque, sino un gráfico de pequeño ancho inducido. Esto se puede explotar haciendo una búsqueda en un conjunto de variables que no es un corte de ciclo pero deja el problema, una vez eliminado, para tener un ancho inducido limitado por algún valor. [ aclaración necesaria ] Este conjunto de variables se denomina-conjunto del problema.
El ancho inducido de un gráfico después de eliminar un conjunto de variables se denomina ancho inducido ajustado . Por lo tanto, el ancho inducido ajustado en relación con un cutset es siempre . Encontrar un tamaño mínimo-El corte es en general duro. Sin embargo, un-cutset de tamaño no mínimo se puede encontrar fácilmente para un orden fijo de las variables. En particular, tal corte dejará un gráfico restante de ancho delimitado por de acuerdo con ese orden particular de las variables.
El algoritmo para encontrar tal conjunto de cortes procede imitando el procedimiento para encontrar la gráfica inducida de un problema de acuerdo con el orden considerado de las variables (este procedimiento procede del último nodo en el orden al primero, agregando un borde entre cada par de padres desconectados de cada nodo). Siempre que este procedimiento encuentre o haga que un nodo tenga más depadres, el nodo se elimina del gráfico y se agrega al conjunto de cortes. Por definición, el gráfico resultante no contiene ningún nodo de ancho mayor que, y el conjunto de nodos eliminados es, por tanto, un -cutset.
Una alternativa al uso de este algoritmo es permitir que la búsqueda evalúe las variables, pero verifique en cada paso si el gráfico restante es un bosque y ejecute una inferencia si este es el caso. En otras palabras, en lugar de buscar un conjunto de variables al principio y usarlas solo durante la búsqueda, el algoritmo comienza como una búsqueda normal; en cada paso, si las variables asignadas forman uncorte del problema, se ejecuta la inferencia para comprobar la satisfacibilidad. Esto es factible porque verificar si un conjunto dado de nodos es uncutset para un fijo es un problema polinomial.
Algoritmo híbrido de descomposición de árboles
Otro algoritmo híbrido de búsqueda / inferencia funciona en la descomposición del árbol . En general, un problema de satisfacción de restricciones se puede resolver creando primero una descomposición de árbol y luego utilizando un algoritmo especializado.
Uno de estos algoritmos se basa en la propagación de restricciones entre los nodos y luego en la resolución del subproblema en cada nodo. Esta propagación consiste en crear nuevas restricciones que representan los efectos de las restricciones en un nodo sobre un nodo unido. Más precisamente, si se unen dos nodos, comparten variables. Las evaluaciones permitidas de estas variables de acuerdo con las restricciones del primer nodo indican cómo el primer nodo afecta las variables del segundo nodo. El algoritmo funciona creando la restricción satisfecha por estas evaluaciones e incorporando esta nueva restricción en el segundo nodo.
Cuando todas las restricciones se han propagado de las hojas a la raíz y de regreso a la raíz, todos los nodos contienen todas las restricciones que son relevantes para ellos. Por tanto, el problema puede resolverse en cada nodo.
Un enfoque híbrido puede ser tomada por el uso de eliminación variables para la creación de las nuevas restricciones que se propagan dentro de los nodos, y un algoritmo de búsqueda (como la vuelta hacia atrás , backjumping , búsqueda local ) en cada nodo individual.
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7.