Apunts PSR V3

7/28/2019 Apunts PSR V3

1/183

Problemas de satisfaccin derestricciones

Constraint Satisfaction Problems

Inteligencia Artificial.Gabriel Fiol

1


2/183

Objetivos del tema Estudiar diferentes alternativas en cuanto a

modelos y tcnicas usadas para resolverproblemas de satisfaccin de restricciones

las tcnicas presentadas.


2


3/183

ndice

1. Introduccin2. Resolucin de un problema de satisfaccin de restricciones.

3. Formulacin del problema de satisfaccin de restricciones.

- Descripcin formal de un PSR.- Clasificacin de los PSR.

- Ejemplos.


3

- Grafo de Restricciones.4. Resolucin de un PSR en trminos de una bsqueda.

- Formulacin de un PSR en trminos de una bsqueda

estndar.- Bsqueda con vuelta atrs para un PSR.


4/183

5. Tcnicas para la mejora de la eficincia.

- Heursticas para la seleccin de variable y ordenamientode valor.

- Propagacin de la informacin a travs de lasrestricciones.

- Comprobacin hacia delante.- Consistencia de arco y consistencia fuerte.

- Manejo de restricciones especiales.

- Vuelta atrs inteligente: mirando hacia atrs.6. Bsqueda local para problemas de satisfaccin de

restricciones.

7. La estructura de los problemas.


4


5/183

Bibliografa bsica

Apuntes del profesor.

Inteligencia Artificial. Un Enfoque Moderno (2a Ed.)S. Russell, P. Norvig


5


6/183

1. Introduccin

Muchos de los problemas de la IA pueden contemplarsecomo problemas de verificacin de restricciones

constraint satisfaction problems, donde el objetivoconsiste en descubrir algn estado del problema quesatisfaga un conjunto dado de restricciones.


6


7/183

Ejemplo 1. El diseo de tareas puede contemplarse como unproblema de verificacin de restricciones donde el proceso dediseo debe realizarse dentro de unos lmites fijos de tiempo,coste y materiales.


7


8/183

Ejemplo 2. El problema de las n-reinas. Deben situarse nreinas en un tablero de nxn de manera que no exista jaqueentre ellas.


8


9/183

Ejemplo 3. Coloreado de mapas. Usando tres colores (rojo,verde, azul), colorear cada una de las provincias deAndalucia de manera que dos provincias adyacentes(vecinas) no posean el mismo color.


9


10/183

Ejemplo 4. Satisfactibilidad proposicional. Dado unconjunto L de variables proposicionales y un conjunto Cde clusulas formadas con los smbolos de L,determinar si existe una asignacin de valores deverdad a los smbolos de L de manera que se satisfagantodas las clusulas.


10


11/183

Ejemplo 5. La elaboracin de un horario de clases para los

cuatro cursos del Grado en Informtica exige que cadacurso se imparta en un horario de maana, tarde, o ambos.

Los horaris de maana deben ajustarse de 8.30 a 14h loslunes y miercoles, de 8 a 13 los martes y jueves y de 8.30 a11 los viernes.

Adems, no pueden impartirse ms de un nmero dado de

en la medida de lo posible a las preferencias de losprofesores.

Tambin debe haber un hueco de 10 minutos entre clase y

clase, sin otros huecos temporales vacios entre clases.


11


12/183

Ejemplo 6. Suma criptoaritmtica. Asignar valores del 0 al

9 a cada letra de manera que la suma de dos palabras seaaritmticamente correcta.


12


13/183

Ejemplo 7. Planificacin. Dada una empresa de transporte,establecer una planificacin diaria de las tareas para los

diferentes conductores de la empresa, de manera quetodas las tareas se lleven a cabo en el horario de trabajo yse satisfagan los requerimientos de los clientes (pore em lo h t re s ue se exi e ue se lleven c bo

una hora prevista, otras pueden realizarse a cualquier horadel dia).


13


14/183

Algunos problemas como los mencionados pueden

resolverse mediante tcnicas de bsquedaconvencionales.

De hecho, la bsqueda en un espacio de estadoscontinuar siendo el mtodo bsico de resolucindel problema.


14


15/183

No obstante, al contemplar la solucin de unproblema como una verificacin de restricciones,es frecuentemente posible una reduccinsustancial en la cantidad de bsquedas que se

necesitan, pues ahora:1. El planteamiento del problema en trminos de la

proceso de bsqueda de una solucin.

2. Slo se pretende alcanzar un estado que satisfaga lasrestricciones consideradas y no un estado ptimo.


15


16/183

2. Resolucin de un problema de

satisfaccin de restricciones (PSR) La resolucin de un PSR se desarrolla en las siguientes

etapas:

Definicin formal del PSR formulacin del problema entrminos de un PSR-.

de una bsqueda.

Consideracin de las heursticas mejora de la eficienciacomputacional-.

Consideracin de las tcnicas de comprovacin haciaadelante.

Codificacin.Inteligencia Artificial.

Gabriel Fiol16


17/183

3. Formulacin del problema de

satisfaccin de restricciones (PSR) Dado un problema a resolver, la primera etapa consiste

en formular definir formalmente- el problema entrminos de un PSR.

Esta eta a es mu im ortante, ues:

Si no se formula el problema, entonces no podr resolversecon las tcnicas que se presentan.

La formulacin debe permitir una resolucin eficiente del

problema. Dependiendo del tipo de formulacin puedenexistir varias- la resolucin del problema puede ser ms omenos eficiente.


17


18/183

Primera definicin (general) de un PSR

Se considera un estado inicial formado por un conjunto deobjetos o variables, cada una de los cuales tiene establecidos

un conjunto de valores sobre determinados parmetros. Setrata de alcanzar un estado en el que los valores de losparmetros de cada uno de los objetos satisfagan


18


19/183

Ejemplo 1. El problema de situar 8 reinas en un

tablero de ajedrez de manera que ninguna de ellashaga jaque a cualquier otra:

- Las variables u objetos son las ubicaciones decada una de las 8 reinas en cada columna,estoes, los cuadrados del tablero ocupados por lasreinas. Habr por tanto 8 variables.


19

-haber dos reinas en una misma fila, columna odiagonal los parmetros aqu son la fila, lacolumna y la diagonal de cada ubicacin.

Un estado solucin contendra, por tanto, valorespara todas las variables de manera que todas lasrestricciones son satisfechas.


20/183

Ejemplo 2. Considrese la siguiente suma cripto-aritmtica:

T W O+ T W O

F O U R

El objetivo del problema es asignar un valor numrico diferente,0..9, a cada una de las letras de la suma, de forma que sta seaaritmticamente correcta.

(Xc3 Xc2 Xc1)

as var a es son ca a una e as etras que orman parte eproblema. En este caso hay seis: T, W, O, F, U, R. Adems,deben considerarse las variables de acarreo adicionales.

Las restricciones especifican que todas las letras tenganvalores diferentes y que se cumplan las reglas de la suma. Eneste caso:


20


21/183

Algunos aspectos a considerar:

1. Pueden existir dependencias entre las restricciones.

2. Sobre una misma variable pueden establecersemuchas restricciones recurdese que sobre un objeto

ueden consider rse diversos r metros un mismo


21

parmetro puede participar de varias restricciones.3. Una misma restriccin puede estar definida sobre

muchos objetos, esto es, puede involucrar muchas

variables un mismo parmetro puede considerarsesobre varios objetos.


22/183

Descripcin formal del problema de satisfaccin derestricciones

Sea X1, X2,, Xnun conjunto de variables, con dominios de valoresno vacos, D1, D2,, Dn, respectivamente, siendo Di el dominio de Xi,i=1n.

Sea C1, C2,, Cm, un conjunto de restricciones, cada una de las cualesenvuelve algn subconjunto de variables y especifica las combinacionesaceptables de valores para ese subconjunto.

Un estado, S, del problema viene definido por una asignacin de= =


22

. , ,

para algn i=1, 2,, n; vkDi}. Una asignacin que no viola ninguna restriccin se llama una

asignacin consistente o legal.

Una asignacin completa es aquella en la que se hace mencin a cada

variable. Una solucin de un PSR es una asignacin completa que satisface

todas las restricciones. Esto es, es una asignacin completaconsistente.


23/183

Clasificacin de los PSR

Clasificacin segn el tipo de restricciones: Restricciones de obligacin (hard constraints). Restricciones de preferencia (soft constraints). Se emplean para

maximizar/minimizar una funcin objetivo.

Clasificacin segn los dominios: Dominios discretos (finitos o infinitos). Dominios contnuos.

Clasificacin segn el nmero de variables implicadasen las restricciones: Restricciones unarias. Restricciones binarias. Restricciones mltiples o de alto orden.


23


24/183

En este tema trataremos PSRs:

Con dominios finitos.

Con restricciones de obligacin.

Todo problema con restricciones mltiples sepuede reducir a uno equivalente con restricciones

binarias.


24


25/183

Ejemplos

Ejemplo 1. El problema del coloreado de zonasConsidrese la tarea de colorear cada zona del mapa demanera que ninguna de las partes adyacentes tenga el mismo

color.Los colores que pueden usarse son el rojo, el verdey el azul.


25

AO

TN

AS

Q

NGS

V

T


26/183

Formulacin del problema en trminos de un PSR

Variables del problema: cada una de las zonas a colorear.Estas son: Xi = {AO, TN, AS, Q, NGS, V, T}.

Dominios de las variable: el conjunto Di={rojo, verde, azul}.

