LA ESTRUCTURA DE LOS PROBLEMAS

Pasos del algoritmo

1. Elija cualquier variable como la raíz del árbol y ordenar las variables desde la raíz a las hojas. (Elija cualquier variable como la raíz del árbol)

2. Para j desde n hasta 2, aplicar la consistencia de arco al arco (Y, X,), donde X, es el padre de Xj, quitando los valores del DOMINIO[X,] que sea necesario.

3. Para j desde 1 a n, asigne cualquier valor para X, consistente con el valor asignado para X, donde X, es el padre de Xj.

Puntos claves

Hay dos puntos claves a destacar.

Después del paso 2 el PSR es directamente
arco-consistente, entonces la asignación de valores en el paso 3 no requiere ninguna vuelta atrás.

Aplicando la comprobación de consistencia de arco en orden inverso en el paso 2. No se puede arriesgar arcos que ya han sido tratados.

Algoritmo General

1. Elegir un subconjunto S de Variables, de tal forma que el grafo sea un árbol despues de quitar S.

S: Ciclo de Corte

2. Para cada asignación a S:

a. Quitar de los dominios las variables restantes que sean inconsistentes

b. Si el PSR tiene solución, devolverla junto con la asignación para S.

Análisis

Las formas por las cuales la la estructura del problema, representada por el grafo de restricciones, puede utilizarse para encontrar soluciones de forma rápida.

La forma más factible para la resolución sería en la descomposición en muchos subproblemas, llamados SUBPROBLEMAS INDEPENDIENTES.

Esta independencia se averigua buscando COMPONENTES CONECTADOS del grafo de restricciones, de esta forma podemos resolver los problemas más facil y rápidamente.

Descomposición de arbol

Debe satisfacer:

1. Cada variable en el problema original aparece en al menos uno de los subproblemas.

2. Si dos variables están relacionadas por una restricción, deben estar juntas en algun subproblema.

3. Si una variable aparece en dos subproblemas, debe aparecer a cada en cada unión de estos dos.