Tarea

3.8 Considere un espacio de estados donde el estado comienzo es el número 1 y la función sucesor para el estado n devuelve 2 estados, los números 2n y 2n + 1.

a) Dibuje el trozo del espacio deestados para los estados del 1 al 15.

[pic]

b) Supongamos que el estado objetivo es el 11. Enumere el orden en que serán visitados los nodos por la búsqueda primero en anchura, búsqueda primero enprofundidad con límite tres, y la búsqueda de profundidad iterativa.

Búsqueda primero en anchura: 1,2,3,4,5,6,7,8,9,10,11
Búsqueda primero en profundidad con límite tres:1,2,4,8,9,5,10,11
Búsqueda en profundidad iterativa: 1,2,4,8,9,5,10,11

c) Será apropiada la búsqueda bidireccional para este problema? Si es así, describa con detalle como trabajaría.

Unabúsqueda bidireccional es básicamente una búsqueda simultánea que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún puntointermedio.

Si en un problema el factor de ramificación b es el mismo en ambas direcciones, la búsqueda bidireccional puede ser muy útil. Si la solución está a profundidad d, entonces lasolución estará a O(2bd/2) = O(bd/2) pasos

O = función de profundidad
b = factor de ramificaciones
d = profundidad
En el siguiente problema es mejor utilizar la búsquedabidireccional realizando una búsqueda en profundidad que comience en el estado inicial, mientras que se desarrolla una búsqueda en amplitud que comienza desde el estado objetivo, cada uno realiza supropio recorrido hasta llegar al estado común (en este caso el nodo 8).

[pic]

d) ¿Qué es el factor de ramificación en cada dirección de Ia búsqueda bidireccional?

Es el número de nodos hijosque genera el algoritmo de búsqueda bidireccional en cada una de sus ramas.

e) ¿La respuesta (c) sugiere una nueva formulación del problema que permitiría resolver el problema de salir del...