ejercicios de busqueda

I

ESTRATEGIAS DE BÚSQUEDA
El siguiente grafo representa el espacio de estados sobre el cual deberás aplicar
distintas estrategias de búsqueda. El estado inicial es S y el estado objetivo es G.El
coste de los operadores viene anotado junto a los arcos dirigidos (que son
bidireccionales). Los valores estimados para los estados por una función heurística h’ se
encuentran junto a losvértices

Estudia si esta heurística es admisible. Explica tu respuesta

Para cada una de las estrategias de búsqueda indicadas, escribe una lista ordenada
de nodos (nombre del estado y coste del camino:p.ej. S0, A3...) que se corresponda con
la secuencia de nodos expandidos por la estrategia de búsqueda y el camino a la
solución, si existe. Cuando dos nodos tengan las mismas características porel criterio
de selección que se esté usando, haz la selección por orden alfabético (generación de
hijos por orden alfabético).
1.

Búsqueda primero en profundidad en los siguientes supuestos:1.1.

No hay control de ciclos de ningún tipo
• Expandidos:
• Camino a la solución:

1.2.

El control de ciclos se limita a los visitados en la rama actual
• Expandidos:

• Camino a lasolución:
1.3.

El control de ciclos incluye todos los expandidos y los pendientes de visitar
• Expandidos:
• Camino a la solución:

2.

Búsqueda primero en anchura, limitándose el control de ciclosa la rama actual
• Expandidos:
• Camino a la solución:

3.

Búsqueda voraz
• Expandidos:
• Camino a la solución:

En el laberinto de la figura, los sucesores de una casilla
incluyen lascasillas que se encuentran a su izquierda, derecha,
arriba y abajo (se debe respetar este orden) salvo que no se
pueda pasar a través de la barrera central. Por ejemplo, los
sucesores de M son N, D yG. El problema a resolver es
encontrar un camino desde S hasta G.
Utilizando como heurística la distancia Manhattan, resuelve el
problema utilizando las siguientes estrategias de búsqueda:
1....