Embed Size (px)
Citation preview
Relajación Relajación y y
Procesamiento híbrido de Procesamiento híbrido de restriccionesrestricciones
Diferentes técnicas de relajaciónDiferentes técnicas de relajación
Algunas técnicas híbridas popularesAlgunas técnicas híbridas populares
RelajaciónRelajación
Consistencia de nodoConsistencia de nodo
Forward checkForward check
Lookahead checkLookahead check
AC1AC1
AC3AC3
Path-consistencyPath-consistency
3
EjemploEjemplo
4 familias 4 familias AA, , BB, , CC y y DD viven unas junto a otras en viven unas junto a otras en casas numeradas casas numeradas 11, , 22, , 33 y y 44.. DD vive en una casa vive en una casa con número más bajocon número más bajo que que BB,, BB vive vive al lado deal lado de AA en una casa en una casa con número con número
mayormayor,, Hay Hay al menos una casa entreal menos una casa entre BB yy CC,, DD no viveno vive en la casa con número en la casa con número 22,, CC no viveno vive en la casa con número en la casa con número 44..
¿Cuál familia vive en cuál casa ?¿Cuál familia vive en cuál casa ?
El enigma de las 4 casas:El enigma de las 4 casas:
4
Representación:Representación:
Las variables: Las variables: AA, , BB, , CC y y DD Los dominios: dLos dominios: dAA = d = dBB = d = dCC = d = dDD = { = { 11, , 22, , 33, , 44}}
Restricciones:Restricciones: unaria:unaria: r(r(CC) =) = CC 4 4 r(r(DD) =) = DD 22 binaria:binaria:
r(r(AA,,BB) =) = BB == A A + 1+ 1
r(r(BB,,DD) =) = DD BB r(r(BB,,CC) = |) = |BB -- CC| | 1 1
r(r(AA,,CC) =) = A A C C r(r(AA,,DD) = ) = A A DD r(r(CC,,DD) = ) = C C DD
5
Consistencia de nodos:Consistencia de nodos:
Las restricciones unarias son eliminadas por Las restricciones unarias son eliminadas por reducción del dominio:reducción del dominio:
O: consistencia-1O: consistencia-1 (solo 1 variable involucrada)(solo 1 variable involucrada)
r(r(CC) =) = CC 4 4
r(r(DD) =) = DD 22
ddCC = { = { 11, , 22, , 33}}
ddDD = { = { 11, , 33,, 4 4}}
6
Red de restricciones:Red de restricciones:
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{ 1, 2, 3, 4} { 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
Relajación débilRelajación débil
Forward CheckForward Check
Lookahead CheckLookahead Check
8
Forward Check:Forward Check: Asuma que fijamos el valor de 1 variable Asuma que fijamos el valor de 1 variable zizi: : zizi = = aa
Forward Check(Forward Check(zizi) = ) = activar cada restricción r(activar cada restricción r(zizi, , zjzj) o r() o r(zjzj, , zizi) una vez ) una vez
para remover los valores inconsistentes con para remover los valores inconsistentes con zizi = = aa
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{2} { 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
Nuestro ejemploNuestro ejemplo: asumir : asumir AA = = 22 : :
9
Forward check: Forward check: consistencia débilconsistencia débil
Requiere que 1 variable ya haya obtenido un valorRequiere que 1 variable ya haya obtenido un valor sugiere el uso en combinación con backtracking sugiere el uso en combinación con backtracking
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{2} { 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
No produce un No produce un estado consistenteestado consistente no se realiza toda la relajaciónno se realiza toda la relajación
Look ahead checkLook ahead check
Método de relajación más fuerte (débil)Método de relajación más fuerte (débil)
11
Look ahead Check:Look ahead Check: Look Ahead Check = Look Ahead Check =
activar cada restricción r(activar cada restricción r(zizi, , zjzj) exactamente ) exactamente una vez para remover los valores una vez para remover los valores inconsistentes de los dominios inconsistentes de los dominios DiDi y y DjDj..
Nuestro ejemploNuestro ejemplo::
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{ 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3, 4}
12
Ejemplo (continuac.):Ejemplo (continuac.):
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{ 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3}
Las otras 3 restriccionesLas otras 3 restricciones::
13
Look ahead: resultados finales:Look ahead: resultados finales:
AA BB
DDCC
B = A + 1
A C D B
A D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 1, 2, 3}
Aun no produce un Aun no produce un estado consistenteestado consistente no se realiza toda la relajaciónno se realiza toda la relajación
El resultado puede depender del orden en el cual se procesan las restricciones. El resultado puede depender del orden en el cual se procesan las restricciones. La remoción de algunos valores inicialmente puede permitir hallar otros La remoción de algunos valores inicialmente puede permitir hallar otros
inconsistentes.inconsistentes.
Técnicas de consistencia de arcoTécnicas de consistencia de arco
Técnicas que reducen los dominios a Técnicas que reducen los dominios a estados consistentes para cada restricción estados consistentes para cada restricción
(o arco).(o arco).
También llamadasTambién llamadas: técnicas consistencia-2: técnicas consistencia-2
15
AC 1 (Mackworth)AC 1 (Mackworth)AC1:AC1:
RepeatRepeat
Look ahead checkLook ahead check;; IfIf algún valor fue removido de algún valor fue removido de algún dominio algún dominio thenthen
Ocurrió_borradoOcurrió_borrado := verdad:= verdad
UntilUntil (not(not Ocurrió_borradoOcurrió_borrado))
Fuerza a que Look ahead alcance un Fuerza a que Look ahead alcance un estado consistenteestado consistente por reactivación de Look ahead hasta consistenciapor reactivación de Look ahead hasta consistencia
Ocurrió_borradoOcurrió_borrado := falso ;:= falso ;
16
El ejemplo (1):El ejemplo (1):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3, 4}
Primera pasada (== Look ahead check):Primera pasada (== Look ahead check):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 1, 2, 3}
Ocurrió_borradoOcurrió_borrado := verdad:= verdad
17
El ejemplo (2):El ejemplo (2): Segunda pasada:Segunda pasada:
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 1, 2, 3}
Ocurrió_borradoOcurrió_borrado := verdad:= verdad
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 2, 3}
18
El ejemplo (3):El ejemplo (3): Tercera pasada:Tercera pasada:
Ocurrió_borradoOcurrió_borrado := falso:= falso
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 2, 3}
ResultadoResultado: : AA ( (2 o 32 o 3) , ) , BB ( (3 o 43 o 4), ), CC ( (1 o 21 o 2), ), DD ( (1 o 31 o 3))
Consistente, pero ¡¡ NO REALMENTE UNA SOLUCIÓN !!Consistente, pero ¡¡ NO REALMENTE UNA SOLUCIÓN !!
19
AC-3 (Mackworth)AC-3 (Mackworth)Consistencia de arco más Consistencia de arco más
eficiente:eficiente:AC3:AC3:
Remover Remover r(r(xx,,yy)) de de COLACOLA;;
End-WhileEnd-While
COLACOLA := {todas las restricciones en el problema}:= {todas las restricciones en el problema}
Remover todos los valores inconsistentes deRemover todos los valores inconsistentes de
los dominios los dominios DDxx y y DDyy con respecto a con respecto a r(r(xx,,yy));;
WhileWhile not vacia(not vacia(COLACOLA) ) DODO
IfIf algún valor fué removido de algún valor fué removido de DDxx (o (o DDyy)) thenthen agregar todas agregar todas las otraslas otras restricciones restricciones que involucranque involucran xx (o (o yy) a ) a COLACOLA;;
20
El ejemplo (1):El ejemplo (1):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3, 4}
COLA COLA = {r(A,B), r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)}: = {r(A,B), r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)}:
COLACOLA = {r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)} = {r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)}
Para agregar: r(A,C), r(A,D), r(B,C), r(B,D)Para agregar: r(A,C), r(A,D), r(B,C), r(B,D)
Todo ya enTodo ya en COLACOLA ! !
21
El ejemplo (2):El ejemplo (2):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3}
COLACOLA = {r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)}: = {r(A,C), r(A,D), r(B,C), r(B,D), r(C,D)}:
COLACOLA = {r(B,C), r(B,D), r(C,D)} = {r(B,C), r(B,D), r(C,D)}
22
El ejemplo (3):El ejemplo (3):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3}
COLA COLA = {r(B,C), r(B,D), r(C,D)}: = {r(B,C), r(B,D), r(C,D)}:
COLACOLA = {r(B,D), r(C,D), = {r(B,D), r(C,D), r(A,B), r(A,C)r(A,B), r(A,C)}}
Para agregar: r(A,B), r(A,C), r(B,D), r(C,D)Para agregar: r(A,B), r(A,C), r(B,D), r(C,D)
23
El ejemplo (4):El ejemplo (4):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3, 4}
{ 1, 2, 3}
COLACOLA = {r(B,D), r(C,D), r(A,B), r(A,C)}: = {r(B,D), r(C,D), r(A,B), r(A,C)}:
COLACOLA = {r(C,D), r(A,B), r(A,C) = {r(C,D), r(A,B), r(A,C), r(A,D), r(A,D)}}
Para agregar: r(A,D), r(C,D)Para agregar: r(A,D), r(C,D)
24
El ejemplo (5):El ejemplo (5):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 1, 2, 3}
COLACOLA = {r(C,D), r(A,B), r(A,C), r(A,D)}: = {r(C,D), r(A,B), r(A,C), r(A,D)}:
COLACOLA = {r(A,C), r(A,D)} = {r(A,C), r(A,D)}
Para agregar: r(A,C), r(A,D)Para agregar: r(A,C), r(A,D)
25
El ejemplo (6):El ejemplo (6):
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 3, 4}
{ 1, 2} { 1, 3}
{ 2, 3}
COLACOLA = {r(A,C), r(A,D)}: = {r(A,C), r(A,D)}:
COLACOLA = vacía = vacía
¡ PARAR !¡ PARAR !
26
Comparación:Comparación:
Igual resultado: completa consistencia de arco:Igual resultado: completa consistencia de arco: A = {2,3}, B = {3,4}, C= {1,2}, D = {1,3} A = {2,3}, B = {3,4}, C= {1,2}, D = {1,3}
Eficiencia:Eficiencia: AC1: AC1:
3 veces 6 verificaciones = 3 veces 6 verificaciones = 1818 AC3:AC3:
99 verificacíones de restricciones verificacíones de restricciones
27
Consistencia-k:Consistencia-k: consistencia-1consistencia-1 (consistencia de nodo): (consistencia de nodo):
restricciones unarias (en 1 variable) son consistentesrestricciones unarias (en 1 variable) son consistentes
consistencia-2consistencia-2 (consistencia de arco): (consistencia de arco): restricciones binarias (en 2 variables) son consistentesrestricciones binarias (en 2 variables) son consistentes
consistencia-3consistencia-3:: todas las restricc. que involucran 3 variables son consist.todas las restricc. que involucran 3 variables son consist.
AA BB
DDCC
B = A + 1
A C D BA D
|B - C| 1
C D
{ 1, 2, 3, 4}
{ 1, 2, 3} { 1, 3, 4}
{ 1, 2, 3, 4}
Un valor Un valor se mantienese mantiene en el dominio si hay valores en el dominio si hay valores consistentes en los dominios de las otras 2 variables consistentes en los dominios de las otras 2 variables (para todas las restricciones que las conectan)(para todas las restricciones que las conectan)
Ejemplo:Ejemplo:
28
Practicidad de la consistencia k:Practicidad de la consistencia k:
VerificarVerificar la consistencia-k para k la consistencia-k para k 2 es muy 2 es muy dificil de realizar eficientemente !!dificil de realizar eficientemente !!
Ejemplo:Ejemplo: consistencia-4 para el enigma de las consistencia-4 para el enigma de las 4 casas es equivalente a hallar soluciones del 4 casas es equivalente a hallar soluciones del problema original.problema original.
Procesamiento híbrido de Procesamiento híbrido de restriccionesrestricciones
Combina el poder de laCombina el poder de la
búsqueda exhaustiva (backtrack)búsqueda exhaustiva (backtrack)
con (relajación) podacon (relajación) poda
Forward checkingForward checking
Backtracking combinado Backtracking combinado con Forward Checkcon Forward Check
31
Forward checking:Forward checking:
Forward Checking:Forward Checking:
ExecuteExecute Standard BacktrackingStandard Backtracking
AfterAfter cada asignación de un cada asignación de un valor a una variable valor a una variable zizi DODO
Forward Check(Forward Check(zizi))
BUTBUT
32
11AA
Funcionamiento de forward checkingFuncionamiento de forward checking
BB
22
AA BB
CC DD
{1}{1} {1,2,3,4}{1,2,3,4}
{1,2,3}{1,2,3} {1,3,4}{1,3,4}
B=A+1B=A+1
AADDAACC
AA BB
CC DD
{1}{1} {2}{2}
{2,3}{2,3} {3,4}{3,4}
|B-C||B-C|11
DD B B
fallafalla
AA BB
CC DD
{2}{2} {1,2,3,4}{1,2,3,4}
{1,2,3}{1,2,3} {1,3,4}{1,3,4}
B=A+1B=A+1
AADDAACC
22
BB33
AA BB
CC DD
{2}{2} {3}{3}
{1,3}{1,3} {1,3,4}{1,3,4}
|B-C||B-C|11
DD B B
CC11
AA BB
CC DD
{4}{4} {3}{3}
{1}{1} {1}{1}CCDD
fallafalla
AA BB
CC DD
{3}{3} {1,2,3,4}{1,2,3,4}
{1,2,3}{1,2,3} {1,3,4}{1,3,4}
B=A+1B=A+1
AADDAACC
33
BB44
AA BB
CC DD
{3}{3} {4}{4}
{1,2}{1,2} {1,4}{1,4}
|B-C||B-C|11
DD B B
AA BB
CC DD
{3}{3} {4}{4}
{1}{1} {1}{1}CCDD
AA BB
CC DD
{3}{3} {4}{4}
{2}{2} {1}{1}CCDD
11 CC 22
fallafalla exitoexito
Lookahead checkingLookahead checking
Backtracking combinado Backtracking combinado con Look ahead checkcon Look ahead check
34
Lookahead checking:Lookahead checking:
ExecuteExecute Standard BacktrackingStandard Backtracking
Look Ahead CheckLook Ahead Check
BUTBUT
Look Ahead Check Look Ahead Check ;;
Lookahead Checking:Lookahead Checking:
AfterAfter cada asignación de un cada asignación de un valor a alguna variable valor a alguna variable DODO
35
Funcionamiento de lookahead checkingFuncionamiento de lookahead checking
AA BB
CC DD
{1,2,3,4}{1,2,3,4} {1,2,3,4}{1,2,3,4}
{1,2,3}{1,2,3} {1,3,4}{1,3,4}
B=A+1B=A+1
AADDAACC DD B B|B-C||B-C|11CCDD
AA BB
CC DD
{1}{1} {3,4}{3,4}
{1,2}{1,2} {1,3}{1,3}
B=A+1B=A+1
fallafalla
AA BB
CC DD
{2}{2} {3,4}{3,4}
{1,2}{1,2} {1,3}{1,3}
B=A+1B=A+1
AADDAACC DD B B|B-C||B-C|11CCDD
fallafalla
AA BB
CC DD
{3}{3} {3,4}{3,4}
{1,2}{1,2} {1,3}{1,3}
B=A+1B=A+1
AADDAACC DD B B|B-C||B-C|11CCDD
AA BB
CC DD
{3}{3} {4}{4}
{2}{2} {1}{1}
DD B B|B-C||B-C|11
CCDD
AA BB
CC DD
{3}{3} {4}{4}
{2}{2} {1}{1}CCDD
11 AA
22
33
BB 44
CC22
exitoexito
36
¿Cuál es mejor?¿Cuál es mejor? Forward checking:Forward checking:
hace menos verificación de consistenciahace menos verificación de consistencia tiene mas ramificacióntiene mas ramificación
más cercano a backtrackingmás cercano a backtracking
Lookahead checking:Lookahead checking: lleva más tiempo con consistencialleva más tiempo con consistencia intenta menos valor alternativosintenta menos valor alternativos
Usualmente: forward checking es la mejor solución de compromisoUsualmente: forward checking es la mejor solución de compromiso Para problemas MUY restringidos:Para problemas MUY restringidos:
Lookahead checking es necesario para podar másLookahead checking es necesario para podar más
37
Aplicaciones:Aplicaciones:
Todos los problemas de búsqueda combinatoriosTodos los problemas de búsqueda combinatorios Problemas de distribución de tareas:Problemas de distribución de tareas:
Ej.:Ej.: redistribución de horario de trenes cuando ha ocurrido algun problema en las vías. redistribución de horario de trenes cuando ha ocurrido algun problema en las vías.
Problemas de distribución de trabajos:Problemas de distribución de trabajos: Ej.:Ej.: computar turnos de trabajo, dadas varias res- computar turnos de trabajo, dadas varias res-
tricciones de expertise y preferencias personalestricciones de expertise y preferencias personales
Planeamiento de producción:Planeamiento de producción: Ej.:Ej.: planificar el flujo óptimo de trabajo planificar el flujo óptimo de trabajo
Problemas de carga:Problemas de carga: Ej.:Ej.: optimizar el espacio en un camión dados varios tipos de cargas optimizar el espacio en un camión dados varios tipos de cargas
38
Técnicas alternativasTécnicas alternativas Programación linealProgramación lineal
técnicas numéricas para la resolución de sistemas de ecuaciones lineales (e inecuaciones) + problemas de optimizacióntécnicas numéricas para la resolución de sistemas de ecuaciones lineales (e inecuaciones) + problemas de optimización Ej.:Ej.: algoritmo simplex algoritmo simplex
Funciona MUY bien para restricciones ‘lineales’ Funciona MUY bien para restricciones ‘lineales’
4*X - 3*Y 4*X - 3*Y Z + 2 Z + 2
XX33 - 3*Y - 3*Y Z Z22 + 2 + 2
¡ SI !¡ SI !
¡ NO !¡ NO !
Funciona, pero no MUY bien, para problemas discretos Funciona, pero no MUY bien, para problemas discretos
En tales casos:En tales casos: Procesam. de Restricc. es una mejor opción Procesam. de Restricc. es una mejor opción
También: para problemas de restricciones en También: para problemas de restricciones en datos no-numericosdatos no-numericos ! !
![Aprende a relajarte - Técnicas de Relajación [C78]](https://img.pdfslide.es/doc/110x75/55cf9cd0550346d033ab232a/aprende-a-relajarte-tecnicas-de-relajacion-c78.jpg)