Restricciones: P Q, para cada par de provincias vecinas P


26

y .

Problema con dominios finitos y restricciones binarias (deobligacin).


27/183

Por ejemplo, las combinaciones aceptables para AO y TNson los pares:

{(rojo, verde), (rojo, azul), (verde, rojo), (verde, azul), (azul,rojo), (azul, verde)}

Existen numerosas solucionesposibles, como por ejemplo:

{AO=rojo, TN=verde, Q=rojo, NGS=verde, V=rojo, AS=azul,T=rojo}


27

AO

TN

AS

Q

NGS

V

T


28/183

Ejemplo 2. El problema de las N reinas.

Situar N reinas en un tablero de ajedrez de tamao N x N, demanera que no exista jaque entre ellas.

Variables: la ubicacin de cada reina. Hay en total N: {X1,..., Xn}.

Dominios: los valores que cada variable puede adoptar. Seconsidera que cada reina est en una columna. Entonces el dominiode valores de cada reina ser la fila en la que la reina puede

=

Restricciones: Jaque horizontal: Xi Xj (dos reinas no pueden estar en la

misma fila).

Jaque diagonal: ||||Xi - Xj|||| ||||i - j|||| (la diferencia entre las filas y lascolumnas de las dos reinas debe ser diferente).

Problema con dominios finitos y restricciones binarias (deobligacin).


28


29/183

CONCLUSIONES

Existe posiblemente ms de una manera de formular unproblema en trminos de un PSR.

Dependiendo del tipo de formulacin, la solucin alproblema puede resultar ms o menos complejacomputacionalmente, tal como ocurre en la formulacin deun roblema en trminos de una bs ueda estndar.

Este aspecto se tratar en el prximo punto.


29


30/183

TALLER-1 Formular en trminos de un PSR el siguiente problema.

Dado un conjunto L de variables proposicionales y unconjunto C de clusulas escritas en trminos de lasvariables de L, determinar si existe una asignacin devalores de verdad (verdadero, falso) a los smbolos de L demanera ue se satisfa an todas las clusulas.

De qu tipo de PSR se trata? Cul es la dimensin del espacio de soluciones del

problema?


30


31/183

TALLER-2 Formular en trminos de un PSR el siguiente problema.

Asignar valores del 1 al 9 a cada letra de manera que:T W O

+ T W O

F O U R De qu tipo de problema se trata?


31


32/183

TALLER-3 Considera el problema de la asignacin de tareas

(scheduling) a empleados segn su capacidad (se asignauna tarea a cada empleado), de manera que se pretendealcanzar una asignacin ptima.

Se considera que se tiene una tabla de capacidades, C:

Formular el anterior problema en trminos de un PSR De qu tipo de problema se trata? NOTA: considrese la posibilidad de usar restricciones de preferencia.


32

T1 T2 T3

E1 1 3 2

E2 3 2 3

E3 2 3 1


33/183

TALLER-4 Considrese una empresa de transportes con nconductores y m

tareas (transportes). Cada tarea mi tiene una duracin,determinada por su hora de inicio y su hora de final en la que

debe realizarse. Un conductor slo puede realizar un transporte en un momento

dado, por tanto, dos tareas que tengan una interseccin temporal

necesariamente por dos transportistas. Se trata de hacer una asignacin de tareas a conductores para un

cierto dia, de manera que se respeten los horarios de realizacinde las tareas.

Formular el anterior problema en trminos de un PSR

De qu tipo de problema se trata?


33


34/183

TALLER-5 Considera el problema de la asignacin de tareas a empleados

segn su capacidad (taller 3), de manera que ahora una tareapuede asignarse a ms de un empleado.

Se pretende alcanzar una asignacin ptima.Se considera que se tiene una tabla de capacidades, C:

Formular el anterior problema en trminos de un PSR De qu tipo de problema se trata? NOTA: considrese la posibilidad de usar restricciones de preferencia.


34

E1 1 3 2

E2 3 2 1

E3 2 3 1


35/183

Grafo de restricciones

Un PSR puede ilustrarse de forma clara medianteun grafo de restricciones.

Los nodos del grafo corresponden a variables delproblema.

os arcos represen an as res r cc ones.


35



36/183


Ejemplo

AO

TN

AS

Q

NGS

V

T


36

AO

TN

AS

Q

NGS

VT

Tipos de restricciones segn el nmero de


37/183

Tipos de restricciones segn el nmero devariables implicadas

Restricciones unarias: son las ms simples, restringen losvalores de una sola variable.

Por ejemplo, en la coloracin de cuadros del anteriorejemplo podra establecerse que AS verde.

Una restriccin unaria puede eliminarse preprocesando eldominio de la variable afectada, eliminando simplementecual uier valor ue viole la restriccin.


37

Restricciones binarias: relacionan dos variables.Por ejemplo, en la coloracin de cuadros del ejemploanterior podra exigirse que AS NGS.

Un PSR binario es un problema con restricciones slobinarias, y puede representarse como un grafo derestricciones tal como el ilustrado en el ejemplo anterior.


38/183

Restricciones mltiples o de alto orden: implican tres oms variables.

Ejemplo. Puzzles cripto-aritmticos.

Inteligencia Artificial.Gabriel Fiol 38

Ejemplo Considrese la sig iente s ma cripto aritmtica


39/183

Ejemplo. Considrese la siguiente suma cripto-aritmtica:

T W O+ T W O

F O U R

Variables principales del problema: (F, T, U, W, R, O).

La restriccin ue establece ue todas las variables deben ser

(Xc3 Xc2 Xc1)


diferentes, todasdif(T, W, O, F, U, R), puede enfocarse diferentesperspectivas:

a. Por una parte puede considerarse como una nica restriccinque afecta a las seis variables.

b. Por otra puede considerarse como una coleccin derestricciones binarias.


40/183

Variables auxiliares: Xc1, Xc2y Xc3. Son binarias.

Descripcin de las restricciones que afectan a las variablesauxiliares:

O + O = R + 10Xc1

Xc1 + W + W = U + 10Xc2

Xc2+ T + T = O + 10Xc3


c3=

Cada ecuacin representa una restriccin.

Como en las ecuaciones excepto la ltima- participan ms dedos variables, entonces deben ser enfocadas como

descripciones de alto orden.

El siguiente hiper-grafo de restricciones constituye una representacin


41/183

El siguiente hiper-grafo de restricciones constituye una representacindel PSR mediante restricciones de alto orden.

Cada restriccin viene representada por un cuadrado que relaciona lasvariables que retringe.

todasdif(T, W, O, F, U, R)

O + O = R + 10Xc1

Xc1 + W + W = U + 10Xc2

=

U WF T R O


Xc3= F

De manera general, una restriccin de alto orden y dominio finito puedereducirse a un conjunto de restricciones binarias si se introducensuficientes variables auxiliares.

X c3 X c1X c2


42/183

Restricciones de obligacin y de preferencia

En las restricciones de obligacino restricciones absolutas-,cualquier solucin resulta igualmente aceptable.

Las restricciones de preferencia se refieren a las solucionespreferidas.

Por ejemplo, en el problema de los horarios de una escuela el

profesor Y prefiere ensear por la tarde. Un horario en el que elprofesor X deba ensear a las cuatro de la tarde constituye unasolucin, pero no un ptimo.

Las restricciones de preferencia pueden a veces codificarse comocostos sobre las asignaciones de variables individuales porejemplo, asignar un intervalo por la tarde al profesor X cuesta trespuntos sobre la funcin objetivo, mientras que asignrselo por lamaana cuesta un punto.


Cuando en un problema existen restricciones de obligacin


43/183

Cuando en un problema existen restricciones de obligaciny de preferencia, slo estas ltimas tendrn un costo

asignado.Por homogeneidad en el manejo de los costes, a lasrestricciones de obligacin puede asignrseles un coste 0.

Los algoritmos que manejan restricciones de preferenciapueden implementarse con la misma tcnica que que losque slo usan restricciones de obligacin, pero haciendouso de la tcnica de ramificacin oda con ob eto dedetectar cundo una solucin parcial no puede aspirar a serptima.


4 R l i d PSR i d


44/183

4. Resolucin de un PSR en trminos de

una bsqueda La resolucin de un PSR puede concebirse mediante un

procedimiento de bsqueda en un espacio de restriccionesestablecidas sobre los parmetros de un conjunto devariables, de manera que cada valor susceptible de ser

restriccin sobre el mismo.


Ventajas:


45/183

Ventajas:

Los estados pueden representarse de manera estndar,como un conjunto de variables con valores asignados.

La funcin sucesor y el test objetivo pueden considerarse

de forma genrica, aplicndose a todo PSR. Pueden desarrollarse heursticas eficaces y genricas que

no requieran ninguna informacin adicional ni experta sobre


el dominio especfico del problema.

Pueden usarse tcnicas para detectar las podas poradelantado, sin necesidad de explorar regiones del rbolque no conducen a una solucin.

La estructura del grafo de restricciones puede usarse parasimplificar el proceso de bsqueda de una solucin.

Formulacin de un PSR entrminos de un


46/183

problema de bsqueda estndar:

Estado inicial. La asignacin vaca, { }, en la que ninguna de lasvariables ha recibido asignacin alguna.

Operadores. Un operador se basa en una asignacin de un valor auna variable no asignada que no genere ningn conflicto convariables ya asignadas.

Test objetivo. La asignacin actual es una asignacin completa.

Coste de ruta. Un coste constante para cada paso. Toda solucin es una asignacin completa que aparece a

