IA - Ponencia 01 v28-03-dia dv1

Vista previa del material en texto

BUSQUEDA DE SATISFACCIÓN DE RESTRICCIONES
Cruz Maldonado, N. Miguel	2016704544
Flores Chalco, Paulina	2016705202
Ibañez Barbaran, Jhoan A.	2016704927
Medina La Torre, Thamar G.	2016704606
Saldivar León, Cesar J.	2016704624
Valencia Castillo, Danny	2016704802
Semestre Académico 2020-1
N. Miguel Cruz Maldonado 
Paulina Flores Chalco
Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre
Cesar J. Saldivar León
Danny Valencia Castillo
EXPOSICION EN GRUPAL Nº 05:
BUSQUEDA DE SATISFACCION DE RESTRICCIONES
Problemas de satisfacción de restricciones, búsqueda de vuelta atrás para PSR.
Búsqueda local para problemas de satisfacción de restricciones, la estructura de los problemas.
UNFV
UNFV
UNFV
UNFV
UNFV
Universidad Nacional
Federico Villarreal
INTELIGENCIA ARTIFICIAL
8F0077
Docente: Jean J. Matos Manguinuri
Tema que como parte del curso presentan los alumnos:
Cruz Maldonado, N. Miguel		2016704544			Flores Chalco, Paulina				2016705202
Ibañez Barbaran, Jhoan A.		2016704927			Medina La Torre, Thamar G.	2016704606
Saldivar León, Cesar J.			2016704624			Valencia Castillo, Danny			2016704802
2021
“Año del Bicentenario del Perú:
 200 años de la Independencia”
