EspacioEstados

Espacio de Estados

Ejemplo
Misioneros y caníbales
Hay 3 misioneros y 3 caníbales en la orilla izquierda de un río. Un
bote puede transportar a 1 ó 2 personas de una orilla a otra.
Objetivo: pasar a todos a la otra orilla.
 Condición: No puede ocurrir nunca que si en una orilla hay algún misionero
haya a la vez un número mayor de caníbales (se los comerían).


Estados:

Parámetros: númeromisioneros lado izquierdo, número caníbales lado
izquierdo, posición bote (izquierda o derecha).
 Se debe verificar la Condición.


Operadores:

Transportar
 Transportar
 Transportar
 Transportar
 Transportar


1
1
2
2
1

misionero.
caníbal.
misioneros.
caníbales.
misionero y 1 caníbal.

Coste operador: 1

Búsqueda en el
Espacio de Estados

Concepto
• La resolución de un problema conesta representación pasa por
explorar el espacio de estados.
• Se parte desde el estado inicial evaluando cada paso hasta
encontrar un estado final
• En el caso peor explora todos los posibles caminos entre el
estado inicial del problema hasta llegar al estado final.
• El espacio problema es creado a medida que es explorado.

Grafos (1/3)
Un grafo viene dado por un conjunto de nodos

y un conjuntode arcos entre los nodos.
Grafo dirigido: grafo en el que (A,B) se
considera diferente de (B,A); ejemplo red
bayesiana.
En caso contrario es no dirigido.
Camino: sucesión de nodos tales que entre
dos de ellos consecutivos existe un arco.
 Grafo conexo: entre dos nodos cualesquiera
existe un camino.

Grafos (2/3)
En un grafo no dirigido cualquier camino cerrado

recibe el nombre de ciclo. Sino contiene ciclos se
denomina árbol (no dirigido).
Nodos: elementos en el espacio de estados que
representan situaciones válidas en el dominio. Es
decir, nodo y estados son sinónimos.
Expansión de un nodo: obtener todos sus
posibles sucesores en el grafo de búsqueda a
través de la aplicación de todos los operadores.

Grafos (3/3)
Nodo o estado cerrado: aquel que ya ha sido expandido.
Nodo oestado abierto: aquél en el que todavía queda

por aplicar algún operador.
Coste de un arco: es un valor numérico que refleja el
tiempo requerido para aplicar un operador a un estado
en el proceso de búsqueda.
Factor de ramificación: número medio de descendientes
de un nodo, o lo que es lo mismo, el número medio de
operadores aplicados a dicho camino.
Profundidad: longitud del camino más cortodesde el
estado inicial a una meta. O la longitud de secuencia
más corta de operadores que resuelven el problema.

Ejemplo
Supóngase que está en París sin un mapa y

no habla francés ¿Cómo llegar hasta la torre
Eiffel?.
Tomar aleatoriamente una calle
Seguir exhaustivamente cada calle de inicio a
fin
Usar nuestro conocimiento sobre la torre

Búsqueda a Ciegas
•
•
•
•
•
•
•
•

Algoritmo delmuseo británico.
Primero a lo ancho (breadth-first).
Primero en profundidad (depth-first).
Búsqueda en árboles y/o.
Búsqueda en sistemas de producción.
Búsqueda bidireccional.
Búsqueda por diferencias.
Búsqueda de soluciones múltiples.

Búsqueda Heurística
Búsqueda escalada (hill-climbing).
Búsqueda por el mejor nodo o algoritmo

A* (best-first).
Búsqueda heurística en árboles y/o o
algoritmoAO*.

Como realizar una búsqueda

Como realizar una búsqueda

Como realizar una búsqueda

Tipos de Búsqueda

Búsqueda a Ciegas (1/2)

Búsqueda a Ciegas (2/2)
Objetivos:
Encontrar el camino óptimo entre la
descripción del problema o estado inicial y el
estado meta.
A veces basta con devolver el estado meta y
no es necesario conocer todo el camino.
Características:
No dejar (a priori)ningún nodo sin explorar.
No explorar un nodo más de una vez.

Búsqueda en amplitud
Es aquél procedimiento de control en el que

se revisan todas las trayectorias de una
determinada longitud antes de crear una
trayectoria más larga.
 Es decir, no se genera ningún nodo de nivel
N hasta que no se hayan obtenido todos los
del nivel N-1.

Búsqueda en amplitud
1. Crear una lista de nodos llamada...