profundidad npara un problema de nvariables.

Adems, el rbol/grafo de bsqueda se extiende slo a profundidad

n.Por tanto, un algoritmo basado en una bsqueda primero enprofundidad parece, en principio, adecuado para un PSR.


Consideraciones generales sobre la eficiencia


47/183

Consideraciones generales sobre la eficiencia.

Si el tamao del dominio de toda variable en un PSR es d,entonces el nmero de posibles asignaciones completas es(dn), siendo nel nmero de variables.

As, en el peor de los casos no puede esperarse la resolucinde un PSR con dominio finito con un tiempo menor alexponencial.


Ejemplo. El problema de las n reinas con X1, X2,, Xn, querepresentan las posiciones de cada reina en las columnas 1,2,, n respectivamente, cuyos dominios D1, D2,, Dn, sonidnticos, con ocho valores, uno para cada fila del tablero, esto

es, Di= {1, 2, 3, 4, ,n}, i = 1n.La eficiencia en el peor de los casos es (nn)


48/183

Las variables discretas pueden tambin tener dominiosinfinitos, por ejemplo, el conjunto de los nmeros enteros,o el conjunto de todas las cadenas de caracteres.

Ejemplo: cuando se requieren programar trabajos deconstruccin en el calendario, la fecha de inicio de cadatrabajo es una variable, y sus valores posibles es el nmerode das enteros a partir de la fecha actual.


Con tales dominios no es posible describir las restriccionesenumerando todas las combinaciones permitidas devalores, para ello debe utilizarse lo que se conoce como unlenguaje de restriccin.


49/183

Por ejemplo, si Trabajo1 toma 5 das, y debe preceder a

Trabajo3, entonces necesitaramos un lenguaje derestricciones de desigualdades algebraicas tal como

InicioTrabajo1 + 5 InicioTrabajo3


L PSR d i i t


50/183

Los PSR con dominios contnuos son muy comunes en

el mundo real y se estudian extensamente en el campo dela investigacin operativa.

La categora ms conocida de PSR con dominios

contnuos son los problemas de programacin lineal. Tales problemas pueden resolverse en tiempo polinomial

en el nmero de variables.


Bsqueda con vuelta atrs para PSRs


51/183

En principio, cualquiera de los algoritmos de bsqueda vistoshasta el momento puede ser utilizado para resolver los PSRs;no obstante, su eficiencia puede variar sensiblemente deunos a otros.

Estado inicial. La asignacin vaca, { }, en la que ninguna delas variables ha recibido asignacin alguna.


Operadores. Un operador se basa en una asignacin de un

valor a una variable no asignada que no genere ningnconflicto con variables ya asignadas.

Test objetivo. La asignacin actual es una asignacincompleta.

Coste de ruta. Un coste constante para cada paso.

Bsqueda primero en anchura


52/183

Bsqueda primero en anchura.

Considrese la solucin de un PSR con nvariables y dominiosdiscretos finitos, con dvalores cada dominio, como sigue:

(1) Partiendo de la asignacin vaca, { }, como estado inicial,

existen ndposibles operadores aplicables recurdese queun operador asigna un valor a una variable no asignada queno genere un conflicto con variables ya asignadas.


(2) En el siguiente nivel el factor de ramificacin para cadauno de los nodos resultantes es (n-1)d, y as sucesivamentepara nniveles.

El resultado ser la generacin de un rbol con n!dnhojas,

aunque slo haya dnasignaciones posibles completas !!!.

Conmutatividad de los PSR.


53/183

La razn del elevadsimo coste del anterior algoritmo seencuentra en el hecho de que una misma asignacin aparecenumerosas veces pero con el orden en que las variables hansido asignadas permutado.

Como cualquier permutacin de una misma asignacin produceidnticos resultados, entonces con la aparicin de una sola delas permutaciones durante el proceso de bsqueda ser


.

Este hecho se conoce como la propiedad de conmutatividadde un problema.

Se dice que un problema es conmutativo si el orden deaplicacin de cualquier conjunto de acciones no tiene ningnefecto sobre el resultado.

Por tanto, los algoritmos de bsqueda debern tener en cuentaesta importante propiedad.

Solucin a la conmutatividad.


54/183

Todos los algoritmos de bsqueda para un PSR generan los sucesoresde un nodo considerando nicamente las posibles asignaciones para unasola variable del mismo.

Con esta consideracin el nmero de nodos hoja es dn.

{ }

AO = rojo AO = verde AO = azul


AO = rojoTN = verde

AO = rojoTN = azul

AO = rojoTN = verdeQ = rojo

AO = rojoTN = verdeQ = azul

Bsqueda primero en profundidad con


55/183

q p p

vuelta atrs. La bsqueda primero en profundidad con vuelta atrs

proporciona una tcnica sencilla y til para superar la

conmutatividad. En cada paso se eligen valores para una misma variable,


legal para asignarle. El siguiente algoritmo constituye un modelo de lo dicho.

Como la formulacin de los PSR est estandarizada, no hayninguna necesidad de proporcionar al algoritmo un estadoinicial del dominio especfico, una funcin sucesor o un testobjetivo.

funcinBsqueda-Con-Vuelta-Atrs(PSR) devuelveuna solucin o fallodevolverVuelta-Atrs-Recursiva({}, PSR)


56/183

({}, )

funcinVuelta-Atrs-Recursiva(asignacin, PSR) devuelveuna solucin o fallo

Inicio

siasignacin es completaentonces devolverasignacin

varSelecciona-variable-no-asignada(variables(PSR), asignacin, PSR)

paracada valor enorden-valores-dominio(var, asignacin, PSR) hacer

sivalor es consistente con asignacin en restricciones(PSR) entonces

aadir {var = valor} a asignacin

resultadoVuelta-Atrs-Recursiva(asignacin, PSR)


siresultado falloentonces devolverresultado

sinoborrar({var = valor}) de asignacin

fin si;

sinono hacer nada (*se prueba con el siguiente valor a travs del bucle*)

fin si

fin para;

devolverfallo

fin;

Consideraciones sobre el algoritmo.


57/183

El nmero total de nodos hoja (asignaciones completas) es dn,para un PSR con nvariables y dvalores de los dominios.

El anterior algoritmo no est informado, por lo cual su eficienciaes exponencial en n.

Las funciones:

- - -


orden-valores-dominio

pueden utilizarse para implementar heursticas que aceleren elproceso de bsqueda de una solucin.

Existen heursticas generales, que no dependen del conocimientoespecfico del dominio, que permiten resolver PSRs de maneraeficiente.

Bsqueda general no recursiva


58/183

Bsqueda general no recursiva

Tambin puede aplicarse el algoritmo general de bsqueda norecursivo visto en el tema anterior.

El algoritmo deber adaptarse a los criterios establecidos paralos PSRs, para ello:

,

almacenar los nodos a ser procesados.

Los operadores se aplicarn segn los criterios mencionados,es decir, no causarn conflictos entre las variables asignadas.


funcin busqueda general(PSR) retorna nodo o fallo


59/183

funcinbusqueda_general(PSR) retornanodo o fallo

inicio

inserta_lista_de_espera(lista, nodo) *El nodo inicial es la asignacin vacia*

bucle hacer

sivacia(lista) entonces retornafallo

sino

nodoelimina_elemento(lista);siprueba_meta(problema, nodo) es xitoentonces retornanodo

sino

_ _ _ , ,

*La funcin expandir devuelve una lista de nodos ordenados porprioridad, de acuerdo con la funcin heurstica aplicada*

*La funcin operadores slo permite generar nodos que no violen laconsistencia de las correspondientes asignaciones*

fin si

fin sifin bucle hacer

fin


Algunas cuestiones fundamentales relacionadas con laseleccin de una buena heurstica


60/183

seleccin de una buena heurstica.

1. Qu variable debe asignarse a continuacin y en quorden deben considerarse sus valores?

2. Cules son las implicaciones de las asignaciones de lasvariables actuales para las otras variables no asignadas?

. ,

el que una variable no tiene ningn valor legal, cmopuede procederse de manera efectiva en la vuelta atrs?

.


Las respuestas a las anteriores cuestiones han hecho


61/183

posible dotar a los algoritmos de tcnicas que permitenmejorar considerablemente su rendimiento.

a. Estas tcnicas son de propsito general.

b. Son totalmente independientes del problema.

c. Permiten a rovechar las caractersticas de la estructura

particular de los PSR. En la siguiente seccin se proporcionan respuestas a cada

una de estas preguntas.


5 Tcnicas para la mejora de la eficincia


62/183

5. Tcnicas para la mejora de la eficincia.

En esta seccin se presentan diferentes tcnicas heursticaspara:

A. La seleccin de variable y valor en cada paso del algoritmo.

. a propagac n e n ormac n a rav s e as res r cc ones,

con objeto de determinar los puntos de poda del algoritmocuanto antes. Se conoce como propagacin de restricciones.

C. La determinacin de los nodos que posiblemente sean los

causantes de la prdida de consistencia cuando esto ocurreen un nodo generado posteriormente. Se conoce comovuelta atrs inteligente.


A. Heursticas para la seleccin de variable yordenamiento de valor


63/183

ordenamiento de valor

Recurdese la sentencia de asignacin de variable delanterior algoritmo:

var Selecciona-variable-no-asignada(variables(PSR),asignacin, PSR)


La forma ms sencilla de seleccionar una variable a travsconsiste en escoger la siguiente variable no asignada en elorden arbitrario en que aparecen ordenadas en la listavariables(PSR).

