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 acíclicos binarios es un problema manejable .
Cada restricción estructural define una medida de complejidad para resolver el problema después de la conversión; esta medida se denomina 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 en esta clase es polinómica para la mayoría de las descomposiciones; si esto se cumple 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 grafo 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 acíclico binario; tales problemas pueden resolverse en un tiempo polinomial en su tamaño. Como resultado, el problema original puede resolverse traduciéndolo primero y luego resolviendo el problema resultante; sin embargo, este algoritmo es polinomial en tiempo solo si la descomposición no aumenta el tamaño superpolinomialmente. El ancho de un método de descomposición es una medida del tamaño del problema que produjo. Originalmente, el ancho se definía como la cardinalidad máxima de los conjuntos de variables originales; un método, la descomposición de 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 acotado por una constante no produzcan problemas excesivamente grandes. Las instancias que tienen una descomposición de ancho fijo pueden traducirse por descomposición en instancias de tamaño acotado por un polinomio en el tamaño de la instancia original.
El ancho de un problema es el ancho de su descomposición de ancho mínimo. Si bien las descomposiciones de ancho fijo se pueden utilizar para resolver un problema de manera eficiente, un límite en el ancho de las instancias produce necesariamente una restricción estructural manejable . De hecho, un problema de ancho fijo tiene una descomposición de ancho fijo, pero su determinación puede no ser polinómica. Para que un problema de ancho fijo se resuelva de manera eficiente mediante descomposición, se debe determinar de manera eficiente 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 se resuelva el problema dada una descomposición de ancho fijo de este en tiempo polinómico, sino que también se determine una descomposición de ancho fijo de un problema de ancho fijo en tiempo polinómico.
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 en el conjunto asociado; en particular, estas 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 aseguran que el nuevo problema sea equivalente al anterior y pueda resolverse de manera eficiente.
Para que el nuevo problema se pueda resolver de manera eficiente, se requiere que el gráfico primario del nuevo problema sea acíclico. En otras palabras, considerando las variables como vértices y las restricciones (binarias) como aristas, el gráfico resultante debe ser 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 obligar a 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, 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 anteriores compartidas entre las dos nuevas variables. Se fuerza que dos copias de una nueva variable sean iguales si existe una ruta de restricciones binarias entre sus nuevas variables y todas las nuevas variables en esta ruta contienen la variable anterior.
Un método de descomposición se define generalmente 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), la primera se aplica automáticamente mediante esta definición. La condición de aplicación de restricciones se formula generalmente 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 se formula generalmente como: el subgrafo inducido por los nodos asociados a una variable original está conectado.
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 utilizando variables ocultas , estos métodos se pueden utilizar indirectamente para proporcionar una descomposición en árbol para problemas de satisfacción de restricciones arbitrarias.
En teoría de grafos, un vértice separador es un nodo de un grafo que "rompe" el grafo cuando se lo elimina de él. Formalmente, es un nodo cuya eliminación del grafo aumenta el número de sus componentes conexos. Un componente biconexo de un grafo es un conjunto máximo de sus nodos cuyo subgrafo inducido es conexo y no tiene ningún vértice separador. Se sabe por la teoría de grafos que los componentes biconexos 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 biconexos y los vértices separadores del grafo; las aristas solo conectan un componente biconexo con un vértice separador, y en particular esto sucede si el vértice está contenido en el componente. Se puede demostrar que este grafo es en realidad un árbol.
Si las restricciones de un problema de satisfacción de restricciones binarias se consideran como aristas de un grafo 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 otra acíclica. Si bien no encaja en la definición de los otros métodos de descomposición, que producen un árbol cuyos nodos están etiquetados con conjuntos de nodos, se puede reformular fácilmente en esos términos.
Este método de descomposición se basa en la idea de que, después de que se le asigna un valor a algunas variables, lo que queda del problema una vez que se han eliminado estas variables puede ser acíclico. Formalmente, un conjunto de cortes de ciclo de un grafo es un conjunto de nodos que hace que el grafo 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 grafo primario. El ancho de una descomposición de ciclo es el número de variables en el conjunto de cortes. El ancho de un problema es el ancho mínimo de sus descomposiciones de conjuntos de cortes de ciclo.
Una descomposición de este tipo no encaja en el esquema de las demás 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, a partir del árbol que resulta de eliminar el cutset se puede obtener un árbol como los generados por los otros métodos de descomposición; 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 a 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 del cutset considerado.
Desafortunadamente, determinar el conjunto mínimo a eliminar es un problema NP-difícil .
La descomposición en árboles es un concepto bien conocido en la teoría de grafos. Reformulada en términos de restricciones binarias, una descomposición en árboles es un árbol cuyos nodos están asociados a conjuntos de variables; el alcance de cada restricción está contenido en el 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 solo las necesarias para garantizar la equivalencia del problema original y el 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 en árbol.
La eliminación de cubos se puede reformular como un algoritmo que funciona en una descomposición de árbol particular. En particular, dado un orden de las variables, cada variable está asociada a un cubo que contiene todas las restricciones de modo que la variable sea la mayor en su alcance. La eliminación de cubos corresponde a la descomposición de árbol que tiene un nodo para cada cubo. Este nodo está asociado a todas sus restricciones y corresponde al conjunto de todas las variables de estas restricciones. El padre de un nodo asociado al cubo de es el nodo asociado al cubo de , donde es el nodo más grande que está en una restricción con y precede en el orden.
Los siguientes métodos se pueden utilizar para traducir un problema de satisfacción de restricciones arbitrario, ya sea binario o de otro tipo. Dado que también se pueden utilizar en problemas binarios, también se pueden utilizar en el resultado de convertir las restricciones en binarias, ya sea traduciéndolo al problema dual o utilizando variables ocultas .
Algunos de estos métodos asocian restricciones a nodos del árbol y definen el ancho teniendo en cuenta el número de restricciones asociadas a los nodos. Esto puede reducir el ancho de algunos problemas. Por ejemplo, una descomposición en la que se asocian diez variables 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, cada nodo puede asociarse con esa restricción, lo que da como resultado un ancho de uno.
La descomposición biconexa de un problema de satisfacción de restricciones arbitrarias es la descomposición biconexa de su gráfico primario. Cada restricción se puede aplicar en un nodo del árbol porque cada restricción crea una camarilla en sus variables en el gráfico primario, y una camarilla es un componente biconexo o un subconjunto de un componente biconexo.
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 aplicar en un nodo del árbol porque cada restricción crea un grupo en sus variables en el gráfico primario y, para cada descomposición en árbol, las variables de un grupo 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 corte para hipergrafos: un hipercorte de ciclo de un hipergrafo es un conjunto de aristas (en lugar de vértices) que hace que el hipergrafo sea acíclico cuando se eliminan todos sus vértices. Se puede obtener una descomposición agrupando todas las variables de un hipercorte en una sola. Esto conduce a un árbol cuyos nodos son conjuntos de hiperaristas. 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 hipercorte 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 un hipergrafo que tiene algunas propiedades definidas a continuación. Una descomposición de bisagra 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 hiperaristas son los alcances de sus restricciones.
La definición de bisagra es la siguiente. Sea un conjunto de hiperaristas. 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 es conexo con respecto a si, para cada par de sus aristas, existe un camino con respecto a de cuyos dos nodos son la primera y la última arista. Un componente conexo con respecto a es un conjunto máximo de aristas conexas con respecto a .
Las bisagras se definen para hipergrafos reducidos, que son hipergrafos en los que ninguna hiperarista está contenida en otra. Un conjunto de al menos dos aristas es una bisagra si, para cada componente conectado con respecto a , todos los nodos en que también están en están todos contenidos en una única arista de .
Una descomposición en bisagra se basa en la correspondencia entre problemas de satisfacción de restricciones e hipergrafos. El hipergrafo asociado a un problema tiene las variables del problema como nodos y los ámbitos de las restricciones como hiperaristas. 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 tales que se cumplen algunas otras condiciones. Por la correspondencia de problemas con hipergrafos, una bisagra es un conjunto de ámbitos de restricciones y, por lo tanto, puede considerarse como un conjunto de restricciones. Las condiciones adicionales de la definición de una 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 ámbito 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, entonces comparten exactamente una restricción y el ámbito 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 bisagra del mismo problema. Este número se denomina grado de ciclicidad del problema o su ancho de bisagra.
La agrupación en árboles o agrupación en árboles de unión se basa en la fusión de 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 cada nodo está asociado a una restricción (y viceversa) y de modo que el subárbol de nodos cuya restricción contiene una variable está conectado. Como resultado, la producción de un árbol de unión puede verse como una forma particular de descomposición, donde cada nodo del árbol está asociado al alcance de una restricción.
No todos los problemas de satisfacción de restricciones tienen un árbol de unión. Sin embargo, los problemas pueden modificarse para adquirir un árbol de unión mediante la fusión de restricciones. La agrupación en árboles se basa en el hecho de que un problema tiene un árbol de unión si y solo si su grafo primario es cordal y conforme con el problema, lo que significa que las variables de cada grupo máximo del grafo primario son el alcance de una restricción y viceversa. La agrupación en árboles modifica un problema arbitrario de tal manera que se cumplan estas dos condiciones. La cordalidad se impone añadiendo nuevas restricciones binarias. La conformidad se obtiene mediante la fusión de restricciones.
En particular, la cordalidad se aplica añadiendo algunas restricciones binarias "falsas" al problema. Se trata de restricciones binarias satisfechas por cualquier par de valores y se utilizan únicamente para añadir aristas al grafo primario del problema. En particular, la cordalidad se obtiene añadiendo aristas que producen el grafo inducido del grafo primario según un orden arbitrario. Este procedimiento es correcto porque el grafo inducido es siempre cordal y se obtiene añadiendo aristas al grafo original.
La conformidad requiere que las camarillas máximas del grafo primario sean exactamente el alcance de las restricciones. Si bien el alcance de cada restricción original es una camarilla en el grafo primario, esta camarilla no es necesariamente máxima. Además, incluso si inicialmente fue máxima, imponer la cordalidad puede crear una camarilla más grande. La conformidad se impone fusionando restricciones. En particular, para cada camarilla máxima del grafo 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 solo 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 grafo cordal. Sin embargo, esto se puede hacer fácilmente utilizando el mismo ordenamiento utilizado para imponer la cordalidad. Dado que los padres de cada nodo están todos conectados entre sí, las camarillas máximas están compuestas por un nodo (el nodo máximo de la camarilla en un ordenamiento de cardinalidad máxima) y todos sus padres. Como resultado, estas camarillas máximas se pueden detectar 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 utilizando nuevamente el mismo orden de variables. Procediendo desde el último nodo hasta el primero, cada restricción se conecta con la restricción anterior que comparte más variables con ella. La agrupación en árboles de unión se puede considerar como un método de descomposición en el que:
El ancho de una descomposición en agrupamiento 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 en agrupamiento de árboles.
El resultado de la descomposición de las bisagras se puede simplificar aún más descomponiendo cada bisagra mediante la agrupación en árbol. En otras palabras, una vez identificadas las bisagras, se produce una agrupación 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 variable o restricción dada está conectado. Más precisamente, para cada variable, el subárbol de nodos asociados a esta variable o con una restricción que tiene esta variable en su alcance está conectado. El ancho de una descomposición es el número máximo combinado de variables y restricciones asociadas con un nodo.
La asociación de restricciones con nodos posiblemente reduce el ancho de las descomposiciones y de las instancias. Por otra parte, esta definición de ancho todavía permite que los problemas de ancho fijo se resuelvan en tiempo polinomial 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 que tiene un número fijo de restricciones. Como resultado, se garantiza que este dominio será de tamaño polinomial; 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 consulta de un ancho dado, se puede construir en el espacio logarítmico una descomposición de 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.
Una desventaja de este método de descomposición es que verificar si una instancia tiene un ancho fijo es, en general, NP-completo ; se ha demostrado que este es el caso con un ancho de 4.
Una descomposición en 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 las siguientes dos condiciones:
El ancho de una descomposición en árbol es el número máximo de restricciones asociadas con cada nodo. Si este ancho está limitado por una constante, se puede construir un problema equivalente al original en tiempo polinomial. 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 primero proyectando las restricciones sobre las variables del nodo y luego encontrando todas las soluciones a este subproblema, o primero resolviendo 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 el nuevo, pero sí para garantizar que los problemas de amplitud limitada se puedan resolver en tiempo polinómico.
La posibilidad de asociar una restricción con un nodo mientras algunas de sus variables no están efectivamente asociadas con el nodo puede producir un ancho menor que el ancho de la consulta. Por ejemplo, si un nodo está asociado a 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 solo se calculan las restricciones al verificar el ancho, este nodo tiene un ancho de dos. El mismo nodo tiene un ancho de cuatro cuando se usa la descomposición de consulta (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 omite el último requisito; se trata de la condición "las variables de las restricciones de un nodo que no son variables del nodo no aparecen en el subárbol con raíz en el nodo". Un problema se puede resolver claramente en tiempo polinomial si se da una descomposición de ancho fijo del mismo. Sin embargo, no se sabe si la restricción a un ancho fijo es manejable, ya que se desconoce la complejidad de encontrar una descomposición de ancho fijo incluso si se sabe que existe, a partir de 2001 [actualizar].
El ancho de las instancias es una forma de medir la eficiencia de los métodos de descomposición. En efecto, dado que los problemas pueden resolverse a partir de descomposiciones de ancho fijo, cuanto menor sea el ancho según una descomposición, más instancias pueden resolverse de manera eficiente utilizando esa descomposición.
Algunas descomposiciones utilizan el número de variables de un nodo (o una cantidad similar) como el ancho. Otras no lo hacen: la descomposición hipercutset cíclica, la descomposición bisagra, la descomposición de consulta, la descomposición hiperárbol y la descomposición hiperárbol generalizada asocian restricciones (o sus alcances en forma de hiperaristas) con nodos e incluyen el número de restricciones asociadas a un nodo en el ancho. Esto puede ser un ahorro significativo en términos de ancho. De hecho, los problemas con una sola restricción en las variables solo se pueden descomponer en un árbol con un solo nodo. Este nodo puede estar asociado con las variables o con la única restricción. Contar el número de variables conduce a width , mientras que contar el número de restricciones conduce a width .
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 para un valor fijo . La superación significa que hay clases de problemas que tienen un ancho fijo según un método de descomposición pero no según otro. Los siguientes son los resultados para problemas arbitrarios, donde no se considera la descomposición de consultas:
También se puede demostrar que el ancho de agrupamiento del árbol es igual al ancho inducido del problema más uno. El algoritmo de consistencia adaptativa, que es polinomial para problemas de ancho inducido fijo, convierte los problemas en equivalentes de la misma manera que el primer paso del agrupamiento del árbol.
Dado el árbol de una descomposición, la solución se puede realizar construyendo el problema tipo árbol binario como se describió anteriormente y resolviéndolo. Este es un problema de tiempo polinómico, ya que se puede resolver en tiempo polinómico utilizando, por ejemplo, un algoritmo para hacer cumplir la consistencia del arco direccional .
A continuación se describe un algoritmo especializado para el caso de problemas acíclicos binarios 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 que se pasa 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 que se pasa a lo largo de una arista indica cómo la parte del extremo de origen de la arista afecta las variables del nodo de destino. En otras palabras, una restricción que se pasa de un nodo a otro indica cómo los nodos "del lado de " restringen las variables del 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 sobre de los nodos del lado de se puede representar como una restricción sobre las variables . Dicha restricción se puede ver como un "resumen" de cómo un conjunto de nodos afecta a otro nodo.
El algoritmo procede a partir de las hojas del árbol. En cada nodo se recogen los resúmenes de sus hijos (si los hay). Estos resúmenes 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 lo envía. Cuando se alcanzan todas las hojas, el algoritmo se detiene.
El conjunto de variables compartidas entre dos nodos se denomina separador . Como el separador es la intersección entre dos conjuntos asociados a nodos, su tamaño no puede ser mayor que el ancho inducido del grafo.
Mientras que el ancho del gráfico afecta el tiempo necesario para resolver los subproblemas en cada nodo, el tamaño del separador afecta el tamaño de las restricciones que se pasan entre nodos. De hecho, estas restricciones tienen como alcance a los separadores. Como resultado, una restricción sobre un separador de tamaño puede requerir que se almacene tamaño , si todas las variables tienen un 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 las restricciones sobre 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 que se pasan entre nodos pueden tener un tamaño exponencial en relación con el tamaño del separador. La memoria necesaria para almacenar estas restricciones se puede reducir utilizando una descomposición en árbol con separadores pequeños. Sin embargo, estos á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 determinado, se puede imponer un tamaño máximo fijo de separador permitido 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 mayor que el de los dos nodos. Esto puede aumentar el ancho del árbol. Sin embargo, esta fusión no cambia los separadores del árbol, salvo que se elimina el separador entre los dos nodos fusionados.
Esto último es una 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 , ya que de lo contrario habría ciclo en el árbol. Como resultado, el nodo obtenido al fusionar y 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, la fusión de un par de nodos unidos por un separador no cambia los demás separadores. Por lo tanto, se puede aplicar un tamaño máximo fijo de separador calculando primero todos los tamaños de separador y luego fusionando de manera iterativa 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 colocando restricciones sobre las relaciones de las restricciones; estas se denominan restricción relacional y el conjunto de relaciones permitidas se denomina lenguaje de restricciones .
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 manejabilidad requiere que se cumplan dos condiciones. Primero, si el problema tiene un ancho limitado por una constante, entonces se puede encontrar una descomposición de ancho limitado en tiempo polinómico. Segundo, el problema obtenido al convertir el problema original según la descomposición no es superpolinómicamente más grande 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 la fijación del ancho de un método de descomposición, se han desarrollado otras. Algunas pueden reformularse en términos de métodos de descomposición: por ejemplo, la restricción al problema acíclico binario puede reformularse como la del problema del ancho de árbol 1; la restricción del ancho inducido (que no se define en términos de una descomposición) puede reformularse como agrupamiento en árbol.
Una restricción estructural temprana (que luego evolucionó hacia la basada en el ancho inducido) se basa en el ancho del grafo primario del problema. Dado un orden de los nodos del grafo, 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 ancho y es fuertemente consistente, es eficientemente solucionable. Esta es una restricción que no es ni 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.
