Métodos de Búsqueda Ciega e Informados
INTELIGENCIA ARTIFICIAL
TEMAS

Métodos de Búsqueda Ciega
Amplitud
 Profundidad
 No determinístico


Métodos Informados
La función Evaluadora
 Ascenso a la Colina
 Primero el Mejor
 A*
 Ramificación y Acotación

MÉTODOS DE BÚSQUEDA CIEGA
Son procedimientos de búsqueda del estado
meta sobre el árbol de estado.
 Sólo consideran la relación de precedencia
entre estados.
 No se considera información de beneficio o
utilidad de pasar de un estado a otro.

MÉTODOS DE BÚSQUEDA CIEGA

Implementación con Listas:
 LE
 Lista de nodos en espera de proceso
 LV  Lista de nodos ya procesados
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN AMPLITUD

El procedimiento consiste en:
 Iniciar
en el nodo raíz.
 Mientras que el nodo no corresponde al nodo meta
Generar
 Terminar
nodos sucesores no redundantes a este
si se encontró el estado meta o no hay
más nodos para verificar.
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN AMPLITUD

Implementación con listas:
 Se
compara el primer elemento de LE
P
 Se
Q
R
registran los sucesores al final de LE
Q
R
Hijos(P)
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN AMPLITUD

Algoritmo:
Inicio
1. LE := (Estado_Inicial);
2. LV:= ();
Test de Parada
3. Si (LE = ()) entonces
Escribir («No hay solución»), PARE;
4. LISTA := Primer (LE);
5. P := Ultimo (LISTA);
6. Si (P es meta) entonces
Escribir («Solución: », P), PARE;
Genera Sucesores
7. Adiciona_ultimo (P, LV);
8. Elimina_primer (LE);
9. Para (Nodos  (Hijos(P) - LV))
W_LISTA := LISTA;
Adiciona_ultimo (Nodo, W_LISTA);
Adiciona_ultimo(W_LISTA, LE);
Fin_Para
10. Ir para 3
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN AMPLITUD

