En la satisfacción de restricciones , un método de descomposición traduce un problema de satisfacción de restricciones en otro problema de satisfacción de restricciones que es binario y acíclico . Los métodos de descomposición funcionan agrupando variables en conjuntos y resolviendo un subproblema para cada conjunto. Estas traducciones se realizan porque resolver problemas binarios acíclicos es un problema manejable .
Cada restricción estructural definió una medida de complejidad de la solución del problema después de la conversión; esta medida se llama ancho . Fijar un ancho máximo permitido es una forma de identificar una subclase de problemas de satisfacción de restricciones. La resolución de problemas de esta clase es polinómica para la mayoría de las descomposiciones; si esto es válido para una descomposición, la clase de problemas de ancho fijo forma una subclase manejable de problemas de satisfacción de restricciones.
Los métodos de descomposición traducen un problema en uno nuevo que es más fácil de resolver. El nuevo problema sólo contiene restricciones binarias ; sus alcances forman un gráfico acíclico dirigido . Las variables del nuevo problema representan cada una un conjunto de variables del original. Estos conjuntos no son necesariamente disjuntos, pero cubren el conjunto de las variables originales. La traducción encuentra todas las soluciones parciales relativas a cada conjunto de variables. El problema que resulta de la traducción representa las interacciones entre estas soluciones locales.
Por definición, un método de descomposición produce un problema binario acíclico; Estos problemas se pueden resolver en tiempo polinómico en su tamaño. Como resultado, el problema original se puede resolver traduciéndolo primero y luego resolviendo el problema resultante; sin embargo, este algoritmo es de tiempo polinomial sólo si la descomposición no aumenta el tamaño de forma superpolinomial. La amplitud de un método de descomposición es una medida del tamaño del problema que produjo. Originalmente, el ancho se definió como la cardinalidad máxima de los conjuntos de variables originales; un método, la descomposición del hiperárbol, utiliza una medida diferente. De cualquier manera, el ancho de una descomposición se define de modo que las descomposiciones de tamaño acotadas por una constante no produzcan problemas excesivamente grandes. Las instancias que tienen una descomposición de ancho fijo se pueden traducir mediante descomposición en instancias de tamaño limitado por un polinomio del tamaño de la instancia original.
El ancho de un problema es el ancho de su descomposición en ancho mínimo. Si bien las descomposiciones de ancho fijo se pueden utilizar para resolver eficientemente un problema, un límite en el ancho de las instancias necesariamente produce una restricción estructural manejable . De hecho, un problema de ancho fijo tiene una descomposición del ancho fijo, pero encontrarlo puede no ser polinómico. Para que un problema de ancho fijo se resuelva eficientemente mediante descomposición, se debe encontrar eficientemente una de sus descomposiciones de ancho bajo. Por esta razón, los métodos de descomposición y su ancho asociado se definen de tal manera que no solo resolver el problema dada una descomposición de ancho fijo es tiempo polinómico, sino que también encontrar una descomposición de ancho fijo de un problema de ancho fijo es polinomial. tiempo.
Los métodos de descomposición crean un problema que es fácil de resolver a partir de uno arbitrario. Cada variable de este nuevo problema está asociada a un conjunto de variables originales; su dominio contiene tuplas de valores para las variables del conjunto asociado; en particular, éstas son las tuplas que satisfacen un conjunto de restricciones sobre estas variables. Las restricciones del nuevo problema limitan los valores de dos nuevas variables para que tengan como valores dos tuplas que concuerden en las variables originales compartidas. Tres condiciones adicionales garantizan que el nuevo problema sea equivalente al antiguo y pueda resolverse de manera eficiente.
Para que el nuevo problema pueda resolverse de manera eficiente, se requiere que el gráfico primario del nuevo problema sea acíclico. En otras palabras, al ver las variables como vértices y las restricciones (binarias) como aristas, se requiere que el gráfico resultante sea un árbol o un bosque .
Para que el nuevo problema sea equivalente al anterior, cada restricción original se aplica como parte de la definición del dominio de al menos una nueva variable. Esto requiere que, para cada restricción del problema anterior, exista una variable del nuevo problema tal que su conjunto asociado de variables originales incluya el alcance de la restricción, y todas las tuplas en su dominio satisfagan la restricción.
Otra condición necesaria para garantizar la equivalencia es que las restricciones binarias sean suficientes para hacer que todas las "copias" de cada variable original asuman el mismo valor. Dado que la misma variable original puede asociarse a varias de las nuevas variables, todos los valores de estas nuevas variables deben coincidir con el valor de la variable anterior. Las restricciones binarias se utilizan para imponer la igualdad de las variables antiguas compartidas entre las dos variables nuevas. Dos copias de una nueva variable son forzadas a ser iguales si existe una ruta de restricciones binarias entre sus nuevas variables y todas las variables nuevas en esta ruta contienen la variable anterior.
Un método de descomposición suele definirse proporcionando un árbol cuyos nodos son las variables del nuevo problema; para cada nodo, también se proporciona el conjunto asociado de variables originales y posiblemente un conjunto de restricciones originales utilizadas para construir el dominio de la variable en el nuevo problema. De las tres condiciones anteriores (estructura de árbol, aplicación de restricciones y equivalencia de copias de variables originales), esta definición aplica automáticamente la primera. La condición de aplicación de restricciones se formula principalmente como: el alcance de cada restricción es un subconjunto de las variables de algún nodo; sin embargo, se puede utilizar una condición diferente cuando los nodos también están asociados a conjuntos de restricciones. La equivalencia de todas las copias de las variables originales suele formularse como: el subgrafo inducido por los nodos asociados a una variable original es conexo.
Existen varios métodos de descomposición. La mayoría de ellos generan una clase manejable al limitar el ancho de las instancias. Los siguientes son los métodos de descomposición definidos para problemas de satisfacción de restricciones binarias. Dado que un problema se puede convertir en binario traduciéndolo a su problema dual o usando variables ocultas , estos métodos se pueden usar indirectamente para proporcionar una descomposición en árbol para problemas de satisfacción de restricciones arbitrarias.
En teoría de grafos, un vértice de separación es un nodo de un gráfico que "rompe" el gráfico cuando se retira de él. Formalmente, es un nodo cuya eliminación del gráfico aumenta el número de componentes conectados. Un componente biconectado de un gráfico es un conjunto máximo de sus nodos cuyo subgrafo inducido está conectado y no tiene ningún vértice de separación. Se sabe por la teoría de grafos que los componentes biconectados y los vértices separadores de un grafo forman un árbol. Este árbol se puede construir de la siguiente manera: sus nodos son los componentes biconectados y los vértices separadores del grafo; Los bordes solo conectan un componente biconectado con un vértice de separación y, en particular, esto sucede si el vértice está contenido en el componente. Se puede demostrar que este gráfico es en realidad un árbol.
Si las restricciones de un problema de satisfacción de restricciones binarias se ven como bordes de un gráfico cuyos nodos son las variables, este árbol es una descomposición del problema. El ancho de una descomposición es el número máximo de vértices en un componente biconectado.
El método de descomposición cíclica divide un problema en una parte cíclica y una parte acíclica. Si bien no encaja en la definición de otros métodos de descomposición, que producen un árbol cuyos nodos están etiquetados con conjuntos de nodos, puede reformularse fácilmente en esos términos.
Este método de descomposición se basa en la idea de que, después de dar un valor a algunas variables, lo que queda del problema una vez eliminadas dichas variables puede ser acíclico. Formalmente, un conjunto de cortes cíclicos de un gráfico es un conjunto de nodos que hacen que el gráfico sea acíclico cuando se eliminan de él. Se puede dar una definición similar para un problema de satisfacción de restricciones utilizando su gráfico primario. El ancho de una descomposición de ciclo es el número de variables en el conjunto de corte. El ancho de un problema es el ancho mínimo de sus descomposiciones de corte de ciclo.
Tal descomposición no encaja en el esquema de las otras descomposiciones porque el resultado de la descomposición no es un árbol, sino un conjunto de variables (las del cutset) y un árbol (formado por las variables que no están en el cutset). Sin embargo, un árbol como los generados por los otros métodos de descomposición se puede obtener a partir del árbol que resulta de eliminar el cutset; Esto se hace eligiendo una raíz, sumando todas las variables del cutset a todos sus nodos y las variables de cada nodo a todos sus hijos. Esto da como resultado un árbol cuyo número máximo de variables asociadas con un nodo es igual al tamaño del cutset más dos. Aparte de la suma de dos, este es el ancho de la descomposición, que se define como el número de variables en el conjunto de corte considerado.
Desafortunadamente, determinar el conjunto mínimo a eliminar es un problema NP-Difícil .
La descomposición de árboles es un concepto bien conocido de la teoría de grafos. Reformulado en términos de restricciones binarias, un árbol de descomposición es un árbol cuyos nodos están asociados a conjuntos de variables; el alcance de cada restricción está contenido en un conjunto de variables de algún nodo, y el subárbol de nodos asociado a cada variable está conectado. Esta es la forma más general de descomposición para restricciones binarias que sigue el esquema descrito anteriormente, ya que las condiciones impuestas al árbol son sólo las necesarias para garantizar el equivalente del problema original y nuevo.
El ancho de dicha descomposición es el número máximo de variables asociadas al mismo nodo menos uno. El ancho de árbol de un problema es el ancho mínimo de sus descomposiciones de árbol.
La eliminación del cubo se puede reformular como un algoritmo que trabaja en la descomposición de un árbol particular. En particular, dado un orden de las variables, a cada variable se le asocia un grupo que contiene todas las restricciones de modo que la variable sea la mayor en su alcance. La eliminación de cubetas corresponde a la descomposición del árbol que tiene un nodo para cada cubeta. Este nodo tiene asociadas todas sus restricciones y corresponde al conjunto de todas las variables de estas restricciones. El padre de un nodo asociado al depósito de es el nodo asociado al depósito de , donde es el nodo mayor que está en una restricción y precede en el orden.
Los siguientes métodos se pueden utilizar para traducir un problema de satisfacción de restricciones arbitraria, ya sea binario o no. Dado que también se pueden usar en problemas binarios, también se pueden usar en el resultado de hacer que las restricciones sean binarias, ya sea traduciéndolas al problema dual o usando variables ocultas .
Algunos de estos métodos asocian restricciones con nodos del árbol y definen el ancho teniendo en cuenta el número de restricciones asociadas con los nodos. Esto puede reducir la amplitud de algunos problemas. Por ejemplo, una descomposición en la que diez variables están asociadas a cada nodo tiene un ancho de diez; sin embargo, si cada uno de estos conjuntos de diez variables es el alcance de una restricción, a cada nodo se le puede asociar esa restricción, lo que da como resultado un ancho uno.
La descomposición biconectada de un problema de satisfacción de restricciones arbitrarias es la descomposición biconectada de su gráfico primario. Cada restricción se puede imponer en un nodo del árbol porque cada restricción crea una camarilla en sus variables en el gráfico principal, y una camarilla es un componente biconectado o un subconjunto de un componente biconectado.
Una descomposición en árbol de un problema de satisfacción de restricciones arbitrarias es una descomposición en árbol de su gráfico primario. Cada restricción se puede imponer en un nodo del árbol porque cada restricción crea una camarilla en sus variables en el gráfico primario y, para cada descomposición del árbol, las variables de una camarilla están completamente contenidas en las variables de algún nodo.
Este es el mismo método de corte de ciclo que utiliza la definición de conjunto de corte para hipergráficos: un hipergráfico de ciclo de un hipergráfico es un conjunto de aristas (en lugar de vértices) que hace que el hipergráfico sea acíclico cuando se eliminan todos sus vértices. Se puede obtener una descomposición agrupando todas las variables de un hipercutset en una sola. Esto conduce a un árbol cuyos nodos son conjuntos de hiperbordes. El ancho de dicha descomposición es el tamaño máximo de los conjuntos asociados con los nodos, que es uno si el problema original es acíclico y el tamaño de su hiperconjunto mínimo en caso contrario. El ancho de un problema es el ancho mínimo de sus descomposiciones.
Una bisagra es un subconjunto de nodos de hipergrafo que tiene algunas propiedades definidas a continuación. Una descomposición de bisagras se basa en los conjuntos de variables que son bisagras mínimas del hipergrafo cuyos nodos son las variables del problema de satisfacción de restricciones y cuyos hiperbordes son los alcances de sus restricciones.
La definición de bisagra es la siguiente. Sea un conjunto de hiperbordes. Un camino con respecto a es una secuencia de aristas tal que la intersección de cada una con la siguiente no está vacía y no está contenida en los nodos de . Un conjunto de aristas está conectado respecto de si, para cada par de sus aristas, existe un camino respecto del cual los dos nodos son la primera y la última arista. Un componente conectado con respecto a es un conjunto máximo de aristas conectadas con respecto a .
Las bisagras se definen para hipergrafías reducidas, que son hipergrafías en las que no hay ningún hiperborde contenido en otro. Un conjunto de al menos dos aristas es una bisagra si, para cada componente conectado con respecto a , todos los nodos que también están contenidos en un solo borde de .
Una descomposición de bisagra se basa en la correspondencia entre problemas de satisfacción de restricciones e hipergrafías. El hipergrafo asociado con un problema tiene las variables del problema como nodos y los alcances de las restricciones como hiperbordes. Una descomposición en bisagra de un problema de satisfacción de restricciones es un árbol cuyos nodos son algunas bisagras mínimas del hipergrafo asociado al problema y de manera que se cumplen algunas otras condiciones. Por la correspondencia de los problemas con los hipergrafos, una bisagra es un conjunto de alcances de restricciones y, por tanto, puede considerarse como un conjunto de restricciones. Las condiciones adicionales de la definición de descomposición en bisagra son tres, de las cuales las dos primeras aseguran la equivalencia del problema original con el nuevo. Las dos condiciones para la equivalencia son: el alcance de cada restricción está contenido en al menos un nodo del árbol y el subárbol inducido por una variable del problema original está conectado. La condición adicional es que, si se unen dos nodos, comparten exactamente una restricción y el alcance de esta restricción contiene todas las variables compartidas por los dos nodos.
El número máximo de restricciones de un nodo es el mismo para todas las descomposiciones de bisagra del mismo problema. Este número se denomina grado de ciclicidad del problema o ancho de bisagra.
La agrupación de árboles o agrupación de árboles de unión se basa en fusionar restricciones de tal manera que el problema resultante tiene un árbol de unión , este árbol de unión es el resultado de la descomposición.
Un árbol de unión de un problema de satisfacción de restricciones es un árbol en el que a cada nodo se le asocia una restricción (y viceversa) y tal que el subárbol de nodos cuya restricción contiene una variable está conectado. Como resultado, producir un árbol de unión puede verse como una forma particular de descomposición, donde a cada nodo del árbol se le asocia el alcance de una restricción.
No todos los problemas de satisfacción de restricciones tienen un árbol de unión. Sin embargo, los problemas se pueden modificar para adquirir un árbol de unión fusionando restricciones. La agrupación de árboles se basa en el hecho de que un problema tiene un árbol de unión si y sólo si su gráfico primario es cordal y conforme con el problema, lo último significa que las variables de cada camarilla máxima del gráfico primario son el alcance de una restricción y viceversa. La agrupación de árboles modifica un problema arbitrario de tal manera que se cumplan estas dos condiciones. La cordalidad se aplica agregando nuevas restricciones binarias. La conformidad se obtiene fusionando restricciones.
En particular, la cordalidad se aplica añadiendo algunas restricciones binarias "falsas" al problema. Estas son restricciones binarias satisfechas por cualquier par de valores y se usan solo para agregar aristas al gráfico primario del problema. En particular, la cordalidad se obtiene sumando aristas produciendo el gráfico inducido del gráfico primario según un orden arbitrario. Este procedimiento es correcto porque la gráfica inducida siempre es cordal y se obtiene sumando aristas a la gráfica original.
La conformidad requiere que las camarillas máximas del gráfico primario sean exactamente el alcance de las restricciones. Si bien el alcance de cada restricción original es de camarilla en el gráfico primario, esta camarilla no es necesariamente máxima. Además, incluso si inicialmente fuera máximo, imponer la cordalidad puede crear una camarilla más grande. La conformidad se impone mediante la fusión de restricciones. En particular, para cada camarilla máxima del gráfico resultante de imponer la cordalidad, se crea una nueva restricción con la camarilla como alcance. Los valores satisfactorios de esta nueva restricción son los que satisfacen todas las restricciones originales cuyo alcance está contenido en la camarilla. Mediante esta transformación, cada restricción original se "incluye" en al menos una nueva restricción. De hecho, el alcance de cada restricción original es una camarilla del grafo primario. Esta camarilla sigue siendo una camarilla incluso después de imponer la cordalidad, ya que este proceso sólo introduce nuevas aristas. Como resultado, esta camarilla es máxima o está contenida en una camarilla máxima.
Esta traducción requiere que se identifiquen las camarillas máximas de un gráfico cordal. Sin embargo, esto se puede hacer fácilmente utilizando el mismo orden utilizado para imponer la cordalidad. Dado que todos los padres de cada nodo están conectados entre sí, las camarillas máximas se componen de un nodo (el nodo máximo de la camarilla en un orden de cardinalidad máxima) y todos sus padres. Como resultado, estas camarillas máximas pueden detectarse considerando cada nodo con sus padres.
El problema que resulta de este proceso tiene un árbol de unión, y dicho árbol de unión se puede obtener usando nuevamente el mismo orden de variables. Desde el último nodo hasta el primero, cada restricción está conectada con la restricción anterior que comparte más variables con ella. La agrupación de árboles de unión puede verse como un método de descomposición en el que:
El ancho de una descomposición de agrupaciones de árboles es el número máximo de variables asociadas con cada nodo del árbol. El ancho de un problema es el ancho mínimo de sus descomposiciones de agrupaciones de árboles.
El resultado de la descomposición de las bisagras se puede simplificar aún más descomponiendo cada bisagra mediante agrupación de árboles. Es decir, una vez identificadas las bisagras se produce un agrupamiento en árbol de cada una de ellas. En términos del árbol resultante, cada nodo se reemplaza por un árbol.
La descomposición de consultas asocia un conjunto de variables y un conjunto de restricciones a cada nodo de un árbol; cada restricción está asociada a algún nodo, y el subárbol inducido por los nodos asociados a una determinada variable o restricción está conectado. Más precisamente, para cada variable, se conecta el subárbol de nodos asociados a esta variable o con una restricción que tiene esta variable en su alcance. El ancho de una descomposición es el número máximo combinado de variables y restricciones asociadas con un nodo.
Asociar restricciones con nodos posiblemente reduzca el ancho de las descomposiciones y de las instancias. Por otro lado, esta definición de ancho todavía permite resolver problemas de ancho fijo en tiempo polinómico si se da la descomposición. En este caso, el dominio de una nueva variable se obtiene resolviendo un subproblema que puede ser polinomialmente grande pero tiene un número fijo de restricciones. Como resultado, se garantiza que este dominio será de tamaño polinómico; las restricciones del nuevo problema, al ser igualdades de dos dominios, también son de tamaño polinomial.
Una descomposición de consulta pura es una descomposición de consulta en la que los nodos solo están asociados a restricciones. A partir de una descomposición de una consulta de un ancho determinado, se puede construir en un espacio logarítmico una descomposición de una consulta pura del mismo ancho. Esto se obtiene reemplazando las variables de un nodo que no están en las restricciones del nodo con algunas restricciones que contienen estas variables.
Un inconveniente de este método de descomposición es que comprobar si una instancia tiene un ancho fijo es, en general, NP-completo ; se ha demostrado que este es el caso con el ancho 4
Una descomposición de hiperárbol asocia un conjunto de variables y un conjunto de restricciones a cada nodo de un árbol. Extiende la descomposición de consultas al permitir que las restricciones de un nodo contengan variables que no se utilizan al crear el dominio de la nueva variable asociada con el nodo. Además de las condiciones comunes para un método de descomposición (el alcance de cada restricción está en al menos un conjunto de variables asociadas con un nodo y el subárbol inducido por una variable original está conectado), se requieren que se cumplan las dos condiciones siguientes:
El ancho de la descomposición de un árbol es el número máximo de restricciones asociadas con cada nodo. Si este ancho está acotado por una constante, se puede construir un problema equivalente al original en tiempo polinómico. Las variables que no están asociadas a un nodo pero que están dentro del alcance de las restricciones del nodo se "proyectan" al construir esta instancia. Esto se puede hacer proyectando primero las restricciones sobre las variables del nodo y luego encontrando todas las soluciones a este subproblema, o resolviendo primero el subproblema con todas las restricciones y luego eliminando las variables adicionales.
Los dos requisitos anteriores no son necesarios para garantizar la equivalencia del problema original y nuevo. Son necesarios para garantizar que los problemas de ancho acotado puedan resolverse en tiempo polinomial.
La posibilidad de asociar una restricción con un nodo mientras algunas de sus variables no están asociadas efectivamente con el nodo puede producir un ancho menor que el ancho de la consulta. Por ejemplo, si un nodo está asociado en una descomposición de consulta y existe una restricción, una descomposición de hiperárbol puede asociar el mismo nodo con restricciones y variables . Dado que sólo se calculan las restricciones al comprobar el ancho, este nodo tiene un ancho dos. El mismo nodo tiene un ancho cuatro cuando se utiliza la descomposición de consultas (una restricción y tres variables). Esta reducción de ancho es posible si dos o más variables se pueden reemplazar con una sola restricción, incluso si esta restricción contiene una variable que no está asociada con el nodo.
Las descomposiciones de hiperárbol generalizadas se definen como descomposiciones de hiperárbol, pero se elimina el último requisito; esta es la condición "las variables de las restricciones de un nodo que no son variables del nodo no ocurren en el subárbol enraizado en el nodo". Un problema se puede resolver claramente en tiempo polinomial si se da una descomposición de ancho fijo. Sin embargo, no se sabe que la restricción a un ancho fijo sea manejable, ya que en 2001 no se conoce la complejidad de encontrar una descomposición de un ancho fijo, incluso si se sabe que existe [actualizar].
El ancho de instancias es una forma de eficiencia de los métodos de descomposición. De hecho, dado que los problemas se pueden resolver a partir de descomposiciones de ancho fijo, cuanto menor sea el ancho según una descomposición, más casos se pueden resolver de manera eficiente usando esa descomposición.
Algunas descomposiciones utilizan el número de variables de un nodo (o una cantidad similar) como ancho. Otros no lo hacen: ciclo de hipercorte, descomposición de bisagra, descomposición de consultas, descomposición de hiperárbol y descomposición de hiperárbol generalizada asocian restricciones (o sus alcances en forma de hiperbordes) con nodos e incluyen el número de restricciones asociadas a un nodo en el ancho. Esto puede suponer un ahorro significativo en términos de ancho. De hecho, los problemas con una única restricción de variables sólo se pueden descomponer en un árbol con un único nodo. Este nodo puede estar asociado con las variables o con la restricción única. Contar el número de variables conduce al ancho , mientras que contar el número de restricciones conduce al ancho .
La comparación entre todos los demás métodos de descomposición se basa en la generalización y la superación. La generalización significa que cada problema que tiene un ancho según un método tiene un ancho limitado por un valor fijo . Batir significa que hay clases de problemas que tienen ancho fijo según un método de descomposición pero no según otro. Los siguientes son los resultados de problemas arbitrarios, donde no se considera la descomposición de consultas:
También se puede demostrar que el ancho del agrupamiento de árboles es igual al ancho inducido del problema más uno. El algoritmo de consistencia adaptativa, que es polinómico para problemas de ancho inducido fijo, convierte los problemas en equivalentes de la misma manera que en el primer paso de la agrupación de árboles.
Dado el árbol de una descomposición, la resolución se puede realizar construyendo el problema en forma de árbol binario como se describe anteriormente y resolviéndolo. Este es un problema de tiempo polinomial, ya que se puede resolver en tiempo polinomial usando, por ejemplo, un algoritmo para imponer la consistencia del arco direccional .
A continuación se describe un algoritmo especializado para el caso de problemas binarios acíclicos que resultan de una descomposición. Funciona creando restricciones que se pasan a lo largo de los bordes del árbol, desde las hojas hasta la raíz y viceversa. La restricción pasada a lo largo de un borde "resume" los efectos de todas las restricciones de la parte del gráfico de un lado del borde al otro.
En un árbol, cada arista divide el gráfico en dos partes. La restricción pasada a lo largo de un borde indica cómo la parte del extremo de origen del borde afecta las variables del nodo de destino. En otras palabras, una restricción pasada de nodo a nodo indica cómo los nodos "del lado de " restringen las variables de nodo .
Si las variables de estos dos nodos son y , los nodos del lado de no afectan a todas las variables sino solo a las variables compartidas . Como resultado, la influencia de los nodos del lado de puede representarse como una restricción de las variables . Esta restricción puede verse como un "resumen" de cómo un conjunto de nodos afecta a otro nodo.
El algoritmo parte de las hojas del árbol. En cada nodo se recopilan los resúmenes de sus hijos (si los hay). Este resumen y la restricción del nodo se utilizan para generar el resumen del nodo para su padre. Cuando se llega a la raíz, el proceso se invierte: se genera el resumen de cada nodo para cada hijo y se envía. Cuando se alcanzan todas las hojas, el algoritmo se detiene.
El conjunto de variables compartidas entre dos nodos se denomina separador . Dado que el separador es la intersección entre dos conjuntos asociados con nodos, su tamaño no puede ser mayor que el ancho inducido del gráfico.
Mientras que el ancho del gráfico afecta el tiempo requerido para resolver los subproblemas en cada nodo, el tamaño del separador afecta el tamaño de las restricciones que se pasan entre los nodos. De hecho, estas restricciones tienen como alcance los separadores. Como resultado, una restricción sobre un separador de tamaño puede requerir que se almacene el tamaño, si todas las variables tienen el dominio de tamaño .
El algoritmo para resolver un problema a partir de un árbol de descomposición incluye dos operaciones: resolver un subproblema relativo a un nodo y crear la restricción relativa a las variables compartidas (el separador) entre dos nodos. Se pueden utilizar diferentes estrategias para estas dos operaciones. En particular, la creación de restricciones en los separadores se puede realizar mediante la eliminación de variables, que es una forma de inferencia, mientras que los subproblemas se pueden resolver mediante búsqueda (retroceso, etc.)
Un problema con este algoritmo es que las restricciones pasadas entre nodos pueden ser de tamaño exponencial en el tamaño del separador. La memoria necesaria para almacenar estas restricciones se puede reducir mediante el uso de una descomposición de árbol con pequeños separadores. Sin embargo, dichos árboles de descomposición pueden tener un ancho (número de nodos en cada nodo) mayor que el óptimo.
Para un árbol de descomposición dado, se puede imponer un tamaño de separador máximo permitido fijo uniendo todos los pares de nodos cuyo separador sea mayor que este tamaño. La fusión de dos nodos generalmente produce un nodo con un conjunto asociado de variables mayores que las de los dos nodos. Esto puede aumentar el ancho del árbol. Sin embargo, esta fusión no cambia los separadores del árbol más que eliminar el separador entre los dos nodos fusionados.
Esto último es consecuencia de la aciclicidad: dos nodos unidos no pueden unirse al mismo otro nodo. Si y son dos nodos que se van a fusionar y y son los conjuntos de nodos unidos a ellos, entonces , de lo contrario habría un ciclo en el árbol. Como resultado, el nodo obtenido al fusionarse se unirá a cada uno de los nodos de . Como resultado, los separadores de este nodo fusionado son exactamente los separadores de los dos nodos originales.
Como resultado, fusionar un par de nodos unidos por un separador no cambia los otros separadores. Como resultado, se puede imponer un tamaño de separador máximo fijo calculando primero todos los tamaños de separador y luego fusionando iterativamente cualquier par de nodos que tengan un separador mayor que una cantidad determinada, y no es necesario volver a calcular el tamaño de los separadores durante la ejecución.
Limitar el ancho de un método de descomposición mediante una constante crea una restricción estructural , es decir, limita los posibles alcances de las restricciones, pero no sus relaciones. La forma complementaria de obtener subclases manejables de satisfacción de restricciones es imponiendo restricciones a las relaciones de restricciones; éstas se denominan restricción relacional y el conjunto de relaciones permitidas se denomina lenguaje de restricción .
Si la resolución de problemas que tienen un ancho de descomposición limitado por una constante está en P , la descomposición conduce a una restricción estructural manejable. Como se explicó anteriormente, la trazabilidad requiere que se cumplan dos condiciones. Primero, si el problema tiene un ancho acotado por una constante, entonces se puede encontrar una descomposición del ancho acotado en tiempo polinomial. En segundo lugar, el problema obtenido al convertir el problema original según la descomposición no es superpolinomialmente mayor que el problema original, si la descomposición tiene un ancho fijo.
Si bien la mayoría de las restricciones estructurales manejables se derivan de fijar el ancho de un método de descomposición, se han desarrollado otras. Algunos pueden reformularse en términos de métodos de descomposición: por ejemplo, la restricción al problema binario acíclico puede reformularse como el problema del ancho de árbol 1; la restricción del ancho inducido (que no está definido en términos de descomposición) puede reformularse como agrupación de árboles.
Una restricción estructural temprana (que luego evolucionó hacia la basada en el ancho inducido) se basa en el ancho del gráfico primario del problema. Dado un orden de los nodos del gráfico, el ancho de un nodo es el número de nodos que lo unen y lo preceden en el orden. Sin embargo, restringir solo el ancho no conduce a una restricción manejable: incluso restringiendo este ancho a 4, establecer la satisfacibilidad sigue siendo NP-completo . La manejabilidad se obtiene restringiendo las relaciones; en particular, si un problema tiene amplitud y es fuertemente consistente, se puede resolver de manera eficiente. Esta es una restricción que no es estructural ni relacional, ya que depende tanto de los alcances como de las relaciones de las restricciones.
Aquí hay algunos enlaces a recursos en línea para la descomposición de árboles/hiperárboles en general.