{ }

AO d AO l

Heurstica de los mnimosvalores restantes MVR


64/183

Ejemplo. considrese elproblema de colorearcuadrculas y obsrvese elrbol de la figura.

Despus de las asignacionespara AO = rojoy TN = verde,hay un solo valor posible paraASAS = azul mientras quepara Qexisten dos posibles

AO = rojo AO = verde AO = azul

AO = rojoTN = verde

AO = rojoTN = azul

AO = rojoTN = verdeQ = rojo

AO = rojoTN = verdeQ = azul

valores restantes, MVR


va ores para as gnar = ro oy Q = azul.

Si se elige ASpara asignarleun valor, las opciones de Q,NGSy Vquedan restringidas.

Obsrvese que al estar ASms restringida que Q, parecems conveniente seleccionarprimero AS, pues Qtiene msopciones alternativas.

AO

TN

AS

Q

NGS

V

T

Idea intuitiva.


65/183

Escoger en cada paso de seleccin de variable aquella variablecuya asignacin de valor tiene ms probabilidades de fallar.Esto es, aquella que con mayor probabilidad causar pronto unfracaso por lo que a la asignacin de un valor se refiere.

As, se pretende que el fracaso se produzca cuanto antes (mejoren este momento que en un futuro), pues ello permite podar lasramas del rbol de bsqueda lo ms pronto posible.


De otra forma, habra tendencia a explorar (innecesariamente)

niveles ms inferiores del rbol para finalmente volver al nivelactual donde llevar a cabo la poda.

As pues, en cada paso se seleccionar la variable que contengaun mnimo nmero de valores consistentes para asignar en estepaso.

Esta tcnica se conoce como la heurstica de los mnimosvalores restantes, MVR.

Asignacin

Otra ventaja de la heursticaMVR


66/183

La mencionada heursticatambin favorece una menorramificacin en los niveles

inferiores del rbol, pues alseleccionar en cada paso lavariable con menos valoresrestantes, el nmero mximo

Asignacin

de A

Asignacin

de B

Asignacin

de C

9 nodos visitados

MVR


e no os para v s ar

posteriormente se reduce, alexpandirse menos el rbol debsqueda.

Por ejemplo, sea MVR(A)=1,MVR(B)=2, MVR(C)=3.

Las figuras ilustran los dosrboles.

Asignacin

de C

Asignacin

de B

Asignacin

de A

15 nodos visitados

Grado heurstico

En caso de empate entre varias variables la heurstica MVR no aporta


67/183

En caso de empate entre varias variables, la heurstica MVR no aporta

ningn mecanismo de seleccin de la variable ms adecuada. En este caso podra usarse la idea intuitiva de intentar reducir el factor

de ramificacin sobre futuras opciones, seleccionando, entre lasvariables no asignadas, aquella que se ve implicada en el mayor

nmero de restricciones. sta es una idea lgica, pues la asignacin de valores a variables con

muchas restricciones requerir posiblemente numeroros ensayos de


67

va ores, o que se ra uce en ram cac ones es e as menc ona as

variables (pues cuantas ms restricciones tiene una variable ms difcilresulta encontrar un valor coherente para la misma).

As, cuanto ms bajas ms cerca de las hojas estn situadas estasvariables en el rbol de bsqueda, ms forzadas estarn lasopciones de asignacin de valores a las mismas, lo que significa quems ensayos de valores ramificaciones debern llevarse a cabo.

En otras palabras, las posibilidades de que la asignacin ai bl bl d d i lt


68/183

una variable se vea bloqueada y as producir una altaramificacin y muy posiblemente una vuelta atrs, son tantomayores cuantas ms restricciones posea la variable.

Por tanto, se quiere evitar que las variables con muchasrestricciones se ramifiquen excesivamente, para lo cual resultaaceptable considerar que tales variables aparezcan en lugaresaltos del rbol cerca de la raiz.


68

Observando el grafo de restricciones del problema de colorearzonas se ve que la variable AS, con cinco restricciones, es laque mayor nmero de ellas tiene, las otras variables tienendos o tres restricciones, excepto Tque tiene cero.

Se conoce como grado heurstico GH


69/183

la heurstica basada en la anterior idea.


69

Como conclusin general, la heurstica de


70/183

mnimos valores restantes ha dadomejores resultados que el gradoheurstico, pero ste puede ser til para el

desempate.


70

Heurstica de seleccin del valor de una variable


71/183

Una vez seleccionada una variable, el algoritmo debeseleccionar un valor para la misma.

Una heurstica eficaz en algunos casos es la del valormenos restringido.

En este caso se elige para la variable actualmente


71

seleccionada el valor que menos afecta las opciones de

las variables vecinas todava no asignadas, esto es, elvalor que menos restringe las opciones de las variablesvecinas todava no asignadas.

Lo dicho se traduce en considerar el valor que elimine lamnima cantidad de valores de las variables por asignar.

TNQ T


72/183

Ejemplo. En el grafo de la figura, una vez realizadas las asignaciones

AO

AS

Q

NGS

V

T


72

, .

En este caso azules una mala opcin, porque elimina todas lasposibilidades de asignacin de AS, con lo que la heurstica del valormenos restringido asignara a Qel valor rojo.

En caso de que la variable seleccionada est sujeta a variasrestricciones con otras variables todava no seleccionadas, entonces

para obtener la capacidad restrictiva de un valor dado, puedeutilizarse la media aritmtica del mencionado valor con cada una de lasvariables.

B. Propagacin de la informacin a travs delas restricciones


73/183

as est cc o es En el algoritmo de bsqueda con vuelta atrs visto, las

restricciones sobre una variable slo se consideraban cuandola variable era elegida por Selecciona-variable-no-asignada.

Entonces, cualquier bloqueo del camino de bsqueda debido auna inconsistencia de valores causada por las restriccionesslo se detectaba en cuanto se roduca. Es decir, en el


73

momento en que se selecciona una variable y se comprueba

que no existe ningn valor consistente de la misma con lasvariables ya asignadas.

Es posible mejorar la eficiencia de la bsqueda si se prevn

futuras inconsistencias, lo que equivale a por aquellas ramas del rbol que se sabecausarn un bloqueo.

Cuestin: Cmo llevar a cabo esta poda por


74/183

Cuestin: Cmo llevar a cabo esta poda por

adelantado?

Solucin: Observando algunas restricciones antes deproceder a la seleccin de una nueva variable.

Esto supone la capacidad de propagar hacia delante


74

de prever futuras inconsistencias.

A continuacin se estudian algunos mtodos


75/183

g

que permiten observar por adelantado lasconsecuencias de las restricciones cuando seasignan valores a variables.


75

B.1 Comprobacin hacia delante (forward checking)


76/183

Siempre que se asigne un valor a una variable, X, elproceso de comprobacin hacia delante mira cadavariable no asignada, Y, que est relacionada con Xpor

alguna restriccin y suprime del dominio de Ycualquiervalor que sea inconsistente con el valor asignado a X.


76

La siguiente figura muestra el progreso de la bsqueda

para el ejemplo de coloracin de zonas.

AO

TNQ T


77/183

AO

AS NGS

V

AO TN Q NGS V AS T

Dominiosiniciales

R-V-A R-V-A R-V-A R-V-A R-V-A R-V-A R-V-A

Despus de

AO = rojoR V-A R-V-A R-V-A R-V-A V-A R-V-A


77

Obsrvese como despus de asignar AO = rojo, Q = verdey V = azul , el dominio deASes vaco, lo cual indica que la mencionada asignacin no conduce a ningunasolucin.En otras palabras, no es necesario que el proceso de bsqueda continue, pues en elmomento en que se seleccione la variable AS se dar cuenta de que existe unbloqueo y deber volver atrs.

Despus de

Q = verde

R A V R A R-V-A A R-V-A

Despus de

V = azulR A V R A R-V-A

Cuestiones tcnicas.


78/183

Cada nodo del rbol debe mantener informacin sobre elestado (variables asignadas) y la lista de valores posiblesen las variables por asignar.

El forward checking permite implementar muy fcilmente laheurstica MVR.

Tambin puede usarse de forma combinada con lasheursticas MVR i Grado heurstico.


78

Ejercicio. Combnese la comprobacin hacia delantecon las heursticas MVR y Grado heurstico en el


79/183

ejemplo del coloreado de zonas.


79

Taller 6


80/183

Considrese el problema de la asignacin de tareas aconductores (taller 4).Pngase un ejemplo con al menos 5 tareas y 2

conductores.a. Combnese el algoritmo de vuelta atrs con el forward

.

b. Combnese el algoritmo de vuelta atrs con la heursticaMVR y el forward checking para resolver el problema.

c. Combnese el algoritmo de vuelta atrs con las heursticasMVR y Grado heurstico y el forward checking pararesolver el problema.


80

Taller 6.bis


81/183

Considrese el problema de la asignacin de tareas aconductores (taller 4).

Desarrollar una implementacin del algoritmo primero en

profundidad para los PSR, que admita una entrada de datosy salida de resultados. Para este taller, no es necesario que

El programa debe desarrollarse en casa y ser probado porel profesor en el taller. Los resultados de la prueba servirnde guia para el buen desarrollo de la prctica por parte delos alumnos.

Los alumnos que hayan desarrollado una implementacinaceptable, recibiran una bonificacin de hasta 1 punto en lanota final de las actividades.


81

Taller 7


82/183

Considrese el problema de situar 4 reinas sin quehagan jaque entre ellas.

