Download - Apunts PSR V3
-
7/28/2019 Apunts PSR V3
1/183
Problemas de satisfaccin derestricciones
Constraint Satisfaction Problems
Inteligencia Artificial.Gabriel Fiol
1
-
7/28/2019 Apunts PSR V3
2/183
Objetivos del tema Estudiar diferentes alternativas en cuanto a
modelos y tcnicas usadas para resolverproblemas de satisfaccin de restricciones
las tcnicas presentadas.
Inteligencia Artificial.Gabriel Fiol
2
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
4
-
7/28/2019 Apunts PSR V3
5/183
Bibliografa bsica
Apuntes del profesor.
Inteligencia Artificial. Un Enfoque Moderno (2a Ed.)S. Russell, P. Norvig
Inteligencia Artificial.Gabriel Fiol
5
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
6
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
7
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
8
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
9
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
10
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
11
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
12
-
7/28/2019 Apunts PSR V3
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).
Inteligencia Artificial.Gabriel Fiol
13
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
14
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
15
-
7/28/2019 Apunts PSR V3
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
17
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
18
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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:
Inteligencia Artificial.Gabriel Fiol
20
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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= =
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
23
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
24
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
25
AO
TN
AS
Q
NGS
V
T
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
26
y .
Problema con dominios finitos y restricciones binarias (deobligacin).
-
7/28/2019 Apunts PSR V3
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}
Inteligencia Artificial.Gabriel Fiol
27
AO
TN
AS
Q
NGS
V
T
-
7/28/2019 Apunts PSR V3
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).
Inteligencia Artificial.Gabriel Fiol
28
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
29
-
7/28/2019 Apunts PSR V3
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?
Inteligencia Artificial.Gabriel Fiol
30
-
7/28/2019 Apunts PSR V3
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?
Inteligencia Artificial.Gabriel Fiol
31
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
32
T1 T2 T3
E1 1 3 2
E2 3 2 3
E3 2 3 1
-
7/28/2019 Apunts PSR V3
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?
Inteligencia Artificial.Gabriel Fiol
33
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
34
E1 1 3 2
E2 3 2 1
E3 2 3 1
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
35
Grafo de restricciones
-
7/28/2019 Apunts PSR V3
36/183
Grafo de restricciones
Ejemplo
AO
TN
AS
Q
NGS
V
T
Inteligencia Artificial.Gabriel Fiol
36
AO
TN
AS
Q
NGS
VT
Tipos de restricciones segn el nmero de
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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
-
7/28/2019 Apunts PSR V3
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)
Inteligencia Artificial.Gabriel Fiol 39
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.
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 40
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 41
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 42
Cuando en un problema existen restricciones de obligacin
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 43
4 R l i d PSR i d
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 44
Ventajas:
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 45
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 46
Consideraciones generales sobre la eficiencia
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 47
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)
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 48
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.
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 49
L PSR d i i t
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 50
Bsqueda con vuelta atrs para PSRs
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 51
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 52
(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.
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 53
.
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.
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 54
AO = rojoTN = verde
AO = rojoTN = azul
AO = rojoTN = verdeQ = rojo
AO = rojoTN = verdeQ = azul
Bsqueda primero en profundidad con
-
7/28/2019 Apunts PSR V3
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,
Inteligencia Artificial.Gabriel Fiol 55
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)
-
7/28/2019 Apunts PSR V3
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)
Inteligencia Artificial.Gabriel Fiol 56
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.
-
7/28/2019 Apunts PSR V3
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:
- - -
Inteligencia Artificial.Gabriel Fiol 57
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 58
funcin busqueda general(PSR) retorna nodo o fallo
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 59
Algunas cuestiones fundamentales relacionadas con laseleccin de una buena heurstica
-
7/28/2019 Apunts PSR V3
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?
.
Inteligencia Artificial.Gabriel Fiol 60
Las respuestas a las anteriores cuestiones han hecho
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 61
5 Tcnicas para la mejora de la eficincia
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 62
A. Heursticas para la seleccin de variable yordenamiento de valor
-
7/28/2019 Apunts PSR V3
63/183
ordenamiento de valor
Recurdese la sentencia de asignacin de variable delanterior algoritmo:
var Selecciona-variable-no-asignada(variables(PSR),asignacin, PSR)
Inteligencia Artificial.Gabriel Fiol 63
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 64
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol 65
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol 66
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
69/183
la heurstica basada en la anterior idea.
Inteligencia Artificial.Gabriel Fiol
69
Como conclusin general, la heurstica de
-
7/28/2019 Apunts PSR V3
70/183
mnimos valores restantes ha dadomejores resultados que el gradoheurstico, pero ste puede ser til para el
desempate.
Inteligencia Artificial.Gabriel Fiol
70
Heurstica de seleccin del valor de una variable
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
72/183
Ejemplo. En el grafo de la figura, una vez realizadas las asignaciones
AO
AS
Q
NGS
V
T
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
74
de prever futuras inconsistencias.
A continuacin se estudian algunos mtodos
-
7/28/2019 Apunts PSR V3
75/183
g
que permiten observar por adelantado lasconsecuencias de las restricciones cuando seasignan valores a variables.
Inteligencia Artificial.Gabriel Fiol
75
B.1 Comprobacin hacia delante (forward checking)
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
76
La siguiente figura muestra el progreso de la bsqueda
para el ejemplo de coloracin de zonas.
AO
TNQ T
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
78
Ejercicio. Combnese la comprobacin hacia delantecon las heursticas MVR y Grado heurstico en el
-
7/28/2019 Apunts PSR V3
79/183
ejemplo del coloreado de zonas.
Inteligencia Artificial.Gabriel Fiol
79
Taller 6
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
80
Taller 6.bis
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
81
Taller 7
-
7/28/2019 Apunts PSR V3
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
83
El forwardEl forward checkingchecking no descubre todas las inconsistenciasno descubre todas las inconsistencias
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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)
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
85
El concepto de consistencia de arco proporcionaun mtodo rpido de propagacin de restricciones
-
7/28/2019 Apunts PSR V3
86/183
que es ms potente que la comprobacin haciadelante.
Inteligencia Artificial.
Gabriel Fiol
86
Definicin formal de la consistencia de arco
di i id
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
87
Consistencia de arco en un PSR
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
88
AO
TN
AS
Q
NGS
TEJEMPLO
-
7/28/2019 Apunts PSR V3
89/183
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 deAO = rojo
R V-A R-V-A R-V-A R-V-A V-A R-V-A
Despus de= verde
R A V R A R-V-A A R-V-A
V
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
90/183
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 = rojo
R V-A R-V-A R-V-A R-V-A V-A R-V-A
Despus deQ = verde
R A V R A R-V-A A R-V-A
Despus de A R R-V-A
V
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
91
Cmo se aplica la consistencia de arco?
R i i d l
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
92
Ejemplo. Planificacin de las acciones de un robot
Un robot necesita planificar cinco actividades (A B C D y E) donde
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
93
Paso 1. Definicin formal del problema entrminos de un PSR
-
7/28/2019 Apunts PSR V3
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
-
7/28/2019 Apunts PSR V3
95/183
Inteligencia Artificial.
Gabriel Fiol
95
Paso 2. Aplicacin de la consistencia de arco
DOMINIOS RESTRICCIONES ARCOS
A REVISAR
DOMINIOSRESULTANTES
-
7/28/2019 Apunts PSR V3
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) ------------------
Inteligencia Artificial.
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)
-
7/28/2019 Apunts PSR V3
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) ------------------
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
98/183
la consistencia de arco, la funcin de sta es slomantener el PSR consistente.
Inteligencia Artificial.
Gabriel Fiol
98
Algoritmo para mantener la consistencia de arco, AC3
El algoritmo para mantener la consistencia de arco AC
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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;
Inteligencia Artificial.
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)
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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?
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
103
La CA no revela todas las inconsistencias
La consistencia de arco no revela todas las inconsistencias
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
105
PSR Fuertemente n-consistente
El concepto de kconsistencia permite definir las formas ms potentesde la propagacin de consistencias.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
108/183
En el peor de los casos, cualquier algoritmo queestablezca la n-consistencia fuerte tendr una
eficiencia exponencial en n.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
110
Ejemplo
TNQ T
R1 R2 R3 R4
-
7/28/2019 Apunts PSR V3
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..
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
112
Ejemplo 2.
Considrese la restriccin de alto orden llamada restriccin de
recursos o restriccin como_mximo.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
114/183
As, si cada variable tiene el dominio {2, 3, 4, 5, 6}, losvalores 5 y 6 pueden suprimirse de cada dominio.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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:
-
7/28/2019 Apunts PSR V3
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]
Inteligencia Artificial.
Gabriel Fiol
116
VueloA [0, 165]; VueloB [0, 385]
VueloA + VueloB [420, 420]
Propagando los lmites de las restricciones los dominios sed
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
119
Ejemplo del coloreado de zonas convuelta atrs cronolgica AO
TN
AS
Q
NGS
V
T
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
Gabriel Fiol
120
U i i i t li t l lt t i t
AO
TN
AS
Q
NGS
V
T
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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.
-
7/28/2019 Apunts PSR V3
122/183
Inteligencia Artificial.
Gabriel Fiol
122
Ejemplo.
Considrese la asignacin parcial {AO=rojo, NGS=rojo, T=rojo} (sabemos
AO
TN
AS
Q
NGS
V
T
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
124/183
Esta idea puede implantarse fcilmente modificando elalgoritmo Bsqueda-Con-Vuelta-Atrs, de manera
que acumule el conjunto conflicto de cada variable.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
126/183
atrs a la variable ms reciente, Xi, tal queXi conflicto(Xj), actualizndose el conjunto
conflicto de Xi, de la siguiente manera:
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
128/183
entonces se vuelve atrs, en este caso a NGS; sino, se
asigna a TNun valor todava no asignado.
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.
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
-
7/28/2019 Apunts PSR V3
130/183
conflicto de la correspondiente variable.
Cuando se vuelve atrs hay que actualizaradecuadamente el conjunto conflicto de las variables
Inteligencia Artificial.
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.
-
7/28/2019 Apunts PSR V3
131/183
Utilizan por lo general una formulacin de estados
completa: en el estado inicial cada variable tiene unvalor asignado.
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
132/183
escoger una reina en cada paso y moverla a otro cuadro
de su columna.
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
133
Implementacindel mtodo(seleccin aleatoria de variable)
Estructura de los nodos: los nodos estan compuestos de laasignacin actual y la ltima variable modificada.
-
7/28/2019 Apunts PSR V3
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;
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
135/183
por un valor particular, considerando el resto de la asignacin actual.
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
136
Propiedades del algoritmo de bsqueda local
No es completo
Complejidad en tiempo: lineal en el nmero de iteraciones
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
138/183
problema de las 8 reinas usando mnimos conflictos para
una posicin inicial dada y una seleccin aleatoria de lavariable.
Inteligencia Artificial.Gabriel Fiol
138
1
3
2
2
2
1
2
3
2
3
3
1
-
7/28/2019 Apunts PSR V3
139/183
1
2
1
3
2
0
situacin inicial
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
141/183
la programacin en no factible. Se desea pues reparar laprogramacin ya hecha con un mnimo nmero de cambios en lamisma.
Inteligencia Artificial.Gabriel Fiol
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
-
7/28/2019 Apunts PSR V3
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:
Inteligencia Artificial.Gabriel Fiol
142
AO
TN
AS
AO
NGS
SG
Q
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
143
Descomposicin del problema en subproblemasindependientes
Dos subproblemas son independientes, si lascaractersticas de la solucin de uno no afecta al otro.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
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.
-
7/28/2019 Apunts PSR V3
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.
Inteligencia Artificial.Gabriel Fiol
145
Descomposicin del problema en un grafo rbol
No obstante, los subproblemas completame