Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Problemas de satisfacción de restricciones en Inteligencia Artificial (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Búsqueda con vuelta atrás para PSR
¿Por qué terrible?:
En el siguiente nivel, el factor de ramificación es (n-1)·d, etcétera para los n niveles.
¡Generamos un árbol con n!·dn hojas, aunque haya sólo dn asignaciones completas!
La formulación del problema, aparentemente razonable pero ingenua, no ha considerado una propiedad crucial común en todos los PSRs:
la conmutatividad
17

Monografias.com

Conmutatividad
Un problema es conmutativo si el orden de aplicación de las acciones no tiene ningún efecto sobre el resultado.
Éste es el caso de los PSRs, donde las acciones son asignaciones de valores a variables.
Por lo tanto, todos los algoritmos de búsqueda para PSR generan los sucesores considerando asignaciones posibles para sólo una variable en cada nodo del árbol de búsqueda.
18

Monografias.com

Conmutatividad
Por ejemplo, en el nodo raíz de un árbol de búsqueda para colorear este mapa:
podríamos tener una opción entre C3 = azul, C3 = rojo y C3 = verde
pero nunca elegiríamos entre C3 = rojo y C1 = azul.
Con esta restricción, el número de hojas es de dn., como era de esperar.
19

Monografias.com

Búsqueda con vuelta atrás
El término búsqueda con vuelta atrás se utiliza para la búsqueda en profundidad que:
elige valores para una variable a la vez y
vuelve atrás cuando una variable no tiene ningún valor legal para asignarle.
El algoritmo
genera los sucesores incrementalmente, uno a la vez
extiende la asignación actual para generar un sucesor, más que volver a copiarlo
20

Monografias.com

Búsqueda con vuelta atrás: algoritmo
21

Monografias.com

Búsqueda con vuelta atrás: algoritmo
función Búsqueda-Con-Vuelta-Atrás(psr) devuelve una solución, o fallo
devolver Vuelta-Atrás-Recursiva({}, psr)

función Vuelta-Atrás-Recursiva(asignación, psr) devuelve una solución, o un fallo
si asignación es completa entonces devolver asignación
var ? Selecciona-Variable-Noasignada(Variables[psr], asignación, psr)
para cada valor en Orden-Valores-Dominio(var, asignación, psr) hacer
si valor es consistente con asignación de acuerdo a las Restricciones[psr] entonces
añadir {var = valor} a asignación
resultado ? Vuelta-Atrás-Recursiva(asignación, psr)
si resultado ? fallo entonces devolver resultado
borrar {var = valor} de asignación
devolver fallo
22

Monografias.com

23
Ejemplo: 4-reinas
Colocar 4 reinas, una en cada fila de un tablero 4×4, sin que se maten.

Variables: R1, … , R4 (reinas)
Dominios: [1 .. 4] para cada Ri (columna)
Restricciones: Ri no-mata Rj

Grafo:
23

Monografias.com

24
Ejemplo: 4-reinas

Monografias.com

25
Propagación de restricciones
Un conjunto de restricciones puede inducir otras (que estaban implícitas).
La propagación de restricciones (PR) es el proceso de hacerlas explícitas.

El papel de la PR es disminuir el
espacio de búsqueda. Se puede realizar
la propagación:
1) como pre-proceso: eliminar zonas del espacio
donde no hay soluciones (arc consistency);
2) durante el proceso:
podar el espacio a medida que la búsqueda
progresa (forward checking).
25

Monografias.com

Propagación de restricciones
Cada ciclo tiene dos partes:
Se propagan las restricciones:
Posible utilización de reglas de inferencia
Las restricciones no tienen por qué ser independientes:
Restricciones que implican a varias variables
Variables que participan en varias restricciones
Se analiza el resultado:
Solución encontrada
Solución imposible
Seguir buscando
26
26

Monografias.com

Propiedades sobre grafos de restricciones
Se pueden definir propiedades sobre los grafos de restricciones que permiten reducir el espacio de búsqueda.
k-consistency: poda de valores que no sean posibles para un grupo de k variables:
Arc consistency (2-consistency): Eliminamos valores imposibles para parejas de variables.
Path consistency (3-consistency): Eliminamos valores imposibles para ternas de variables.