1. Combnese el algoritmo de vuelta atrs con el forwardchecking para resolver el problema. Se supone que lasreinas se consideran una a la vez, a partir de lasco umnas e zqu er a a erec a.

2. Combnese el algoritmo de vuelta atrs con la heursticaMVR y el forward checking para resolver el problema.

3. Combnese el algoritmo de vuelta atrs con lasheursticas MVR y Grado heurstico y el forward checkingpara resolver el problema.

Inteligencia Artificial.

Gabriel Fiol

82

Taller 8


83/183

Considrese el problema del taller 5.Pngase un ejemplo con al menos 5 tareas y 3empleados.

a. Combnese el algoritmo de vuelta atrs con el forwardchecking para resolver el problema.

b. Combnese el algoritmo de vuelta atrs con la heursticaMVR y el forward checking para resolver el problema.

c. Combnese el algoritmo de vuelta atrs con las

heursticas MVR y Grado heurstico y el forward checkingpara resolver el problema.


Gabriel Fiol

83

El forwardEl forward checkingchecking no descubre todas las inconsistenciasno descubre todas las inconsistencias


84/183

Si se observa por ejemplo la tercera fila de laanterior tabla, se ve que cuando AO = rojoyQ = verde, tanto TNcomo ASnicamentepueden ser azules, pero como sonadyacentes, no pueden por tanto tener elmismo valor.

La comprobacin hacia delante no descubreesta inconsistencia porque no mira lobastante lejos.

AO

TN

AS

Q

NGS

V

T


Gabriel Fiol

84

AO TN Q NGS V AS T

Dominios

inicialesR-V-A R-V-A R-V-A R-V-A R-V-A R-V-A R-V-A

Despus de

AO = rojoR V-A R-V-A R-V-A R-V-A V-A R-V-A

Despus de

Q = verdeR A V R A R-V-A A R-V-A

Despus de

V = azulR A V R A R-V-A

B.2 Consistencia de arco (CA)


85/183

El forward checking no descubre todas las inconsistencias. Hace falta propagar las implicaciones de una restriccin sobre una

variable en todas las otras variables, y no solamente en las queestn relacionadas directamente con ella a travs de alguna

restriccin, lo que se conoce como propagacin derestricciones.

restricciones desde AOy Qa TNy AStal como se hizo en lacomprobacin hacia delante y luego se precisa la propagacin ala restriccin entre TNy ASpara descubrir la inconsistencia.

Existen tcnicas ms completas para propagar restricciones.

La propagacin debe ser rpida i no alterar el requisito decompletitud de la solucin.


Gabriel Fiol

85

El concepto de consistencia de arco proporcionaun mtodo rpido de propagacin de restricciones


86/183

que es ms potente que la comprobacin haciadelante.


Gabriel Fiol

86

Definicin formal de la consistencia de arco

di i id


87/183

Un arco se refiere a un arco dirigidoy por tantounidireccional en el grafo de restricciones, como el arcodesde ASa NGS.

Definicin (arco consistente). Un arco (A,B): ABesconsistente si, para todo valor, x, de la variable A, existe un

, , , .

La anterior definicin garantiza que, para cualquierasignacin a la variable A, existe una asignacin consistentepara la variable B.


Gabriel Fiol

87

Consistencia de arco en un PSR


88/183

La aplicacin de la consistencia de arco a un PSR con nvariables se establece del siguiente modo:

Un PSR mantiene la consistencia de arco PSR arcoconsistente- si todo arco XYes un arco consistente.

mantenga la consistencia de arco.

En caso de que un PSR no mantenga la consistencia dearco, sta puede intentar restablecerse. Si ello no esposible, entonces no existe solucin para el PSR.


Gabriel Fiol

88

AO

TN

AS

Q

NGS

TEJEMPLO


89/183

AO TN Q NGS V AS T

Dominiosiniciales


Despus deAO = rojo

R V-A R-V-A R-V-A R-V-A V-A R-V-A

Despus de= verde


V


Gabriel Fiol

89

En la fila 3 de la figura se observa que los dominios de ASy NGSson {azul} y {azul,rojo}, respectivamente.

Para AS = azul, hay una asignacin consistente para NGS, que es NGS = rojo; por

tanto, el arco desde ASa NGSes consistente. No obstante, el arco inverso desde NGSa ASno es consistente, pues para la

asignacin NGS = azulno existe ninguna asignacin para ASconsistente con la misma. Dicho arco puede hacerse consistente suprimiento el valor azuldel dominio de NGS.

Despus de

V = azul

R A V R A R-V-A

AO

TN

AS

Q

NGS

V

T


90/183

AO TN Q NGS V AS T

Dominiosiniciales


Despus de

AO = rojo

R V-A R-V-A R-V-A R-V-A V-A R-V-A

Despus deQ = verde


Despus de A R R-V-A

V


Gabriel Fiol

90

Continuando con el ejemplo de la situacin descrita en la tercera fila de la anteriortabla, si se aplica el mtodo del arco consistente al arco desde ASa TN, seobserva que los dominios de ambas variables son idnticos, coincidiendo amboscon el conjunto {azul}.

En tal caso el valor azuldebe suprimirse del dominio de AS, lo cual lo deja vaco. De esta forma el mtodo del arco consistente detecta una inconsistencia que no

hubiera sido detectada por el mtodo de comprobacin hacia delante.

V = azul

Idea intuitiva para mantener la consistencia de arcode un PSR


91/183

Objetivo:

Actualizar los dominios de todas las variables de manera que todoslos arcos sean consistentes.

Si un arco es inconsistente, intentar hacerlo consistente eliminandodel dominio de la variable inicial del arco aquellos valores para losque no existen valores en el dominio de la variable final del arcoque satisfagan la condicin de consistencia.

Si despus de aplicar la consistencia de arco el dominio de lavariable inicial queda vacio, entonces no existe solucin para elPSR.


Gabriel Fiol

91

Cmo se aplica la consistencia de arco?

R i i d l


92/183

Revisin de los arcos: Siempre que se suprime un valor del dominio de una

variable con objeto de eliminar una inconsistencia de unarco, una nueva inconsistencia de arco podra surgir enarcos que apuntan a dicha variable.

Todos los arcos son consistentes, o Algn dominio queda vacio, lo que significa que existe alguna

inconsistencia entre los valores de las variables asignadas.Si en la etapa de preproceso algn dominio queda vacio,

entonces el PSR no tiene solucin.


Gabriel Fiol

92

Ejemplo. Planificacin de las acciones de un robot

Un robot necesita planificar cinco actividades (A B C D y E) donde


93/183

Un robot necesita planificar cinco actividades (A, B, C, D y E), dondecada actividad ha de comenzar en un momento en el tiempo (1, 2, 3, o 4)y dura exactamente una nidad de tiempo. Restricciones:

La actividad B no puede realizarse en el momento nmero 3.

La actividad C no puede realizarse en el momento nmero 2.

Las actividades A B no ueden realizarse simultneamente.

Las actividades B y C no pueden realizarse simultneamente.

La actividad C ha de realizarse antes de la D.

Las actividades B y D no pueden realizarse simultneamente.

Las actividades A y D han de realizarse simultneamente. La actividad E ha de ser la primera de todas.


Gabriel Fiol

93

Paso 1. Definicin formal del problema entrminos de un PSR


94/183

Variables: {A, B, C, D, E} Dominios: Di = {1, 2, 3, 4}, para toda variable. Restricciones:

B 3. C 2. . B C.

C < D. B D. A = D. E = 1.

E < A. E < B. E < C. E < D. Inteligencia Artificial.

Gabriel Fiol

94

Grafo binario de restricciones


95/183


Gabriel Fiol

95

Paso 2. Aplicacin de la consistencia de arco

DOMINIOS RESTRICCIONES ARCOS

A REVISAR

DOMINIOSRESULTANTES


96/183

A REVISARA(1,2,3,4) B(1,2, 4) C(1,3,4) D(1,2,3,4) E(1) A B (A,B) -----------------

A(2,3,4) C(1,3) D(2,3,4) (B,A) ------------------

B C (B,C) ------------------

(C,B) ------------------

C < D (C,D) C(1,3)

, , ,

(C,D) ------------------

B C (B,C) ------------------

(C,B) ------------------

B D (B,D) ------------------

(D,B) ------------------

A = D (A,D) A(2,3,4)

(D,A) ------------------


Gabriel Fiol

96

DOMINIOS RESTRICCIONES ARCOSA REVISAR

DOMINIOSRESULTANTES

A(2,3,4) B(1,2, 4) C(1,3) D(2,3,4) E(1) E < A (E,A) -----------------

A(4) B(2,4) C(3) D(4) (A,E) -----------------

B(2) E B (E B)


97/183

B(2) E < B (E,B) -----------------

(B,E) B(2,4)

E < C (E,C) -----------------

(C,E) C(3)

B C (B,C) ------------------

(C,B) ------------------

C < D (C,D) ------------------


Gabriel Fiol

97

(D,C) D(4)

E < D (E,D) -----------------(D,E) -----------------

B D (B,D) B(2)

(D,B) -----------------

A = D (A,D) A(4)

(D,A) ------------------

A(4) B(2) C(3) D(4) E(1) No hay msrestricciones

Aunque en el anterior ejemplo se ha encontradouna solucin al problema mediante la aplicacin de

la consistencia de arco la funcin de sta es slo


98/183

la consistencia de arco, la funcin de sta es slomantener el PSR consistente.


Gabriel Fiol

98