Lima - Perú
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
BUSQUEDA EN I.A. 
Definición
Problemas que, para resolverlos de forma exacta, requieren la realización de una búsqueda en un espacio que es de tamaño exponencial.
Nadie sabe como evitar esa búsqueda.
No se espera que nadie lo consiga nunca…
Todos los problemas de los que se ocupa la I.A. son NP-difíciles (si existe un algoritmo rápido para un problema, difícilmente consideraremos que el problema requiere inteligencia).
Si un problema es NP-difícil y tenemos un algoritmo que encuentra la solución de forma rápida y casi siempre correcta, podemos considerar que el algoritmo es “Inteligente”.
La I.A. implica que la búsqueda está sujeta a errores.
NP.- En teoría de la Complejidad Computacional, es el acrónimo en inglés de Nondeterministic Polynomial Time (“Tiempo polinomial no Determinista").
Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista.
Para poder resolver el problema, debemos construir un modelo para basar nuestras decisiones en las consecuencias (hipotéticas) de nuestras acciones:
Descripción inicial
del sistema
Descripción final
del sistema
¿?
Estado 1
Estado 2
Estado n
…
Representa la aplicación de algún operador o transformación del Sistema.
¿Cómo se selecciona, en cada momento, el operador que se debería aplicar?
Problema Típico
 en Inteligencia Artificial
Se dispone de varios operadores (movimientos legales).
Se ha de elegir cuál es el más adecuado en cada momento (¿qué pieza movemos y a dónde?).
No tiene sentido aplicar (ejecutar) el primer operador que sea válido, sino que se debe realizar un proceso previo de búsqueda del mejor operador, tras lo cual se procederá a su aplicación.
EJEMPLO DE PROBLEMA TÍPICO EN I.A.
Ajedrez
 ¿ ?		 Mate del Tonto
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Heurísticas :
¿Qué pieza deberíamos mover en una partida de ajedrez?
¿Qué regla aplicamos en primer lugar al hacer un diagnóstico?
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
¿DE QUÉ CONSTA UNA BÚSQUEDA EN I.A.?
Un problema de búsqueda en I.A. consta de:
Un espacio de estados .
Un conjunto de operadores (acciones, con costes).
Un estado inicial (punto de partida de la búsqueda).
Una función objetivo (comprueba si el estado actual corresponde a una solución del problema).
La búsqueda la realiza un programa (o agente).
El espacio de búsqueda será un grafo dirigido en el que cada nodo representa un posible estado del sistema.
NOTA: Dependiendo del problema, cada nodo incluirá una descripción completa del sistema, o bien sólo las modificaciones necesarias para pasar de un nodo padre a su hijo.
E, 1
Espacio de Estados 
Estado Inicial
Función Objetivo
Acción
Costo
Estado
n1
n2
n3
n4
n5
n6
n7
n8
n9
v1
v3
v4
v7
v6
v5
v9
v14
v2
v10
v12
v13
v15
v16
v8
v11
Donde:
 
 
 
 
Componentes de un Grafo
¿De que Consta una Búsqueda en I.A.?
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
¿De que Consta una Búsqueda en I.A.?
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Espacio de estados .
Conjunto de operadores (acciones, con costes).
Estado inicial (punto de partida de la búsqueda).
Función objetivo (comprueba si el estado actual corresponde a una solución del problema).
Agente o programa (el que realiza la búsqueda).
Grafo dirigido en el que cada nodo representa un posible estado del sistema (espacio de búsqueda)
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
BUSQUEDA EN UN
 ESPACIO DE ESTADOS 
Definición
Espacio de Estados:
Representación del problema a través de las (posibles) acciones del agente.
Búsqueda en el Espacio de Estados:
Resolución del problema mediante la proyección de las distintas acciones del agente.
Grafo:
Representación matemática de un problema de búsqueda.
Nodos: Estados. 
Arcos: Operadores
Tipos 
Grafo del Espacio de Estados – Grafo Implícito.
Árbol de Búsqueda – Grafo Explicito.
Posibles Acciones del Agente (Operadores)
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
GRAFO DEL ESPACIO
GRAFO IMPLÍCITO
Definición
Grafo teórico que representa todas las posibles transformaciones del sistema aplicando todos los operadores posibles recursivamente.
Debido a su complejidad exponencial, que requeriría una cantidad inviable de memoria y tiempo, el grafo del espacio de estados no puede generarse por completo.
Debido a la complejidad exponencial del grafo implícito, se irá generando, paso a paso, una porción del grafo conforme avance el proceso de búsqueda.
Un problema puede tener varias soluciones, pero debido a la extensión del grafo implícito, no podemos explorarlo por completo, por lo que tampoco podemos buscar la mejor solución al problema (suponiendo algún criterio de optimalidad). 
Grafo del Espacio de Estados - Grafo Implícito
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Árbol de Búsqueda – Grafo Explicito
ÁRBOL DE BUSQUEDA
GRAFO EXPLÍCITO
Debido a la complejidad exponencial del grafo implícito, se irá generando, paso a paso, una porción del grafo conforme avance el proceso de búsqueda.
Definición
Es el subgrafo del grafo implícito que se va generando durante el proceso de búsqueda de una secuencia de operadores que resuelva nuestro problema (camino solución).
Usualmente, en forma de árbol, de ahí su nombre.
Nodo raíz: Estado inicial.
Hijos de un nodo: Posibles sucesores (nodos correspondientes a estados resultantes de la aplicación de un operador al nodo padre).
Los nodos del árbol representan estados, pero corresponden a PLANES mediante los cuales se alcanzan dichos estados.
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Estado Inicial
Sucesor 2
Sucesor 1
Sucesor 3
Futuros Posibles
CONDICIONES DE PARADA
Se ha encontrado la solución.
Se ha acabado el tiempo disponible.
Se ha llegadoa un nivel de profundidad determinado.
AGENTES SEGÚN
 EL TIPO DE PROBLEMA
Según el tipo de problema, nos podemos encontrar con agentes de búsqueda :
Que Devuelven un Único Operador.
Juegos con adversario (como el ajedrez)
Devuelven una Secuencia de Operadores.
Juegos sin adversario (como el 8-puzzle).
Sistemas de planificación.
Sistemas Expertos (con encadenamiento hacia adelante).
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
	2	8	3
	1	6	4
	7		5
	1	2	3
	8		4
	7	6	5
	2	8	3
	1	6	4
	7		5
	2	8	3
	1		4
	7	6	5
	2		3
	1	8	4
	7	6	5
	2	8	3
	1	6	4
		7	5
	2	8	3
	1	6	4
	7	5	
	2	8	3
	1	4	
	7	6	5
	2	8	3
		1	4
	7	6	5
		2	3
	1	8	4
	7	6	5
	1	2	3
		8	4
	7	6	5
	2	3	
	1	8	4
	7	6	5
	1	2	3
	8		4
	7	6	5
	1	2	3
	7	8	4
		6	5
En el problema del 8-puzzle hay que encontrar un camino desde la Configuración inicial hasta una determinada Configuración Final.
8-Puzzle
Ejemplo: Condiciones de Parada 
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Descripción
Inicial
del Sistema
Descripción
Final
del Sistema
Estado 1
Estado X
Estado n
…
Proceso de Búsqueda
Movimiento del Adversario
Proceso de Búsqueda
Ajedrez
…Que Devuelven 
un Único Operador
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
…Que Devuelven 
una Secuencia de Operadores
Descripción
Inicial
del Sistema
…
Descripción
Final
del Sistema
Estado 1
Estado 2
Estado n
8-Puzzle
Proceso de Búsqueda
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
1983
USO DE INFORMACIÓN
Un problema puede tener varias soluciones, pero debido a la extensión del grafo implícito, no podemos explorarlo por completo, por lo que tampoco podemos buscar la mejor solución al problema (suponiendo algún criterio de optimalidad). 
Por eso, en muchos problemas de I.A. nos conformamos con buscar soluciones aceptables (cualquier camino a una solución lo suficientemente buena) y no soluciones óptimas (la mejor solución posible).
NOTA: Existen técnicas matemáticas/algorítmicas para resolver determinados tipos de problemas de optimización, por ejemplo la programación dinámica.
-3
-5
-5
-3
-3
-4
-6
	2	8	3
	1	6	4
	7		5
	2	8	3
	1		4
	7	6	5
	2		3
	1	8	4
	7	6	5
	2	8	3
	1	6	4
		7	5
	2	8	3
	1	6	4
	7	5	
	2	8	3
	1	4	
	7	6	5
	2	8	3
		1	4
	7	6	5
-4
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
USO DE INFORMACIÓN
Heurísticas
Son criterios, métodos o principios para decidir cuál de entre varias acciones promete ser la mejor para alcanzar una determinada meta.
En la generación del árbol de búsqueda, nos podemos guiar con heurísticas que nos den una indicación acerca de cómo de bueno o prometedor es un determinado estado u operador.
El uso de heurísticas nos permite convertir nuestra búsqueda de una solución en un proceso guiado de ensayo y error.
NOTA: Compárese el uso heurístico de información para guiar el proceso de búsqueda en Inteligencia Artificial con formalismos como la teoría de la decisión o la teoría de juegos, que en ocasiones nos permitirán determinar la decisión óptima si somos capaces de identificar todos los factores relevantes para el problema en cuestión (y las incertidumbres asociadas a ellos !!).
	2	8	3
	1	6	4
	7		5
	1	2	3
	8		4
	7	6	5
8-puzzle
Ya que conocemos el estado final deseado, podemos utilizar la siguiente función heurística:
f(tablero)= - número de piezas mal colocadas con respecto al objetivo
f(E) = -4
f(OBJ) = 0
-3
-5
-5
-
-3
-3
-4
-5
-6
	2	8	3
	1	6	4
	7		5
	2	8	3
	1		4
	7	6	5
	2		3
	1	8	4
	7	6	5
	2	8	3
	1	6	4
		7	5
	2	8	3
	1	6	4
	7	5	
	2	8	3
	1	4	
	7	6	5
	2	8	3
		1	4
	7	6	5
-4
-2
-4
0
-2
		2	3
	1	8	4
	7	6	5
	1	2	3
		8	4
	7	6	5
	2	3	
	1	8	4
	7	6	5
	1	2	3
	8		4
	7	6	5
	1	2	3
	7	8	4
		6	5
DIFERENCIAS ENTRE
GRAFO IMPLÍCITO
GRAFO EXPLÍCITO
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
GRAFO IMPLICITO O DEL ESPACIO
Grafo teórico que representa todas las posibles transformaciones del sistema aplicando todos los operadores posibles recursivamente.
DIFERENCIAS ENTRE
GRAFO IMPLÍCITO
GRAFO EXPLÍCITO
GRAFO EXPLICITO O ÁRBOL DE BUSQUEDA
Debido a la complejidad exponencial del grafo implícito, se irá generando, paso a paso, una porción del grafo conforme avance el proceso de búsqueda.
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
PROBLEMA DE SATISFACCIÓN DE RESTRICCIONES
(PSR) 
PROBLEMA DE SATISFACCIÓN DE RESTRICCIÓN
VARIABLES
Vi
DOMINIOS
Di
RESTRICCIONES
Ci
VALORES
Vi = Vj tal que Vj ∈ Di 
ASIGNACIÓN
CONSISTENTE
FUNCIÓN OBJETIVA 
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES
Estado Mundial:
Conjunto bien definido de Variables Vi con Dominio Di
Prueba de objetivo:
Satisface un conjunto de restricciones que especifican combinaciones permitidas de valores para subconjuntos de variables.
Profundidad Primera Búsqueda Adecuada: 
La ruta no importa, solo el estado del objetivo, la profundidad máxima fijada en n, el número de variables, seleccione 1 variable para ramificar en cada nivel del árbol.
Retroceso: 
Una vez que se viola una restricción, no tiene sentido buscar más
Verificación hacia Adelante: 
Conozca el factor de ramificación al "encoger" los dominios de las variables no establecidas para reflejar las restricciones impuestas por las variables ya establecidas. Retroceda si algún dominio de variables no establecido está vacío 
Un Problema de Satisfacción de Restricciones (PSR) viene definido por los siguientes elementos: 
Un Conjunto finito de Variables: X1, X2, X3,… Xn 
X1 X2 X3 X4
Cada variable Xi tiene un dominio Di no vacío de valores posibles, vi. 
Estados: 4 reinas en 4 columnas (44 = 256 Estados).
Un conjunto finito de dominios Di asociados a cada Variable Xi , especificando los posibles valores que puede tomar.
{ Xi = Vi , XJ = VJ , … }
Conjunto finito de Restricciones: C1, C2,… Cn , que definen una serie de propiedades que deben verificar los valores asignados a las Variables.
Cada restricción Ci involucra algún subconjunto de las variables y especifica las combinaciones permitidas de valores vi’s para ese subconjunto.
Operadores: Mover reina en columna.
Prueba Objetivo: No Atacarse.
∀ i, j no atacarse ( Xi, Xj )
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
TIPOS DE PSR
Clasificación según:
El Tipo de Restricciones:
Restricciones de Obligación.
Hard Constraints.
Restricciones de Preferencia.
Soft Constraints.
Los Dominios:
Dominios Discretos.
Finitos.
n variables, tamaño de dominio d→O (dn) asignaciones completas.
p.ej., PSR booleanos, como 3-SAT (NP-completo).
En el peor de los casos, no se pueden resolver CSP de dominio finito en menos de un tiempo exponencial 
Infinitos.
Enteros, cadenas, etc.
p.ej., programación de trabajos, las variables son los días de inicio / finalización de cada trabajo.
Necesita un lenguaje de restricción,por ejemplo, StartJob1 + 5 ≤ StartJob3
Un Estado o solución del Problema se define mediante una asignación de valores a algunas o todas las variables :
{Xi = vi, Xj = vi, ...} tal que vi ∈ Di y se verifican las restricciones.
Evaluación: h(n) = Número de ataques.
Esta formulación permite una representación simple del problema, y el uso de heurísticas de propósito general, independientes del problema Una asignación es consistente o legal si no se viola ninguna restricción.
h = 5
h = 2
h = 0
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
TIPOS DE PSR
Dominios Continuos.
p.ej., horas de inicio / finalización para las observaciones del telescopio espacial Hubble
Restricciones lineales que se pueden resolver en tiempo polinomial mediante programación lineal
El Número de Variables Implicadas en las Restricciones:
Restricciones Unarias.
Involucran una sola variable.
p.ej., SA ≠ verde 
Restricciones Binarias.
Involucran pares de variables.
p.ej., SA ≠ WA
Restricciones Múltiples.
O de orden superior involucran 3 o más variables. 
p.ej., restricciones de columna de Criptaritmética. 
Coloque N Reinas en un tablero de ajedrez N X N para que ninguna Reina pueda atacar a ninguna otra Reina.
Formulación del Problema: 
N variables (N reinas)
Valores de N2 para cada variable que representa las posiciones en el tablero de ajedrez.
Variables: V1, . . . , VN
Dominios: Di = {1, . . . , N}
Restricciones:
Jaque horizontal: Vi ≠ Vj
Jaque diagonal: |Vi − Vj | ≠ |i − j|
Ejemplo (V1 = 1, V2 = 3):
Problema con dominios finitos y restricciones binarias (de obligación).
Ejemplo: N reinas
Variables: Xij
Dominios: {0, 1}
Restricciones: 
∑ij Xij = N
(Xij, Xik) ∈ {(0,0),(0,1),(1,0)}
(Xij, Xkj) ∈ {(0,0),(0,1),(1,0)}
(Xij, Xi+k, j+k) ∈ {(0,0),(0,1),(1,0)}
(Xij, Xi+k, j-k) ∈ {(0,0),(0,1),(1,0)}
Poner n reinas en un tablero n x n sin dos reinas en la misma fila, columna o diagonal
Variables: Qi
Dominios: {1,…, n}
Restricciones: 
∀ i, j no atacarse ( Qi, Qj )
Xij
Q1
Q2
Q3
Q4
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Ejemplo : N Reinas
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Solución PSR de las n-reinas
Primer paso: Representación de la solución
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Ejemplo : N Reinas
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Si esta en la misma fila o están en la misma diagonal dos reinas
EVALUA
Variables: WA, NT, Q, NSW, V, SA, T
Dominios: {rojo, verde, azul}
Restricciones: las regiones adyacentes deben tener diferentes colores
WA ≠ NT, o (WA, NT) en {(rojo, verde), (rojo, azul), (verde, rojo),
(verde, azul), (azul, rojo), (azul, verde)}
Problema con dominios finitos y restricciones binarias (de obligación).
Usando tres colores (rojo, azul, verde) colorear el mapa de Australia
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
WA
NT
SA
Q
NSW
V
T
Ejemplo : Mapa para Colorear
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Gráfico de Restricción
WA
NT
SA
Q
NSW
V
T
Gráfico de restricción:
Los nodos son variables. 
Los arcos son limitaciones.
PSR Binario:
Cada restricción relaciona dos variables.
PSR se ajusta a un patrón estándar.
Un conjunto de variables con valores asignados.
Función de sucesor genérico y prueba de objetivo.
Heurística genérica.
Reducir la complejidad.
EVALUA
Como Problema de Búsqueda.
Estado inicial:
{} - Todas las variables están sin asignar.
Función sucesora:
Se asigna un valor a una de las variables no asignadas sin conflicto.
Prueba de objetivos:
Una tarea completa. 
Costo de ruta:
Un costo constante por cada paso
La solución aparece en la profundidad n si hay n variables.
Los métodos de búsqueda local o en profundidad funcionan bien.
Las Soluciones de PSR pueden ser más rápido.
La Solución de PSR puede eliminar rápidamente gran parte del espacio de búsqueda.
Si {SA = azul}.
Luego, 35 asignaciones se pueden reducir a 25 asignaciones, una reducción del 87%.
En un PSR, si una asignación parcial no es una solución, podemos descartar inmediatamente nuevos refinamientos.
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Resolviendo PSR como 
 Problema de Búsqueda
WA
NT
SA
Q
NSW
V
T
EVALUA
Usando el algoritmo AC-3 para demostrar que la consistencia del arco es capaz de detectar la inconsistencia de la asignación parcial {WA = rojo, V = azul} en el siguiente problema de coloración del mapa. 
Un posible trazo del algoritmo: 
Eliminar SA-WA, eliminar rojo de SA
Eliminar SA-V, eliminar azul de SA, dejando solo verde 
Eliminar NT-WA, eliminar rojo de NT
Elimine NT-SA, elimine el verde de NT, dejando solo el azul
Eliminar NSW-SA, eliminar verde de NSW
Elimine NSW-V, elimine el azul de NSW, dejando solo el rojo
Eliminar Q-NT, eliminar azul de Q
Eliminar Q-SA, eliminar verde de Q 
Elimine Q-NSW, elimine el rojo de Q, sin dejar una asignación adecuada para Q
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Resolviendo PSR con Algoritmo AC-3 (Arc Consistency #3)
NT
SA
Q
NSW
V
T
WA
EVALUA
Considere colorear mapas con solo dos colores.
Cada arco es consistente inicialmente.
Compruebe la consistencia de la ruta del conjunto {WA, SA} con respecto a NT.
De manera más general, k-consistencia
1-consistencia = consistencia de nodo.
2-consistencia = consistencia del arco.
3-consistencia = consistencia de ruta.
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Consistencia de Ruta
NT
SA
Q
V
T
WA
NSW
EVALUA
El recorrido simulado de alta escalada, normalmente funciona con estados "completos", es decir, todas las variables asignadas.
Aplicando PSR:
Permitir estados con restricciones insatisfechas.
Los operadores reasignan valores de variables.
Selección de variable:
Seleccione aleatoriamente cualquier variable en conflicto.
Selección de valores por heurística de conflictos mínimos:
Elija el valor que viole la menor cantidad de restricciones.
Es decir, alta escalada con h(n) = número total de restricciones violadas.
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Las soluciones son asignaciones completas y consistentes, 
WA = rojo, NT = verde, Q = rojo, NSW = verde, V = rojo, SA = azul, T = verde
Búsqueda Local PSR
NT
SA
Q
V
T
WA
NSW
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia CastilloWA = rojo, NT = verde,
Q = rojo, NSW = verde,
V = rojo, SA = azul, 
T = verde
Estados:
Variables y Valores asignados hasta ahora 
Estado Inicial:
La asignación vacía 
Acción:
Elija cualquier variable no asignada y asígnele un valor que no viole ninguna restricción
Falla si no hay asignaciones legales 
Prueba de objetivos:
La asignación actual está completa y satisface todas las restricciones.
Las soluciones son asignaciones completas y consistentes 
Formulación de Búsqueda Estándar (Incremental) 
WA
NT
Q
NSW
SA
T
WA
NT
Q
NSW
SA
T
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
En PSR, las asignaciones de variables son conmutativas 
Por ejemplo, [WA = rojo luego NT = verde] es lo mismo que [NT = verde luego WA = rojo]
Solo necesitamos considerar las asignaciones a una sola variable en cada nivel (es decir, fijamos el orden de las asignaciones)
Entonces solo quedan mn hojas 
La búsqueda en profundidad para los PSR con asignaciones de una sola variable se denomina búsqueda de retroceso.
Algoritmo de Búsqueda en Retroceso
Hacer que la búsqueda de retroceso sea eficiente:
¿Qué variable debería asignarse a continuación?
¿En qué orden se deben probar sus valores?
¿Podemos detectar temprano el fracaso inevitable? 
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Las soluciones son asignaciones completas y consistentes, 
WA = rojo, NT = verde, Q = rojo, NSW = verde, V = rojo, SA = azul, T = verde
Ejemplo : Mapa para Colorear
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Las soluciones son asignaciones completas y consistentes, 
WA = rojo, NT = verde, Q = rojo, NSW = verde, V = rojo, SA = azul, T = verde
Ejemplo : Mapa para Colorear
EVALUA
X2 X1
Variables: T, W, O, F, U, R
X1, X2
Dominios: {0, 1, 2, …, 9}
Restricciones: 
O + O = R + 10 * X1
W + W + X1 = U + 10 * X2
T + T + X2 = O + 10 * F
Todas las Diferencias (T, W, O, F, U, R)
T ≠ 0, F ≠ 0
Ejemplo : Criptaritmética
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Las soluciones son asignaciones completas y consistentes, 
WA = rojo, NT = verde, Q = rojo, NSW = verde, V = rojo, SA = azul, T = verde
EVALUA
Variables: Xij
Dominios: {1, 2, …, 9}
Restricciones: 
Todas las Diferencias (Xij en la misma unidad)
Ejemplo : Sudoku
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Las soluciones son asignaciones completas y consistentes, 
WA = rojo, NT = verde, Q = rojo, NSW = verde, V = rojo, SA = azul, T = verde
Xij
EVALUA
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
ESO ES TODO DE NUESTRA PONENCIA.
GRACIAS TOTALES
¿Qué es una Prueba de Turing?
Breve historia de la Prueba de Turing y su impacto 
https://www.youtube.com/watch?v=4VROUIAF2Do&feature=emb_logo
What is a Turing Test? A Brief History of the Turing Test and its Impact
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo
Eye on Tech
CONOCE
N. Miguel Cruz Maldonado | Paulina Flores Chalco | Jhoan A. Ibañez Barbaran
Thamar G. Medina La Torre | Cesar J. Saldivar León | Danny Valencia Castillo