Comenzar con un grafo k-consistent (2, 3…) reduce el número de vueltas atrás.

Monografias.com

Preproceso
Un PSR es arco-consistente si para cada par de variables (Xi, Xj) y para cualquier valor vk de Di existe un valor vl de Dj tal que se satisfacen las restricciones.
Se pretende que todas las variables sean arco consistentes para todos los arcos que inciden en ellas.
Los dominios actuales de cada variable tienen que ser consistentes con todas las restricciones.

Monografias.com

Preproceso
Si un PSR no es arco-consistente se le puede convertir mediante el siguiente algoritmo:

(Se vuelve a analizar la consistencia de arcos cuyo destino ha podido cambiar.)

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
30

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
31

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
32

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
33

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
34

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
35

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
36

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
37

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
38

Monografias.com

Ejemplo de arco-consistencia: colorear mapa
39

Monografias.com

Propagación durante la búsqueda(forward checking)
Modificación del algoritmo de búsqueda en profundidad con vuelta atrás cronológica
Anticipación: detectar cuanto antes caminos sin solución y podarlos.
Asignar un valor y consultar las restricciones sobre las variables futuras con arco desde la actual
Se eliminan valores no compatibles de los dominios correspondientes a dichas variables futuras
Equivale a hacer arco-consistente la variable actual con las futuras en cada paso.
La eficiencia dependerá del problema.
Se incrementa el coste de cada iteración.

Monografias.com

Algoritmo forward checking

Monografias.com

Ejemplo: 4-reinas mediante forward checking

Monografias.com

Ejemplo: 4-reinas mediante forward checking
R1=1? Propagamos: R2=3,4; R3=2,4; R4=2,3 ? R1=1
R2=3? Propagamos: R3= Ø
R2=4? Propagamos: R3=2; R4=3 ? R2=4
R3=2? Propagamos: R4= Ø
Ningún otro valor para R3. Backtracking a R2
Ningún otro valor para R2. Backtracking a R1
R1=2? Propagamos: R2=4; R3=1,3; R4=1,3,4 ? R1=2
R2=4? Propagamos: R3=1; R4=1,3 ? R2=4
R3=1? Propagamos: R4=3 ? R3=1
R4=3? No hay propagaciones ? R4=3

Monografias.com

44
PSR: ejemplo

Monografias.com

45
PSR: ejemplo

Monografias.com

46
PSR: ejemplo

Monografias.com

Forward checking
Idea:
Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
47
47

Monografias.com

48
Forward checking
Idea:
Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
48

Monografias.com

49
Forward checking
Idea:
Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
49

Monografias.com

50
Forward checking
Idea:
Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
50

Monografias.com

51
Forward checking
Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:

NT and SA cannot both be blue!

Constraint propagation repeatedly enforces constraints locally.
51

Monografias.com

52
Arc consistency
Simplest form of propagation makes each arc consistent .
(X Y) is consistent iff:
for every value x of X there is some allowed y
52

Monografias.com

53
Arc consistency
Simplest form of propagation makes each arc consistent .
(X Y) is consistent iff:
for every value x of X there is some allowed y
53

Monografias.com

54
Arc consistency
Simplest form of propagation makes each arc consistent .
(X Y) is consistent iff:
for every value x of X there is some allowed y

If X loses a value, neighbors of X need to be rechecked.
54

Monografias.com

55
Arc consistency
Simplest form of propagation makes each arc consistent .
(X Y) is consistent iff:
for every value x of X there is some allowed y

Arc consistency detects failure earlier than forward checking.
Can be run as a preprocessor or after each assignment.
55

Monografias.com

Heurísticas adicionales
La búsqueda con vuelta atrás puede mejorarse reordenando las variables:
Antes de la búsqueda (primero las mas restrictivas)
Durante la búsqueda:
Variable con mas restricciones
Variable con menos valores
La reordenación de variables puede reducir el tiempo de búsqueda varios ordenes de magnitud en ciertos problemas.

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter