LA ESTRUCTURA DE LOS PROBLEMAS

更多类似内容

CAMEL CASE JAVA

由JORGE LUIS

Algoritmo y Pseudocódigo

由Jasmin Guerra

Programacion

由Adolfo Mario Viloria Corro

Graficos de Control

由Paola Pinzon

LA ESTRUCTURA DE LOS PROBLEMAS

Descomposición de arbol

Debe satisfacer:

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

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

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

Análisis

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

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

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.

Algoritmo General

2. Para cada asignación a S:

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

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

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

S: Ciclo de Corte

Puntos claves

Hay dos puntos claves a destacar.

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.

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.

Pasos del algoritmo

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.

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.

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)