Algoritmo híbrido (satisfacción de restricciones)

En el ámbito de la inteligencia artificial y la investigación operativa para la satisfacción de restricciones, un algoritmo híbrido resuelve un problema de satisfacción de restricciones mediante la combinación de dos métodos diferentes, por ejemplo, el condicionamiento de variables ( retroceso , salto hacia atrás , etc.) y la inferencia de restricciones ( consistencia de arco , eliminación de variables , etc.).

Los algoritmos híbridos aprovechan las ventajas 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 insatisfacibilidad de problemas con restricciones excesivas.

Este algoritmo híbrido se basa en realizar una búsqueda sobre un conjunto de variables y una inferencia sobre las demás. En concreto, se realiza una búsqueda con retroceso u otro método sobre varias variables; cuando se encuentra una asignación parcial consistente sobre estas variables, se realiza una inferencia sobre las variables restantes para comprobar si esta asignación parcial puede extenderse para formar una solución.

Para ciertos tipos de problemas, existen algoritmos de inferencia eficientes y completos. Por ejemplo, los problemas cuyos grafos primales o duales son árboles o bosques pueden resolverse en tiempo polinomial. Esto influye en la elección de las variables evaluadas durante la búsqueda. De hecho, una vez evaluada una variable, puede eliminarse del grafo, restringiendo así todas las restricciones asociadas a su valor. Alternativamente, una variable evaluada puede reemplazarse por varias variables distintas, una para cada restricción, todas con un dominio de un solo valor.

Este algoritmo mixto es eficiente si las variables de búsqueda se eligen de manera que su duplicación o eliminación convierta el problema en uno que pueda resolverse eficientemente mediante inferencia. En particular, si estas variables forman un conjunto de corte cíclico del grafo del problema, la inferencia es eficiente porque debe resolver un problema cuyo grafo es un árbol o, más generalmente, un bosque . Dicho algoritmo es el siguiente:

encontrar un conjunto de corte de ciclos del grafo del problema realizar búsqueda en las variables del conjunto de corte cuando se encuentra una asignación parcial consistente a todas las variables, reemplazar cada variable del conjunto de corte con una nueva variable para cada restricción; Establezca los dominios de estas nuevas variables al valor de la variable anterior en la asignación parcial. Resuelve el problema usando inferencia

La eficiencia de este algoritmo depende de dos factores contrapuestos. Por un lado, cuanto menor sea el conjunto de corte, menor será el subproblema a resolver mediante la búsqueda; dado que la inferencia es eficiente en árboles, la búsqueda es el factor que más influye en la eficiencia. Por otro lado, encontrar un conjunto de corte de tamaño mínimo es un problema complejo. En consecuencia, puede utilizarse 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 aumentar la carga en la parte de inferencia. En particular, la inferencia puede ser relativamente eficiente incluso si el grafo del problema no es un bosque, sino un grafo de ancho inducido pequeño. Esto se puede aprovechar realizando la búsqueda en un conjunto de variables que no sea un conjunto de corte de ciclos, pero que deje el problema, una vez eliminado, con un ancho inducido limitado por algún valor.${\displaystyle b}$. Dicho conjunto de variables se llama${\displaystyle b}$-conjunto de cortes del problema.

El ancho inducido de un gráfico después de eliminar un conjunto de variables se llama ancho inducido ajustado . Por lo tanto, el ancho inducido ajustado en relación con un${\displaystyle b}$El conjunto de cortes siempre es${\displaystyle b}$. Encontrar un tamaño mínimo${\displaystyle b}$-cutset es generalmente difícil. Sin embargo, un${\displaystyle b}$-un conjunto de corte de tamaño no mínimo se puede encontrar fácilmente para un orden fijo de las variables. En particular, dicho conjunto de corte dejará un grafo restante de ancho acotado por${\displaystyle b}$según ese orden particular de las variables.

El algoritmo para encontrar dicho conjunto de corte procede imitando el procedimiento para encontrar el grafo inducido de un problema según el orden considerado de las variables (este procedimiento procede desde el último nodo en el ordenamiento hasta el primero, agregando una arista entre cada par de padres no conectados de cada nodo). Siempre que este procedimiento encuentre o cree un nodo que tenga más de${\displaystyle b}$padres, el nodo se elimina del grafo y se agrega al conjunto de corte. Por definición, el grafo resultante no contiene ningún nodo de ancho mayor que${\displaystyle b}$y el conjunto de nodos eliminados es, por lo tanto, un${\displaystyle b}$-conjunto de cortes.

Una alternativa al uso de este algoritmo es dejar que la búsqueda evalúe las variables, pero verificar en cada paso si el grafo restante es un bosque y ejecutar la inferencia si este es el caso. En otras palabras, en lugar de encontrar un conjunto de variables al principio y usar solo ellas durante la búsqueda, el algoritmo comienza como una búsqueda regular; en cada paso, si las variables asignadas forman un${\displaystyle b}$corte del problema, se ejecuta una inferencia para comprobar la satisfacibilidad. Esto es factible porque comprobar si un conjunto dado de nodos es un${\displaystyle b}$conjunto de corte para un fijo${\displaystyle b}$es un problema polinomial.

Otro algoritmo híbrido de búsqueda/inferencia funciona sobre la descomposición en árbol . En general, un problema de satisfacción de restricciones se puede resolver creando primero una descomposición en árbol y luego utilizando un algoritmo especializado.

Un algoritmo de este tipo se basa en propagar primero las restricciones entre los nodos y luego resolver el subproblema en cada uno de ellos. Esta propagación consiste en crear nuevas restricciones que representan los efectos de las restricciones de un nodo sobre un nodo conectado. Más precisamente, si dos nodos están conectados, comparten variables. Las evaluaciones permitidas de estas variables según las restricciones del primer nodo indican cómo afecta este a las variables del segundo. El algoritmo funciona creando la restricción que satisfacen estas evaluaciones e incorporando esta nueva restricción en el segundo nodo.

Cuando todas las restricciones se han propagado desde las hojas hasta la raíz y viceversa, todos los nodos contienen todas las restricciones que les son relevantes. Por lo tanto, el problema puede resolverse en cada nodo.

Se puede adoptar un enfoque híbrido utilizando la eliminación de variables para crear las nuevas restricciones que se propagan dentro de los nodos, y un algoritmo de búsqueda (como retroceso , salto hacia atrás , búsqueda local ) en cada nodo individual.

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7.