En 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 definió una medida de complejidad para resolver el problema después de la conversión; esta medida se llama ancho . La fijación de un ancho máximo permitido es una forma de identificar una subclase de problemas de satisfacción de restricciones. Resolver problemas en esta clase es polinomial 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.
Descripción general
Los métodos de descomposición traducen un problema en uno nuevo que es más fácil de resolver. El nuevo problema solo 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 acíclico binario; tales problemas se pueden resolver en polinomios de tiempo 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 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 definió como la cardinalidad máxima de los conjuntos de variables originales; un método, la descomposición de hiperárboles, utiliza una medida diferente. De cualquier manera, el ancho de una descomposición se define de manera que las descomposiciones de tamaño limitadas 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 delimitadas 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 pueden usarse para resolver un problema de manera eficiente, un límite en el ancho de instancias produce necesariamente una restricción estructural manejable . De hecho, un problema de ancho fijo tiene una descomposición de ancho fijo, pero encontrarlo puede no ser polinomio. Para que un problema de ancho fijo se resuelva de manera eficiente por descomposición, se debe encontrar 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 resuelve el problema dada una descomposición de ancho fijo de su tiempo polinomial, sino que también encuentra una descomposición de ancho fijo de un problema de ancho fijo es polinomio- hora.
Métodos de descomposición
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 delimitan los valores de dos nuevas variables para tener como valores dos tuplas que coinciden con las variables originales compartidas. Tres condiciones más 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 principal del nuevo problema sea acíclico. En otras palabras, al ver las variables como vértices y las restricciones (binarias) como bordes, 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 de manera 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 asegurar 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 se puede asociar a varias de las nuevas variables, los valores de estas nuevas variables deben coincidir con el valor de la antigua. Las restricciones binarias se utilizan para hacer cumplir la igualdad de las viejas variables compartidas entre las dos nuevas variables. Dos copias de una nueva variable se fuerzan iguales si existe una ruta de restricciones binarias entre sus nuevas variables y todas las nuevas variables en esta ruta contienen la antigua variable.
Un ejemplo de problema de satisfacción por restricciones; este problema es binario y las restricciones están representadas por los bordes de este gráfico. | |
Un árbol de descomposición; para cada borde del gráfico original, hay un nodo que contiene sus dos extremos; todos los nodos que contienen una variable están conectados | |
Resolver un subproblema. Este ejemplo muestra la resolución del subproblema formado por todas las restricciones sobre las variables del primer conjunto. Se realiza un procedimiento similar para los otros conjuntos y | |
Cada nodo del árbol se convierte en una variable. Su dominio es el conjunto de soluciones del problema parcial, que es un conjunto de tuplas. Las restricciones del nuevo problema permiten solo las tuplas que contienen valores iguales de las variables originales. En la figura, la igualdad de se muestra: la restricción correspondiente solo se cumple con la primera tupla de y la primera tupla de , y por la segunda tupla de y la segunda tupla de . Además, la segunda tupla de no puede encontrar una tupla satisfecha en su hijo izquierdo (). Por tanto, la segunda tupla de debería ser removido. |
Un método de descomposición generalmente se define 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 imposició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 usar 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 suele formular como: el subgrafo inducido por los nodos asociados a una variable original está conectado.
Métodos de descomposición para problemas binarios.
Existen varios métodos de descomposición. La mayoría de ellos generan una clase manejable al delimitar 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 puede hacerse binario traduciéndolo en su problema dual o usando variables ocultas , estos métodos pueden usarse indirectamente para proporcionar una descomposición de árbol para problemas arbitrarios de satisfacción de restricciones.
Componentes biconectados
En la teoría de grafos, un vértice de separación es un nodo de un gráfico que "rompe" el gráfico cuando se quita de él. Formalmente, es un nodo cuya eliminación del gráfico aumenta el número de sus 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 de separación 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 de separación del gráfico; 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 gráfico principal de un problema de satisfacción de restricciones (cada nodo representa una variable y cada borde una restricción entre dos variables) | Sus componentes biconectados (coloreados) y sus vértices separadores (negro, solo uno en este caso) | La descomposición biconectada: los nodos del árbol son vértices separadores y componentes biconectados |
Ciclo de corte
El método de descomposición cíclica divide un problema en partes cíclicas y acíclicas. 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, puede reformularse fácilmente en tales 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 estas variables puede ser acíclico. Formalmente, un corte cíclico de un gráfico es un conjunto de nodos que hace 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 con restricciones utilizando su gráfico principal. El ancho de la descomposición de un ciclo es el número de variables en el corte. El ancho de un problema es el ancho mínimo de sus descomposiciones de conjuntos de cortes de ciclo.
Una representación gráfica de un problema de satisfacción de restricciones. | Un corte de ciclo del gráfico (existen otros) | Eliminando el corte de ciclo, lo que queda es un gráfico acíclico (un árbol, en este caso, pero un bosque en general) |
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 del árbol que resulta de eliminar el corte; esto se hace eligiendo una raíz, agregando 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 corte 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 corte considerado.
Desafortunadamente, determinar el conjunto mínimo a eliminar es un problema NP-Hard .
Descomposición del árbol
La descomposición de árboles es un concepto bien conocido de la teoría de grafos. Reformulado en términos de restricciones binarias, una descomposición de árbol 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 el equivalente del problema original y nuevo.
El ancho de tal 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 de depósitos se puede reformular como un algoritmo que trabaja en la descomposición de un árbol en particular. En particular, dado un orden de las variables, a cada variable se le asocia un depósito que contiene todas las restricciones de manera que la variable sea la mayor en su alcance. La eliminación del depósito corresponde a la descomposición del árbol que tiene un nodo para cada depósito. 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 depósito de es el nodo asociado al cubo de , dónde es el mayor nodo que está en una restricción con y precede en el pedido.
Métodos de descomposición para problemas arbitrarios.
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 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 los nodos del árbol y definen el ancho teniendo en cuenta el número de restricciones asociadas con los nodos. Esto puede reducir el ancho de algunos problemas. Por ejemplo, una descomposición en la que diez variables están asociadas con 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 a esa restricción en su lugar, lo que da como resultado un ancho.
Componentes biconectados
La descomposición biconectada de un problema de satisfacción con restricciones arbitrarias es la descomposición biconectada de su grafo 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 principal, y una camarilla es un componente biconectado o un subconjunto de un componente biconectado.
Descomposición del árbol
Una descomposición de árbol de un problema de satisfacción de restricciones arbitraria es una descomposición de árbol de su gráfico principal. 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, para cada descomposición del árbol, las variables de una camarilla están completamente contenidas en las variables de algún nodo.
Hipercorte de ciclo
Este es el mismo método de corte cíclico que utiliza la definición de corte para hipergráficos: un hipergrama cíclico de un hipergráfico es un conjunto de aristas (en lugar de vértices) que hace que el hipergrama 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 hiperequipos. El ancho de tal 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.
Descomposición de bisagras
Una bisagra es un subconjunto de nodos de 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 hipergráfico cuyos nodos son las variables del problema de satisfacción de restricciones y cuyos hiperfrenos son los alcances de sus restricciones.
La definición de bisagra es la siguiente. Dejarser un conjunto de hiperextensiones. Un camino wrt 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 bordes está conectado wrt si, para cada par de sus bordes, hay un camino wrt de los cuales los dos nodos son el primero y el último borde. Un componente conectado wrt es un conjunto máximo de bordes conectados wrt .
Las bisagras se definen para hipergrafos reducidos, que son hipergrafos en los que no hay hipergrafia en otro. Un conjunto de al menos dos aristas. es una bisagra si, para cada componente conectado wrt , todos los nodos en que tambien estan en están todos contenidos en un solo borde de .
Una descomposición de bisagra se basa en la correspondencia entre los problemas de satisfacción de restricciones y los hipergráficos. El hipergrafo asociado con un problema tiene las variables del problema, ya que los nodos son los alcances de las restricciones como hiperexpresiones. Una descomposición de bisagras de un problema de satisfacción de restricciones es un árbol cuyos nodos son algunas bisagras mínimas del hipergráfico asociado al problema y de manera que se cumplen algunas otras condiciones. Por la correspondencia de problemas con hipergráficos, una bisagra es un conjunto de alcances de restricciones y, por lo tanto, puede considerarse como un conjunto de restricciones. Las condiciones adicionales de la definición de descomposición de 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, entonces 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 su ancho de bisagra.
Agrupación de árboles
La agrupación de árboles o agrupación de árboles de unión se basa en las restricciones de fusión 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, 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 se pueden modificar para adquirir un árbol de combinació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 solo si su grafo primario es cordal y conforme con el problema, esto último significa que las variables de cada camarilla máxima del grafo primario son el alcance de una restricción y viceversa. La agrupación de árboles modifica un problema arbitrario de tal manera que se cumplen estas dos condiciones. La cordalidad se refuerza agregando nuevas restricciones binarias. La conformidad se obtiene fusionando restricciones.
En particular, la cordalidad se refuerza agregando 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 principal del problema. En particular, la cordalidad se obtiene agregando aristas que producen el gráfico inducido del gráfico primario de acuerdo con un orden arbitrario. Este procedimiento es correcto porque la gráfica inducida es siempre cordal y se obtiene agregando 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 una camarilla en el gráfico principal, esta camarilla no es necesariamente máxima. Además, incluso si inicialmente fue máximo, hacer cumplir la cordalidad puede crear una camarilla más grande. La conformidad se refuerza fusionando restricciones. En particular, por cada camarilla máxima del gráfico resultante de hacer cumplir 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 pandilla del gráfico 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.
Un ejemplo: un problema de satisfacción de restricciones binarias (la agrupación de árboles de unión también se puede aplicar a restricciones no binarias). Este gráfico no es cordal (x3x4x5x6 forman un ciclo de cuatro nodos que no tienen acorde). | El gráfico se hace acorde. El algoritmo analiza los nodos de x6 a x1. El borde rojo es el único borde agregado porque x6 es el único nodo que tiene dos padres no unidos. Representa una restricción entre x4 y x5 que se satisface con cada par de valores. | Se identifican las camarillas máximas del gráfico resultante. La agrupación de árboles de unión reemplaza las restricciones en {x3, x4, x5, x6} con dos restricciones equivalentes, una en {x3, x4, x5} y otra en {x4, x5, x6}. |
Esta traducción requiere que se identifiquen las camarillas máximas de un gráfico cordal. Sin embargo, esto se puede hacer fácilmente usando el mismo orden que se usa para hacer cumplir la cordalidad. Dado que los padres de cada nodo están conectados entre sí, las camarillas máximas están compuestas por 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 combinación, y dicho árbol de combinación se puede obtener usando el mismo orden de variables nuevamente. Pasando del último nodo al 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:
- los elementos de la portada son las camarillas del gráfico que resultan de hacer cumplir la cordalidad;
- el árbol es el árbol de unión;
- cada restricción se asigna a todos los nodos del árbol cuyos conjuntos de variables contienen el alcance de la restricción.
El ancho de una descomposición de 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 agrupadas en árboles.
Descomposición de bisagras / agrupaciones
El resultado de la descomposición de las bisagras se puede simplificar aún más descomponiendo cada bisagra mediante la agrupación de árboles. Es decir, una vez identificadas las bisagras, se produce un agrupamiento de árboles de cada una de ellas. En términos del árbol resultante, cada nodo se reemplaza por un árbol.
Descomposición de consultas
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.
La asociación de restricciones con nodos posiblemente reduce 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 tiene un tamaño polinomial; las limitaciones del nuevo problema, al ser igualdades de dos dominios, también son polinomiales en tamaño.
Una representación hipergráfica de un problema de satisfacción de restricciones: las restricciones reciben nombres (P, Q, R, S, T) y sus alcances se muestran (P (a, b, c) significa que la restricción P está en las variables {a , antes de Cristo} | Una descomposición de consultas del problema. Los nodos pueden contener variables, restricciones o ambos. Aunque al nodo más a la derecha se asocian un total de cinco variables (es decir, a, b, c, d, e entre las dos restricciones), esta es una descomposición de ancho 3 porque ningún nodo contiene más de tres restricciones y variables aisladas (hay otra descomposición de ancho 2 y es posible mostrar que esta descomposición de ancho 2 es el ancho mínimo de este hipergráfico). |
Una descomposición de consultas pura es una descomposición de consultas en la que los nodos solo están asociados a restricciones. A partir de una descomposición de consultas de un ancho dado, se puede construir en un espacio logarítmico una descomposición de consultas pura del mismo ancho. Esto se obtiene reemplazando las variables de un nodo que no están en las restricciones del nodo por 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 ancho 4
Descomposición de árboles hipertróficos
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 las siguientes dos condiciones para cumplir:
- cada variable original en un nodo está en el alcance de al menos una restricción asociada con el nodo;
- las variables de las restricciones de un nodo que no son variables del nodo no ocurren en el subárbol enraizado en el nodo.
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 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 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 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 consultas y una restricción existe, 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 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.
Descomposición de hipertárbol generalizada
Las descomposiciones de hipertárbol generalizadas se definen como descomposiciones de hiperárbol, pero se descarta 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 puede resolverse claramente en tiempo polinomial si se da una descomposición de ancho fijo del mismo. Sin embargo, no se sabe que la restricción a un ancho fijo sea 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].
Comparación
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 de acuerdo con una descomposición, más instancias se pueden resolver de manera eficiente usando esa descomposición.
Algunas descomposiciones usan el número de variables de un nodo (o una cantidad similar) como ancho. Otros no: ciclan hipercortes, descomposición de bisagras, descomposición de consultas, descomposición de hiperárboles y descomposición de hiperárboles generalizada asocian restricciones (o sus alcances en forma de hiperexpresiones) 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 sola restricción enlas variables solo se pueden descomponer en un árbol con un solo nodo. Este nodo se puede asociar con elvariables o con la restricción única. Contar el número de variables conduce al ancho, mientras que contar el número de restricciones conduce a ancho .
La comparación entre todos los demás métodos de descomposición se basa en la generalización y la paliza. La generalización significa que cada problema que tiene ancho según un método tiene un ancho delimitado por por un fijo . Batir 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:
- La descomposición de hiperárboles generaliza y supera a todos los demás métodos.
- La descomposición de las bisagras mejorada con la agrupación de árboles generaliza y supera tanto la descomposición de las bisagras como la agrupación de árboles
- la agrupación de árboles es equivalente a la descomposición de árboles (en el gráfico principal)
- Tanto la descomposición de las bisagras como la agrupación de árboles generalizan y superan los componentes biconectados
- el conjunto de corte de ciclo (en el gráfico principal) se generaliza y supera tanto por el hiperciclo de ciclo como por la agrupación de árboles
También se puede demostrar que el ancho de la agrupación de árboles es igual al ancho inducido del problema más uno. El algoritmo de consistencia adaptativa , que es polinomio para problemas de ancho inducido fijo, convierte los problemas en equivalentes de la misma manera que el primer paso de la agrupación de árboles.
Resolviendo a partir de una descomposición
Dado el árbol de una descomposición, se puede resolver construyendo el problema binario similar a un árbol como se describió anteriormente y resolviéndolo. Este es un problema de tiempo polinomial, ya que se puede resolver en tiempo polinomial utilizando, por ejemplo, un algoritmo para hacer cumplir la coherencia 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 transmiten 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 borde 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 desde el nodo al nodo dice cómo los nodos "en el lado de "restringir las variables del nodo .
Si las variables de estos dos nodos son y , los nodos del tamaño de no afectan a todas las variables pero solo las variables compartidas . Como resultado, la influencia sobre de los nodos en el lado de se puede representar como una restricción en las variables . Tal restricción puede verse como un "resumen" de cómo un conjunto de nodos afecta a otro nodo.
El algoritmo procede 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 y envía el resumen de cada nodo para cada hijo. Cuando se alcanzan todas las hojas, el algoritmo se detiene.
Un árbol de descomposición con restricciones asociadas. Todas las variables tienen dominio {0, .., 10} en este ejemplo. | El nodo más a la izquierda contiene la restricción a Estas restricciones permiten que b solo tome valores mayores o iguales que 1. Esta restricción b> 0 se envía a su padre. | El hijo izquierdo de la raíz recibe la restricción b> 0 y la combina con su restricción b | Cuando la raíz ha recibido restricciones para todos sus hijos, las combina y les envía las restricciones. El proceso termina cuando se alcanzan todas las hojas. En este punto, los valores permitidos de las variables son explícitos. |
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.
Si bien 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 los separadores como alcance. Como resultado, una restricción sobre un separador de tamaño puede requerir tamaño para ser almacenado, si todas las variables tienen dominio de tamaño .
Compensación de memoria / tiempo
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 en los separadores se puede hacer mediante la eliminación de variables, que es una forma de inferencia, mientras que los subproblemas se pueden resolver mediante la 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 utilizando 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 aplicar 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 más grande 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 fusionarán 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 combinado 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 otros separadores. Como resultado, se puede aplicar 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 tenga un separador mayor que una cantidad determinada, y no es necesario volver a calcular el tamaño de los separadores durante la ejecución.
Restricciones estructurales
Limitar el ancho de un método de descomposición por 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 restricciones; estos 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 manejabilidad requiere que se cumplan dos condiciones. Primero, si el ancho del problema está limitado por una constante, entonces se puede encontrar una descomposición del ancho limitado en el tiempo polinomial. En segundo lugar, el problema obtenido al convertir el problema original de acuerdo con 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 la fijación del 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 acíclico binario puede reformularse como el problema del ancho de árbol 1; la restricción del ancho inducido (que no se define en términos de descomposición) puede reformularse como agrupamiento 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 principal 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, el establecimiento de satisfacibilidad sigue siendo NP-completo . La tratabilidad se obtiene restringiendo las relaciones; en particular, si un problema tiene ancho y es fuertemente -consistente, se puede resolver de manera eficiente. Ésta es una restricción que no es estructural ni relacional, ya que depende tanto de los alcances como de las relaciones de las restricciones.
Ver también
- Descomposición de árboles en la teoría de grafos
- Algoritmo de árbol de unión utilizado en el aprendizaje automático para extraer la marginación en gráficos generales.
Recursos en línea
Aquí hay algunos enlaces a recursos en línea para la descomposición de árboles / hipertrboles en general.
- Treewidthlib : un punto de referencia para algoritmos para Treewidth y problemas de gráficos relacionados
- Una implementación de C ++ utilizada en el artículo "Un algoritmo completo en cualquier momento para Treewidth, Vibhav Gogate y Rina Dechter, UAI 2004". El enlace es a la página de inicio del autor, donde se distribuyen tanto la fuente LINUX como el ejecutable de Windows.
- Una implementación de Hypertree Decomposition , usando varias heurísticas.
- La herramienta de la barra de herramientas tiene implementación de algunas heurísticas de descomposición de árboles
- Biblioteca TreeD: tiene el código fuente de algunos métodos de descomposición
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7
- Downey, Rod; Michael Fellows (1997). Complejidad parametrizada . Saltador.ISBN 0-387-94883-X
- Gottlob, Georg; Nicola Leone; Francesco Scarcello (2001). "Descomposiciones de Hypertree: una encuesta" . MFCS 2001 . págs. 37–57.[ enlace muerto ]
- Gottlob, Georg; Nicola Leone; Francesco Scarcello (2000). "Una comparación de los métodos de descomposición estructural de CSP" . Inteligencia artificial . 124 (2): 243-282. doi : 10.1016 / S0004-3702 (00) 00078-3 .