Ejemplo: Determine un camino para a-k
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN AMPLITUD
#
LE
P
LV
1
((a))
a
()
2
((a b) (a d) (a c))
b
(a)
3
((a d) (a c) (a b i) (a b h))
d
(a b)
4
((a c) (a b i) (a b h) (a d e))
c
(a b d)
5
((a b i) (a b h) (a d e) (a c f) (a c g))
i
(a b d c)
6
((a b h) (a d e) (a c f) (a c g))
h
(a b d c)
7
((a d e) (a c f) (a c g) (a b h k))
e
(a b d c h)
8
((a c f) (a c g) (a b h k) (a d e b))
f
(a b d c h e)
9
((a c g) (a b h k) (a d e b) (a c f j)
g
(a b d c h e f)
10
((a b h k) (a d e b) (a c f j)
k
(a b d c h e f g)
La ruta solución es a-b-h-k
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD

Conceptos:
 Hoja
Nodo del árbol que no tiene sucesores.
 Rama
Camino que inicia en el nodo raíz y termina en un nodo
hoja.
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD

El procedimiento consiste en:
 Buscar
por las ramas del árbol de estados.
 Mientras que en la rama no se encuentra el estado
meta
Generar
 Terminar
nodos sucesores no redundantes a este
si se encontró el estado meta o no hay
más ramas para investigar.
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD

Implementación con listas:
 Se
compara el primer elemento de LE
P
 Se
Q
R
registran los sucesores al inicio de LE
Hijos(P)
Q
R
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD

Algoritmo:
Inicio
1. LE := (Estado_Inicial);
2. LV:= ();
Test de Parada
3. Si (LE = ()) entonces
Escribir («No hay solución»), PARE;
4. LISTA := Primer (LE);
5. P := Ultimo (LISTA);
6. Si (P es meta) entonces
Escribir («Solución: », P), PARE;
Genera Sucesores
7. Adiciona_ultimo (P, LV);
8. Elimina_primer (LE);
9. Para (Nodos  (Hijos(P) - LV))
W_LISTA := LISTA;
Adiciona_ultimo (Nodo, W_LISTA);
Adiciona_primero (W_LISTA, LE);
Fin_Para
10. Ir para 3
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD
 Ejemplo: Determine un camino para a-k
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA EN PROFUNDIDAD
#
LE
P
LV
1
((a))
a
()
2
((a b) (a d) (a c))
b
(a)
3
((a b i) (a b h) (a d) (a c))
i
(a b)
4
((a b h) (a d) (a c))
h
(a b i)
5
((a b h k) (a d) (a c))
k
(a b i h)
La ruta solución es a-b-h-k
MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA NO DETERMINÍSTICA
El procedimiento consiste en seleccionar un
nodo aleatoriamente de la lista LE.
 Los nodos sucesores pueden ser colocados
tanto al inicio como el final.

MÉTODOS DE BÚSQUEDA CIEGA:
BÚSQUEDA NO DETERMINISTA

Algoritmo:
Inicio
1. LE := (Estado_Inicial);
2. LV:= ();
Test de Parada
3. Si (LE = ()) entonces
Escribir («No hay solución»), PARE;
4. P := Aleatorio(LE);
5. Si (P es meta) entonces
Escribir («Solución: », P), PARE;
Genera Sucesores
6. Adiciona_ultimo (P, LV);
7. Elimina_Aleatorio(LE);
8. Adiciona_inicio (Hijos(P)-LV, LE);
9. Ir para 3
MÉTODOS INFORMADOS
Se aplica un conocimiento al proceso de
búsqueda para hacerlo más eficiente.
 El conocimiento esta dado por una función que
estima lo deseable de expandir un nodo.

LA FUNCIÓN EVALUADORA
Mapea cada nodo de búsqueda N a un número
real f(N).
 Mide la utilidad de la información adicional
asociado a cada estado.

h(N)  Función Heurística, costo real del camino
mínimo que une N y un nodo objetivo.
 g(N)  costo del camino de mínimo costo que une el
nodo inicial y N.
 f(N)  costo del camino de mínimo costo que pasa por
N, entre el nodo inicial y un nodo objetivo.

f(N) = h(N)  búsqueda Primero el Mejor
 f(N) = g(N) + h(N)

MÉTODOS INFORMADOS DE BÚSQUEDA:
ASCENSO A LA COLINA
Procedimiento semejante a la búsqueda en
profundidad.
 La diferencia es que los nodos sucesores son
ordenados del mejor al peor valor de su
función de evaluación antes de adicionarse a la
lista LE.

 Minimización
 menor a mayor valor
 Maximización  mayor a menor valor
MÉTODOS INFORMADOS DE BÚSQUEDA:
ASCENSO A LA COLINA

Implementación con listas:
 Se
compara el primer elemento de LE
P
Q
R
 Se
registran los sucesores al inicio de LE luego de
haberlos ordenado.
Hijos(P)
Q
R
MÉTODOS INFORMADOS DE BÚSQUEDA:
ASCENSO A LA COLINA

Algoritmo:
Inicio
1. LE := (Estado_Inicial);
2. LV:= ();
Test de Parada
3. Si (LE = ()) entonces
Escribir («No hay solución»),
PARE;
4. LISTA := Primer o(LE);
5. P := Ultimo(LISTA);
6. Si (P es meta) entonces
Escribir («Solución: », P),
PARE;
Genera Sucesores
7. Adiciona_ultimo (P, LV);
8. Elimina_primero (LE);
9. Hijos_diferentes := Hijos (P) – LV;
10. Ordena(Hijos_diferentes);
11. Para (Nodo  Hijos_diferentes)
Inicio
W_LISTA := LISTA;
Adiciona_final(Nodo,W_LISTA)
;
Adiciona_inicio(W_LISTA, LE);
Fin_Para
12. Ir para 3
MÉTODOS INFORMADOS DE BÚSQUEDA:
ASCENSO A LA COLINA

Ejemplo:


Considerar el siguiente laberinto, en el cual se puede
pasar desde una casilla a cualquiera de las posibles
adyacentes (arriba, abajo, izquierda o derecha), salvo si
hay una barrera entre ellas:
A
B
C
D
E
N
G
I
W
W
M
P
Q
R
T
F
Se trata de encontrar el camino más corto para ir desde la
casilla I a la casilla F.
MÉTODOS INFORMADOS DE BÚSQUEDA:
ASCENSO A LA COLINA
 Función de evaluación:
 F(n)
= Distancia Manhattan a la casilla F
#
LE
P
LV
1
((I)-4)
(I-4)
()
2
((I Q)-3 (I W)-3 (I G)-5)
(Q-3)
(I)
3
((I Q R)-2 (I Q P)-4 (I W)-3 (I G)-5)
(R-2)
(I Q)
4
((I Q R T)-1 (I Q P)-4 (I W)-3 (I G)-5)
(T-1)
(I Q R)
5
((I Q R T K)-2 (I Q P)-4 (I W)-3 (I G)-5)
(K-2)
(I Q R T)
6
((I Q R T K M)-1 (I Q R T K W)-3 (I Q R T K C)-3 (I Q P)-4
(I W)-3 (I G)-5)
(M-1)
(I Q R T K)
7
((I Q R T K M F)-0 (I Q R T K M N)-2 (I Q R T K M D)-2 (I
Q R T K W)-3 (I Q R T K C)-3 (I Q P)-4 (I W)-3 (I G)-5)
(F-0)
(I Q R T K M)
 La
ruta es I-Q-R-T-K-M-F
MÉTODOS INFORMADOS DE BÚSQUEDA:
PRIMERO EL MEJOR
En este procedimiento se ordenan los nodos
después de insertarlos a LE.
 De esta manera el criterio de selección es dado
por el nodo LE que presenta el «mejor» valor de
la función de evaluación.

MÉTODOS INFORMADOS DE BÚSQUEDA:
PRIMERO EL MEJOR
 Implementación con listas:
 Se
compara el primer elemento de LE
P
 Se
R
registran los sucesores en LE.
Hijos(P)
 Se
Q
Q
R
ordenan los elementos de LE.
MÉTODOS INFORMADOS DE BÚSQUEDA:
PRIMERO
EL
MEJOR
8. Elimina_primero (LE);
 Algoritmo:
Inicio
1. LE := (Estado_Inicial);
2. LV:= ();
Test de Parada
3. Si (LE = ()) entonces
Escribir («No hay solución»),
PARE;
4. LISTA := Primer o(LE);
5. P := Ultimo(LISTA);
6. Si (P es meta) entonces
Escribir («Solución: », P),
PARE;
Genera Sucesores
7. Adiciona_ultimo (P, LV);
9. Hijos_diferentes := Hijos (P) – LV;
10. Para (Nodo  Hijos_diferentes)
Inicio
W_LISTA := LISTA;
Adiciona_final(Nodo,W_LISTA)
;
Adiciona_inicio(W_LISTA, LE);
Fin_Para
11. Ordena(LE);
12. Ir para 3

MÉTODOS INFORMADOS DE BÚSQUEDA:
PRIMERO EL MEJOR
Ejemplo:


Considerar el siguiente laberinto, en el cual se puede
pasar desde una casilla a cualquiera de las posibles
adyacentes (arriba, abajo, izquierda o derecha), salvo si
hay una barrera entre ellas:
A
B
C
D
E
N
G
I
W
W
M
P
Q
R
T
F
Se trata de encontrar el camino más corto para ir desde la
casilla I a la casilla F.
MÉTODOS INFORMADOS DE BÚSQUEDA:
PRIMERO EL MEJOR
 Función de evaluación:
 F(n)
= Distancia Manhattan a la casilla F
#
LE
P
LV
1
((I)-4)
(I-4)
()
2
((I Q)-3 (I W)-3 (I G)-5)
(Q-3)
(I)
3
((I Q R)-2 (I W)-3 (I Q P)-4 (I G)-5)
(R-2)
(I Q)
4
((I Q R T)-1 (I W)-3 (I Q P)-4 (I G)-5)
(T-1)
(I Q R)
5
((I Q R T K)-2 (I W)-3 (I Q P)-4 (I G)-5)
(K-2)
(I Q R T)
6
((I Q R T K M)-1 (I Q R T K C)-3 (I W)-3 (I Q R T K W)-3 (I
Q P)-4 (I G)-5)
(M-1)
(I Q R T K)
7
((I Q R T K M F)-0 (I Q R T K M D)-2 (I Q R T K M N)-2 (I
Q R T K C)-3 (I W)-3 (I Q R T K W)-3 (I Q P)-4 (I G)-5)
(F-0)
(I Q R T K M)
 La
ruta es I-Q-R-T-K-M-F
MÉTODOS INFORMADOS DE BÚSQUEDA:
BÚSQUEDA A*

Se considera la siguiente función de
evaluación:
f(N) = g(N) + h(N)
donde:
g(N) = costo de la mejor ruta a N encontrada hasta aquí
h(N) = función heurística admisible
MÉTODOS INFORMADOS DE BÚSQUEDA:
BÚSQUEDA A*

Ejemplo:


Considerar el siguiente laberinto, en el cual se puede
pasar desde una casilla a cualquiera de las posibles
adyacentes (arriba, abajo, izquierda o derecha), salvo si
hay una barrera entre ellas:
A
B
C
D
E
N
G
I
W
W
M
P
Q
R
T
F
Se trata de encontrar el camino más corto para ir desde la
casilla I a la casilla F.
MÉTODOS INFORMADOS DE BÚSQUEDA:
BÚSQUEDA A*
 Función de evaluación:
 F(n)
= g(n) + h(n)
 Donde:
g(n): Número de Casillas que ha avanzado
 h(n): Distancia Manhattan a la casilla F

MÉTODOS INFORMADOS DE BÚSQUEDA:
BÚSQUEDA A*
#
LE
P
LV
1
((I)-4)
(I-4)
()
2
((I Q)-4 (I W)-4 (I G)-6)
(Q-4)
(I)
3
((I Q R)-4 (I W)-4 (I G)-6 (I Q P)-6)
(R-4)
(I Q)
4
((I Q R T)-4 (I W)-4 (I G)-6 (I Q P)-6)
(T-4)
(I Q R)
5
((I W)-4 (I G)-6 (I Q R T K)-6 (I Q P)-6)
(W-4)
(I Q R T)
6
((I W K)-4 (I G)-6 (I Q R T K)-6 (I Q P)-6)
(K-4)
(I Q R T W)
7
((I W K M)-4 (I W K T)-4 (I W K C)-6 (I G)-6 (I Q R T K)-6 (I
(M-4)
Q P)-6)
8
((I W K M F)-4 (I W K T)-4 (I W K C)-6 (I W K M D)-6 (I G)6 (I Q R T K)-6 (I W K M N)-6 (I Q P)-6)
 La
ruta es I-W-K-M-F
(F-4)
(I Q R T W K)
(I Q R T W K M)
RAMIFICACIÓN Y ACOTACIÓN

Ramificar:
Proceso de generar los nodos sucesores de cierto
nodo de un árbol.

Criterios de Ramificación:
 Primero
 FIFO
 LIFO
el mejor
RAMIFICACIÓN Y ACOTACIÓN

Acotación
Proceso de simplificación de la búsqueda a través de
la poda de ramas o subárboles que presentan peores
soluciones.

Actualización de la Cota
Cota del nodo es el valor de la función de evaluación
que tiene un nodo ya procesado.
Si en la ramificación se genera un nodo con mejor
valor, entonces la cota se actualiza.

RAMIFICACIÓN Y ACOTACIÓN
Algoritmo:
Inicio
1. LE := (Estado_Inicial); LV:= (Estado_Inicial); Cota(Estado_Inicial) :=0;
Test de Parada
3. Si (LE = ()) entonces Escribir («No hay solución»), PARE;
4. LISTA := Primer o(LE); P := Ultimo(LISTA);
5. Si (P es meta) entonces Escribir («Solución: », P), PARE;
Ramificación y Acota
6. Elimina_Mejor(LE);
7 Para (Nodo  Hijos(P))
W_LISTA := LISTA;
Si (Nodo  LV)
Adiciona_final(Nodo,W_LISTA);
Adiciona_inicio(W_LISTA, LE);
Cota(nodo) := f(W_LISTA);
Adiciona_ultimo (Nodo, LV);
sino
Si (f(W_LISTA) < Cota(Nodo))
Adiciona_final(Nodo,W_LISTA);
Adiciona_inicio(W_LISTA, LE);
Cota(nodo) := f(W_LISTA);
Fin_Si
Fin_Para
8. Ordena(LE);
9. Ir para 2
Descargar

Métodos de Búsqueda - inteligencia artificial