4.
- Dado el grafo siguiente, que representa el espacio de búsqueda de un problema, modelizado
mediante una representación por estados:
Estado Sucesores de Estado (h=valor heurı́stico en Sucesor,
c=costo desde Estado a Sucesor)
A (Inicio) (h=1) B (h=7 c=3), C (h=3 c=1), D (h=1 c=1)
B E (h=6 c=13)
C F (h=5 c=2)
D J (h=2 c=3), K (h=18 c=3), H (h=7 c=2)
E NINGUNO
F L (h=5 c=1)
H I (h=0 c=7)
I (Meta) NINGUNO
J M (h=10 c=12)
K NINGUNO
L I (h=0 c=5)
M NINGUNO
a) ¿Es la heurı́stica definida admisible? Justifica la respuesta.
Resolverlo mediante los siguientes procedimientos. Mostrar y analizar las soluciones encontradas.
b) Ascensión de Colinas
c) Temple Simulado
d) A
SOLUCIÓN
El grafo de búsqueda que nos describe la información proporcionada es el siguiente.
A1
A1 1
3 1 1
3 1 1
f=1+3=4 f=1+1=2 B7 C3 D1
B7 3
C3 2
D1
13 2 3 3 2
2 3 3 2
8 f=4+2=6 f=4+18=22 f=3+7=10 E6 F5 J2 K18 H7
F5 4
J2 K18 H7
1 12
1 12
9
f=16+10=26 L5 M10 7
L5 M10
6 5
5
=0 I0
7
I0
c) Resolvamos el problema mediante el procedimiento local Temple Simulado.
Primero, notar que estamos minimizando y que lo que se muestra es una simulación. Para
Mediante
ello, vamos a fijar proced. Adel procedimiento.
los parámetros
• T ← 60; • esquema ← decrecimiento constante 20; • Lt ← 2
Lista de no s aleatorios (entre 0 y 1): (0.949, 0.893, 0.999, 0.001, 0.456, 0.357, ...)
Empezamos
1) actual = A
• Esquema: T = 60.
• Como T 6= 0 el procedimiento continúa.
2
• Lt ← 1
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = B(7)
◦ 4E = v(actual) − v(siguiente) = 1 − 7 < 0.
◦ Elegimos “siguiente” con probabilidad e4E/T = e−6/60 =0.905
0.949=No aleatorio∈ [0, 1]. Como 0.949>0.905 no cogemos “siguiente”.
• Lt ← 2
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = C(3)
◦ 4E = v(actual) − v(siguiente) = 1 − 3 < 0.
◦ Elegimos “siguiente” con probabilidad e4E/T = e−2/60 =0.967
0.893=No aleatorio∈ [0, 1]. Como 0.893<0.967 cogemos “siguiente”. actual ← C
2) actual = C
• Esquema: T ← T − 20 = 40
• Como T 6= 0 el procedimiento continúa.
• Lt ← 1
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = F (5)
◦ 4E = v(actual) − v(siguiente) = 3 − 5 < 0.
◦ Elegimos “siguiente” con probabilidad e4E/T = e−2/40 =0.951
0.999=No aleatorio∈ [0, 1]. Como 0.999>0.951 no cogemos “siguiente”.
• Lt ← 2
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = F (5)
◦ 4E = v(actual) − v(siguiente) = 3 − 5 < 0.
◦ Elegimos “siguiente” con probabilidad e4E/T = e−2/40 =0.951
0.001=No aleatorio∈ [0, 1]. Como 0.001<0.951 cogemos “siguiente”. actual ← F
3) actual = F
• Esquema: T ← T − 20 = 20
• Como T 6= 0 el procedimiento continúa.
• Lt ← 1
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = L(5)
◦ 4E = v(actual) − v(siguiente) = 5 − 5 como no es mayor que 0.
◦ Elegimos “siguiente” con probabilidad e4E/T = e0/20 =1
0.456=No aleatorio∈ [0, 1]. Como 0.456<1 cogemos “siguiente”. actual ← L
• Lt ← 2
◦ Seleccionamos un sucesor aleatorio de actual: siguiente = I(0)
◦ 4E = v(actual) − v(siguiente) = 5 − 0 > 0.
◦ Elegimos “siguiente”. actual ← I
4) actual = I
• Esquema: T ← T − 20 = 0
• Como T = 0 entonces se termina y se devuelve la solución obtenida: devuelve el
nodo I.
Guardando punteros a los padres de los nodos, obtendrı́amos el camino A-C-F-L-I (costo 9).