Algoritmo para mantener la consistencia de arco, AC3

El algoritmo para mantener la consistencia de arco AC


99/183

El algoritmo para mantener la consistencia de arco, AC-3, utiliza una cola para guardar los arcos que tienen quecomprobarse.

Cada arco (Xi, Xj) se quita sucesivamente de la cola y


Gabriel Fiol

99

dominio de Xirequiere ser suprimido, entonces cadaarco (Xk, Xi) apuntando a Xidebe ser reinsertado en lacola para la comprobacin de su consistencia.

funcin AC-3(psr) devuelve un PSR posiblemente con dominio reducido;entradas:psres un PSR binario con n variables, {X1, X2,, Xn};variables locales: cola, una cola de arcos, inicialmente todos los arcos delpsr;Inicio

mientrascola no sea vacia hacer

(Xi, Xj)DESENCOLA(cola);si BORRAR-VALORES-INCONSISTENTES(Xi Xj) entonces


100/183

funcinBORRAR-VALORES-INCONSISTENTESX X devuelve verdadero si slo si se ha

siBORRAR VALORES INCONSISTENTES(Xi, Xj) entoncesinicio

para cadaXken VECINOS(Xi) hacerAADIR(Xk, Xi) a la cola

fin para

fin sifin mientras

fin;


Gabriel Fiol

100

borrado algn valor;

inicio

borrado falso;para cadax en DOMINIO(Xi) hacer

si no hay uny en DOMINIO(Xj) que permita a (x,y) satisfacer la restriccin entreXi

yXjentonces

inicio

borrarx de DOMINIO(Xi);

borrado

verdaderofin si

fin para

devolverborrado

fin;

Complejidad de la consistencia de arco

Un PSR binario tiene a lo sumo (n2) arcos para un conjunto denvariables, cada variable contiene a lo sumo n-1 arcos haciacada na de las dems ariables se tienen por tanto n (n 1)


101/183

variables, cada variable contiene a lo sumo arcos haciacada una de las dems variables; se tienen por tanto, n(n-1)arcos.

Cada arco (Xk, Xi) se insertar en la cola dveces a lo sumo,pues Xi tiene como mximo dvalores para suprimir.

La comprobacin de la consistencia de un arco (Xk, Xi) puede


Gabriel Fiol

101

hacerse en (d ) pasos, pues al tener cada variable dvalores

como mximo, entonces cada valor del dominio de Xksecompara con cada uno de los dvalores del dominio de Xiconobjeto de determinar la consistencia del valor de Xk.

Por tanto, el tiempo total, en el peor de los casos, es (n2d3).

Este coste es mayor que el de la comprobacin hacia delante, noobstante la diferencia, por lo general, vale la pena.

Slo con AC-3 no es posible resolver un PSR.

Cundo se aplica la consistencia de arco?


102/183

Slo con AC 3 no es posible resolver un PSR. AC-3 puede combinarse con la bsqueda primero en profundidad,

de la siguiente manera:

1. como un paso de preproceso antes de comenzar el proceso debsqueda, y

2. como un paso de propagacincomo la comprobacin hacia


Gabriel Fiol

102

delante despus de cada asignacin durante la bsqueda.

Este ltimo caso se conoce como MCA, mantenimiento de laconsistencia del arco.

En ambos casos el proceso debe aplicarse repetidamente hasta

que no permanezcan inconsistencias.

Si se detecta que algn dominio queda vacio, entonces nohay solucin con las asignaciones actuales.

Si se detecta q e todos los dominios tienen n nico alor


103/183

Si se detecta que todos los dominios tienen un nico valor,antonces se ha alcanzado una solucin. El proceso debsqueda termina.

En otro caso, la bsqueda prosigue, seleccionando unanueva variable para asignarle un valor.


Gabriel Fiol

103

La CA no revela todas las inconsistencias

La consistencia de arco no revela todas las inconsistencias


104/183

La consistencia de arco no revela todas las inconsistenciasposibles.

Por ejemplo, en el problema de coloreado de zonas, la

asignacin parcial {AO = rojo, NGS = rojo} es inconsistente,pero AC-3 no la encuentra.


Gabriel Fiol

104

AO

TN

AS

Q

NGS

V

T

La CA detecta las inconsistencias entre arcos (Xi, Xj); pero la propiedadde arco consistente no necesariamente se propaga a ternas (Xi, Xj, Xk) oeplas con un mayor nmero variables.


105/183

AO

TN

AS

Q

NGS

V

T

Tenemos: AO(R), TN(V,A), AS(V,A), Q(V,A), NGS(R), V(V,A), T(R,V,A).

Aunque todos los arcos sean consistentes, la consistencia no se propagaa la epla (AO, TN, AS, Q, NGS).

Motivo: Al asignar posteriormente un valor a una variable no asignada,

entonces su dominio se restringe a este valor, con lo que puede dejar desatisfacerse la CA.


Gabriel Fiol

105

PSR Fuertemente n-consistente

El concepto de kconsistencia permite definir las formas ms potentesde la propagacin de consistencias.


106/183

PSR kconsistente: si, para cualquier conjunto de k-1 variables y paracualquier asignacin consistente a esas variables, siempre se puedeasignar un valor consistente a cualquier k-sima variable.

Por ejemplo, la 1consistencia significa que cada variable individual,por s misma, es consistente, lo que se conoce como consistencia denodo.

La 2consistencia significa que, para cualquier conjunto de una variable

y para cualquier asignacin consistente a la variable del conjunto,siempre se puede asignar un valor consistente a cualquier otra segunda variable. Por tanto, la 2consistencia es lo mismo que laconsistencia de arco.

La 3consistencia significa que cualquier par de variables adyacentespueden siempre extenderse a una tercera variable, lo que se conocetambin como consistencia de camino.


Gabriel Fiol

106

Grafo fuertemente kconsistente: si es kconsistente y tambin(k-1)consistente, (k-2)consistente,, 1consistente.

PSR fuertemente n consistente: Supngase que se tiene un


107/183

PSR fuertemente nconsistente: Supngase que se tiene unPSR con nnodos variables de manera que es fuertemente nconsistente esto es, fuertemente kconsistente, para k = n. Elproblema puede resolverse sin vuelta atrs.

Primero se elige un valor consistente para X1. Entonces se tienearantizado oder ele ir un valor ara X or ue el rafo es 2


Gabriel Fiol

107

consistente, tambin para X3, porque es 3consistente,

El tiempo para encontrar una solucin es (nd).

El mayor obstculo radica en el establecimientode la n-consistencia fuerte.

E l d l l i l it


108/183

En el peor de los casos, cualquier algoritmo queestablezca la n-consistencia fuerte tendr una

eficiencia exponencial en n.


Gabriel Fiol

108

C. Manejo de restricciones especiales

Ciertas restricciones frecuentes en problemas realespueden manejarse mediante algoritmos de propsitoespecial de manera ms eficiente que los mtodos de


109/183

especial de manera ms eficiente que los mtodos depropsito general descritos hasta ahora.

Ejemplo 1: considrese la restriccin todasdifque imponeque el valor de todas las variables implicadas debe serdiferente, como en el problema criptoaritmtico.


Gabriel Fiol

109

Una forma sencilla de deteccin de inconsistencias para lamencionada restriccin es como sigue:

si hay mvariables implicadas en la restriccin, y si entretodas tienen nposibles valores distintos, y si m > n,

entonces la restriccin no puede satisfacerse.

Algoritmo para detectar si se ha producido unainconsistencia:

Quitar cualquier variable en la restriccin que tenga un


110/183

dominio con una sola posibilidad y suprmase el valor de esavariable de los dominios de las variables restantes.

Reptase el proceso mientras existan variables con una solaposibilidad.

Si en algn momento se produce un dominio vacio o hay ms

variables que valores en sus dominios, entonces se hadescubierto una inconsistencia.


Gabriel Fiol

110

Ejemplo

TNQ T

R1 R2 R3 R4


111/183

R1, R2, R3, R4 re resentan restricciones todasdif

AO

AS NGS

VAO=R V=

{V,A}

TN=

{V,A}

AS=

{V,A}

Q=

{V,A}

NGS=R

Aplicando el anterior algoritmo para detectar las inconsistencia en lasiguiente asignacin parcial {AO = rojo, NGS = rojo}, observamos que lasvariables AS, TN y Q estn relacionadas por una restriccin todasdif,cuyo dominio es {verde, azul}.

Al haber tres variables y solamente dos valores se detecta la existenciade inconsistencias en la asignacin parcial a travs de R2..


Gabriel Fiol

111

La consistencia de arco no detecta las inconsistencias delanterior ejemplo para la asignacin parcial considerada.

Por tanto, un procedimiento simple de consistencia para una


112/183

, p p prestriccin de alto orden es a veces ms eficaz que laaplicacin de la consistencia de arco a un conjunto

equivalente de restricciones binarias.

,preciso que prviamente el problema se formule en trminosde un PSR adecuado al caso.


Gabriel Fiol

112

Ejemplo 2.

Considrese la restriccin de alto orden llamada restriccin de

recursos o restriccin como_mximo.


113/183

Por ejemplo, PA1, ..., PA4 denotan la cantidad de personasasignadas a cada una de las cuatro tareas.

La restriccin que no asigna ms de 10 personas en total seescribe: como_mximo(10, PA1, PA2, PA3, PA4).

As, se puede descubrir una inconsistencia simplementecomprobando la suma de los valores mnimos de los dominiosactuales (el dominio de una variable se refiere a la cantidad depersonas que esta variable puede contener).

