BusquedaEnElEspacioDeEstados presentacion

B´
usqueda general

B´
usqueda con adversarios

B´usqueda en el espacio de estados
Ver´
onica E. Arriola-Rios
Inteligencia Artificial

31 de agosto de 2015

Ver´
onica E. Arriola-Rios

B´
usquedaReferencias

B´
usqueda general

B´
usqueda con adversarios

Temas

1

B´
usqueda general

2

B´
usqueda con adversarios

Ver´
onica E. Arriola-Rios

B´
usqueda

Referencias

B´
usqueda general

B´usqueda con adversarios

Referencias

Nodo de una b´usqueda
Un Nodo que contendr´a los elementos siguientes:
Estado. La representaci´
on de un estado en el espacio de
estados.
Nodo padre. Una referenciaa su nodo predecesor inmediato
en el ´arbol de b´
usqueda.
Acci´on. La acci´on que, al realizarse en el estado del nodo
padre produce el estado de este nodo.
Costo del camino. El costo total delcamino que lleva a este
nodo.
Profundidad. La profundidad de este nodo en el ´arbol de
b´
usqueda.

Ver´
onica E. Arriola-Rios

B´
usqueda

B´
usqueda general

B´
usqueda con adversarios

ReferenciasAlgorithm 1 B´
usqueda en un ´arbol.
1:
2:
3:
4:
5:
6:
7:
8:

´
´ squedaEnArbol(problema,
function Bu
estrategia)
margen ← { new NodoB´
usqueda(problema.estadoInicial)}
loop
if vac´ıa(margen) thenreturn Fallo
nodo ← seleccionaDe(margen, estrategia)
if problema.PruebaEsMeta(nodo.estado) then
return caminoA(nodo)
margen ← margen + expande(problema, nodo)

Ver´
onica E. Arriola-Rios

B´
usqueda

B´usqueda general

B´
usqueda con adversarios

Referencias

Para generar las diferentes estrategias de b´
usqueda se puede:
Cambiar la estructura de datos adecuada para alterar el orden
en que seselecciona el nodo siguiente,
O en la l´ınea 8, modificar la posici´
on en la estructura donde
son agregados los nodos a expandir.
B´
usqueda en profundidad: la lista abierta es una pila.
B´
usqueda enamplitud: la lista abierta es una cola.

Agregar el uso de una lista cerrada para no volver a expandir
nodos que lleven a estados ya visitados ⇒ b´
usqueda en grafos.

Ver´
onica E. Arriola-Rios

B´...