Por ejemplo, si cada variable tiene el dominio {3, 4, 5, 6}, larestriccin como_mximono puede satisfacerse, pues el nmerode personas asignadas seria 3x4=12.


Gabriel Fiol

113

Tambin puede hacerse cumplir la consistencia suprimiendoel valor mximo de cualquier dominio si no es consistente

con los valores mnimos de los otros dominios.A i d i bl i l d i i {2 3 4 5 6} l


114/183

As, si cada variable tiene el dominio {2, 3, 4, 5, 6}, losvalores 5 y 6 pueden suprimirse de cada dominio.


Gabriel Fiol

114

Ejemplo 3.

Para problemas grandes cuyos recursos vienen delimitadoscon valores enteros (por ej. problemas de logstica queimplican el movimiento de miles de personas en cientos de


115/183

implican el movimiento de miles de personas en cientos devehculos) no es, en general, posible representar el dominio

de cada variable como un conjunto grande de enteros ygradualmente reducir este conjunto por los mtodos decom robacin de consistencias.

En estos casos, los dominios se representan por lmitessuperiores e inferiores y son manejados por la propagacinde lmites.


Gabriel Fiol

115

Supngase que hay dos vuelos, el A y el B, para los cuales losaviones tienen capacidades de 165 y 385 pasajeros

respectivamente. Los dominios iniciales para el nmero depasajeros en cada vuelo son:


116/183

p j

VueloA [0, 165]y VueloB [0, 385]

Supngase que se tiene la restriccin adicional que los vuelos

VueloA + VueloB [420, 420]


Gabriel Fiol

116

VueloA [0, 165]; VueloB [0, 385]

VueloA + VueloB [420, 420]

Propagando los lmites de las restricciones los dominios sed


117/183

reducen a:

VueloA

[35, 165]y VueloB

[255, 385]

Se dice que un PSR es consistente-acotado si para todo valor deuna variable X (incluyendo las cotas inferior y superior), existe un

valor de Y que satisface la restriccin entre X e Y, para cadavariable Y.

La propagacin de lmites se utiliza mpliamente en problemas

restringidos prcticos.


Gabriel Fiol

117

D. Vuelta atrs inteligente: mirando hacia atrs

El algoritmo Bsqueda-Con-Vuelta-Atrs que se ha descritoimplementa una poltica de vuelta atrs cronolgica que le


118/183

implementa una poltica de vuelta atrs cronolgica que leindica lo que debe hacer cuando falla una rama: vuelve a la

variable anterior e intenta un valor diferente para ella. No obstante, puede haber numerosos caminos de vuelta


Gabriel Fiol

118

u u .

Observaciones.

El salto atrs ocurre cuando cada valor del dominio de un nodo

(nodo bloqueado) est en conflicto con la asignacin actual. Pero la comprobacin hacia delante (FC) y la consistencia de


119/183

Pero la comprobacin hacia delante (FC) y la consistencia dearco descubren muchos bloqueos con antelacin y previenen a la

bsqueda de alcanzar alguna vez el nodo bloqueado. As pues, el salto atrs parece ser redundante con una bsqueda

(PIR).

No obstante, los mtodos de PIR, como el forward checking o elAC-3, no previenen la bsqueda de todos los conflictos, con locual se hace imprescindible el uso de bactracking.

Por tanto, cuanto ms inteligente sea la tcnica de bactracking,ms eficiente ser el algoritmo de bsqueda.


Gabriel Fiol

119

Ejemplo del coloreado de zonas convuelta atrs cronolgica AO

TN

AS

Q

NGS

V

T


120/183

Obsrvese lo que ocurre cuando se considera el siguiente orden

de seleccin de las variables:Q, NGS, V, T, AS, AO, TN

Supngase que se ha generado la asignacin parcial { rojo,NGS =verde, V =azul, T =rojo}.

Al probar con la siguiente variable, AS, se observa que cada valorviola una restriccin.

Entonces se vuelve atrs a la variable Ty se prueba con un nuevo

color para la misma. Naturalmente, este trabajo es intil, pues Test aislada de cualquier otra variable y no puede ni tan siquieraparticipar en la causa del fracaso.


Gabriel Fiol

120

U i i i t li t l lt t i t

AO

TN

AS

Q

NGS

V

T


121/183

Una aproximacin ms inteligente a la vuelta atrs consisteen ir hacia atrs hasta el conjunto de variables que causaron

el fracaso. Esto es, retroceder basndose en los motivos delfracaso.


Gabriel Fiol

121

A este conjunto se le llama conjunto conflicto.

En el ejemplo el conjunto conflicto de ASes {Q, NGS, V}.

De manera general, el conjunto conflicto de una variable Xes el conjunto de variables previamente asignadas queestn relacionadas con Xa travs de las restricciones.

Ahora, la vuelta atrs debera retroceder hasta elconjunto conflicto de la variable en curso para la

cual no existe ninguna asignacin posible.


122/183


Gabriel Fiol

122

Ejemplo.

Considrese la asignacin parcial {AO=rojo, NGS=rojo, T=rojo} (sabemos

AO

TN

AS

Q

NGS

V

T


123/183

g p { j j j } (que es inconsistente).

Considrese la asignacin de valores en el siguiente orden de lasvariables: TN, Q, V, AS.

por lo que una vez TN haya agotado todos sus valores, surge la pregunta:

dnde debe regresar el algoritmo? La causa del fracaso no se encuentra solamente en el conjunto conflicto

de TN, sino en aquellas variables que no permiten ninguna asignacinconsistente de TN, Q, V y AS juntas.

As, una vez no se encuentre ningn valor alternativo para TN, deberretrocederse al conjunto conflicto que cause el fallo de las cuatrovariables juntas.


Gabriel Fiol

123

A partir de los anteriores ejemplos ya estamos encondiciones de ver cmo calculamos el conjunto

conflicto de una variable. Esta idea puede implantarse fcilmente modificando el


124/183

Esta idea puede implantarse fcilmente modificando elalgoritmo Bsqueda-Con-Vuelta-Atrs, de manera

que acumule el conjunto conflicto de cada variable.


Gabriel Fiol

124

Cmo calcular el conjunto conflicto de unavariable?

La comprobacin hacia delante puede suministrar el conjunto conflicto

sin trabajo suplementario, de la siguiente forma: Siempre que la comprobacin hacia delante, basada en una asignacin

a X suprima un valor del dominio de Y se debera aadir X al conjunto


125/183

a X, suprima un valor del dominio de Y, se debera aadir Xal conjuntoconflicto de Yel conjunto conflicto generado as se llama conjuntoconflicto directo

Adems, siempre que se suprima el ltimo valor del dominio actual de Ya causa de la asignacin a X, como se ha mencionado, las variables


Gabriel Fiol

125

.

En resumen, en la vuelta atrs inteligente, cuando una variable, Y, quedasin valores en su dominio, se vuelve atrs a la variable del conjuntoconflicto de Yms recientemente asignada.

Al algoritmo de salto atrs que hace uso de los conjuntos conflictodefinidos de esta forma se le llama salto atrs dirigido por conflicto.

En general, sea Xj la variable actual y seaconflicto(Xj) su conjunto conflicto. Si para todo valorposible de Xjse produce fallo, entonces se saltaatrs a la variable ms reciente Xi tal que


126/183

atrs a la variable ms reciente, Xi, tal queXi conflicto(Xj), actualizndose el conjunto

conflicto de Xi, de la siguiente manera:


Gabriel Fiol

126

conflicto(Xi) conflicto(Xi) conflicto(Xj) {Xi}

Ejemplo

Considrese la asignacin parcial {AO=rojo, NGS=rojo, T=rojo}.

Considrese en el siguiente orden la asignacin a TN Q AS en la cual

AO

TN

AS

Q

NGS

V

T


127/183

Considrese en el siguiente orden la asignacin a TN, Q, AS, en la cualla variable ASfalla en un instante dado, siendo {AO, NGS,TN, Q} suconjunto conflicto.

Se salta entonces atrs a Q, cuya asignacin es la ms reciente de lasque aparecen en el conjunto conflicto, y Qabsorbe el conjunto conflicto


Gabriel Fiol

127

, ,que es {TN, NGS}.

El nuevo conjunto conflicto de Qes {AO, TN, NGS}. Pero ya se han probado todos los valores sobre Q, lo que significa que

no hay ninguna asignacin consistente de Q hacia delante a partir de laasignacin precedente.

Por tanto, se vuelve hacia atrs a TN, cuya asignacin es la msreciente. TN absorbe {AO, TN, NGS} - {TN} en su conjunto conflictodirecto, que es {AO}, dando {AO, NGS}.

Si para TNya se han probado todos los posibles valores,

AO

TN

AS

Q

NGS

V

T


128/183

entonces se vuelve atrs, en este caso a NGS; sino, se

asigna a TNun valor todava no asignado.


Gabriel Fiol

128

Detalles a tener en cuenta:

1. En la vuelta atrs, hay que actualizar los conjuntos conflictode las variables abandonadas bloqueadas- en la bsqueda.

2 Cuando la vuelta atrs alcanza una variable X para la que


129/183

2. Cuando la vuelta atrs alcanza una variable, X, para la queexiste algn valor alternativo para probar y as continuar la

bsqueda hacia delante, hay que mantener el conjuntoconflicto no directo de esta variable (esto es, el conjunto


Gabriel Fiol

129

con cto e aque as var a es que an resu ta o oquea ascausando la vuelta atrs a X), puesto que si en un futuro sevuelve atrs a la variable X, resultando sta bloqueada, hayque dar oportunidad a las variables previamente bloqueadasque causaron el retorno a X.

Para llevar a cabo la implementacin de la vuelta atrsinteligente, puede usarse la comprobacin hacia

delante, aadiendo ahora a cada fila de la matriz, unanueva columna en la que se almacenar el conjuntoconflicto de la correspondiente variable


130/183

conflicto de la correspondiente variable.

Cuando se vuelve atrs hay que actualizaradecuadamente el conjunto conflicto de las variables


Gabriel Fiol

130

afectadas (detalle 1). Si se usa la comprobacin hacia

delante, entonces dicha actualizacin es automtica.

6. Bsqueda local para problemasde satisfaccin de restricciones

Los algoritmos de bsqueda local resultan muy eficacesen la resolucin de muchos PSRs.


131/183

Utilizan por lo general una formulacin de estados

completa: en el estado inicial cada variable tiene unvalor asignado.


131

La funcin sucesor elige una variable y cambia el valor

que tiene asignado. Para ello puede hacer uso de ciertaaleatoriedad y alguna heurstica.

Los estados finales son soluciones al PSR.

En realidad, se trata de mtodos de mejora iterativa.

Ejemplo.

En el problema de las 8 reinas, el estado inicial podraser una configuracin arbitraria de ocho reinas en ochocolumnas, y la funcin sucesor se encargara de


132/183

escoger una reina en cada paso y moverla a otro cuadro

de su columna.


132

Heurstica de los mnimos conflictos

Variable seleccionada para cambiar su valor:

Aquella (diferente de la ltima variable modificada) que participa enms restricciones NO satisfechas en el estado (los empates se

S


133/183

deciden aleatoriamente). Se trata de la variable cuyo valor asignadoen el estado actual posee un mayor nmero de conflictos.

Seleccionada aleatoriamente (diferente a la ltima) de entre las queosean conflictos.

Nuevo valor elegido:

El valor (diferente del que tenia) que produce el menor nmero deconflictos (restricciones incumplidas). Los empates de decidenaleatoriamente.

En numerosos problemas se ha comprobado que el xito delmtodo reside especialmente en el estado inicial seleccionadoms que en la seleccin de la variable.


133

Implementacindel mtodo(seleccin aleatoria de variable)

Estructura de los nodos: los nodos estan compuestos de laasignacin actual y la ltima variable modificada.


134/183

Funcin MNIMOS-CONFLICTOS(psr,max_pasos) devuelve una solucin o

fallovariables: psr, un problema de satisfaccin de restricciones;

max_pasos, nmero de pasos permitidos antes de abandonar;


134

actual una asignacin completa inicial parapsr;para i = 1 hasta max_pasoshacer

siactual es una solucin parapsrentoncesdevolver actualsino

var escoger aleatoriamente una variable conflictiva deVARIABLES(psr)

valor el valor, v, para varque minimiza CONFLICTOS(var,v,actual,psr)ACTUALIZAR(actual) (*actual se actualiza con la nueva asignacin*)

fin sifin para

fin;

El estado inicial puede elegirse al azar o por un proceso voraz deasignacin de valores que elige un valor de mnimo conflicto para

cada variable.

La funcin CONFLICTOS cuenta el nmero de restricciones violadas


135/183

por un valor particular, considerando el resto de la asignacin actual.


135

Implementacindel mtodo(seleccin de variable con ms restricciones No satisfechas)

FUNCION MIN-CONFLICTOS(MAX-PASOS)1. Hacer ACTUAL igual a un nodo con una asignacin generada aleatoriamente.


136/183

2. Para I desde 1 hasta MAX-PASOS hacer

2.1 Si la asignacin de ACTUAL es una solucin, devolverla y terminar.2.2 Hacer VARIABLE igual a una variable (distinta de la ltima modificada)

nmero de restricciones incumplidas.

2.3 Hacer SUCESORES igual a la lista de nodos obtenidos cambiando en laasignacin ACTUAL el valor de VARIABLE por cada uno de los posiblesvalores del dominio de VARIABLE en *VARIABLES* (excepto elcorrespondiente al valor que tena en ACTUAL)

2.4 Hacer ACTUAL el nodo de SUCESORES escogido aleatoriamente de entreaquellos cuya asignacin incumple el menor nmero de restricciones

3. Devolver FALLO


136

Propiedades del algoritmo de bsqueda local

No es completo

Complejidad en tiempo: lineal en el nmero de iteraciones


137/183

p j p

Posible Aleatoriedad: En la asignacin del estado inicial, devariable y al deshacer empates.

La bsqueda local tiene muy buenos resultados en algunos

tipos de PSRs: PSRs cuyas soluciones estn distribuidas uniformemente

a lo largo del espacio de estados

PSRs en los que las restricciones pueden cambiardinmicamente


137

Los mnimos conflictos son sorprendentemente eficacespara muchos PSRs, en particular, cuando se parte de un

estado inicial razonable. La siguiente figura ilustra una solucin de dos pasos al

problema de las 8 reinas usando mnimos conflictos para


138/183

problema de las 8 reinas usando mnimos conflictos para

una posicin inicial dada y una seleccin aleatoria de lavariable.


138

1

3

2

2

2

1

2

3

2

3

3

1


139/183

1

2

1

3

2

0

situacin inicial


139

El nmero de conflictos en cada cuadro de la columnaconsiderada esto es, el nmero de reinas que atacandicho cuadro viene anotado en cada uno de los cuadros.

El algoritmo mueve la reina al cuadro de mnimo conflicto,deshaciendo los empates de manera aleatoria

De manera extraordinaria, para el problema de las n-reinas, si nose tiene en cuenta la colocacin inicial de las reinas, el tiempo deejecucin del anterior algoritmo es ms o menos independiente

del tamao del problema. Resuelve el problema de un milln dereinas en un promedio de 50 pasos despus de la asignacininicial.

Estos sorprendentes resultados fueron el estmulo que condujo a


140/183

Estos sorprendentes resultados fueron el estmulo que condujo agran parte de la investigacin en los aos 90 sobre la bsquedalocal y sobre la diferencia entre problemas fciles y difciles.

En trminos a roximados se dice ue las n-reinas es un


140

problema fcil para la bsqueda local porque las soluciones estndensamente distribuidas en todas las partes del espacio de

estados. El algoritmo de los mnimos conflictos tambin se ha utilizado para

programar las observaciones del telescopio Hubble, reduciendo eltiempo utilizado para programar una semana de observaciones,

de tres semanas a alrededor de unos 10 minutos.

Otra ventaja de la bsqueda local radica en que puede usarse enun ajuste onlinecuando el problema cambia.

Esto resulta importante en la programacin de problemas. Porejemplo, el programa de vuelos de una semana en unaeropuerto puede implicar miles de vuelos y decenas de milesde asignaciones de personal, pero el mal tiempo puede convertirla programacin en no factible Se desea pues reparar la


141/183

la programacin en no factible. Se desea pues reparar laprogramacin ya hecha con un mnimo nmero de cambios en lamisma.


141

bsqueda local comenzando desde la programacin actual lacual constituye el estado inicial del algoritmo, que seramodificada con las oportunas asignaciones.

Usar un algoritmo con vuelta atrs partiendo con un nuevoconjunto de restricciones las debidas al mal tiempo, requiere,por lo general, mucho ms tiempo y podra encontrar unasolucin, a partir de la programacin actual como estado inicial,con muchos cambios.

7. La estructura de los problemas

En esta seccin se observan las formas por lascuales la estructura del problema representada por


142/183

cuales la estructura del problema, representada por

el grafo de restricciones, puede utilizarse paraencontrar soluciones de forma rpida.

Ejemplo: observando el grafo de estadoscorrespondiente al coloreado de zonas, se observaun hecho:


142

AO

TN

AS

AO

NGS

SG

Q


143/183

AS

V

T

La zona Tno est relacionada con ninguna otra zona del sub-grafoSG. Por tanto, es bvio que colorear la zona Ty colorear elsubgrafo, SG, son subproblemas independientescualquier

solucin para el sub-grafo SG combinada con cualquier solucinpara la zona, T, produce una solucin para el problema.


143

Descomposicin del problema en subproblemasindependientes

Dos subproblemas son independientes, si lascaractersticas de la solucin de uno no afecta al otro.


144/183

La independencia puede averiguarse buscandocomponentes conectados del grafo de restricciones.

En trminos del grafo de restricciones, no existe arista

que una dos subproblemas independientes.

Cada componente corresponde a un subproblema PSRi.

Si la asignacin, Si, es una solucin de PSRi, entoncesiSies una solucin de iPSRi.


144

Considrese que cada PSRitiene cvariables del total de nvariables, siendo cuna constante.

Entonces hay n/csubproblemas, cada uno de los cuales tieneun coste mximo asociado de dcrecurdese que des elnmero de valores de cada variable para resolverlo.


145/183

As, el trabajo total es

(d

c

n/c), que es lineal en n. Sin la descomposicin, el trabajo total es (dn), que esexponenc a en n.

Por tanto, cuanto menor es el nmero de variables, c, de lossubproblemas cunto ms pequeos son los subproblemas-,menor es el factor dcy ms eficiente es la resolucin delproblema entero.

De ah la importancia de reducir un problema en subproblemasindependientes siempre que se pueda.


145

Descomposicin del problema en un grafo rbol

No obstante, los subproblemas completame

Documents

Apunts PSR V3