Entregable Algoritmos de Búsqueda

1. ALGORITMOS DE BÚSQUEDA CIEGA

1.1. DEPTH-FIRST SEARCH

Si aplicamos el algoritmo de búsqueda Depth-First Search para buscar la solución, indicad: el paso a paso de la
ejecución del algoritmo, mostrando el nodo que está visitando, el valor actual de Vmax en cada paso (que irá
cambiando dependiendo de los nodos que ha visitado hasta el momento), y finalmente cuál es el camino
solución.

Respuesta

Se aplica el algoritmo de búsqueda (Depth First Search - DFS) en el grafo,

El objetivo es visitar los nodos en un camino que maximice el valor de Vmax, que representa la suma de los valores de los
nodos visitados hasta el momento. Vamos a asumir que la "solución" es el camino que maximiza Vmax.

A continuación, describiremos el proceso,

Pasos Estructura de datos

Inicio: Nodo a {a} Nodos visitados=a Vmax=2

Expandimos de a ⟶ b {ab, ac, ad} Nodos visitados= a, b Vmax=9

Expandimos b ⟶ e {abe, abf, ac, ad} Nodos visitados a, b, e Vmax=19

Expandimos e ⟶ como es un nodo hoja retornamos b,

Expandimos b ⟶ f {abf, ac, ad} Nodos visitados a, b, e, f Vmax= 14

Expandimos f ⟶ como es un nodo hoja retornamos a b.

Como b ya fue visitado retornamos a a y expandimos c.

Expandimos a ⟶ c {ac, ad} Nodos visitados a, b, e, f, c Vmax=10

Expandimos c ⟶ g {acg, ad} Nodos vitados a, b, e, f, c, g Vmax= 16

Expandimos g ⟶ …. k {acgk, ad} Nodos visitados a, b, e, f, c, g, k Vmax= 72

Con infinitos nodos debajo de g, sin un criterio de parada, el DFS continuaría indefinidamente. Suponiendo que no hay
nodos con Vmax= 72 en la parte infinita del árbol, el algoritmo eventualmente retrocedería a g, luego a c, y finalmente a.

Expandimos a ⟶ d {ad} Nodos visitados a, b, e, f, c, g, k, d Vmax=3

Expandimos d ⟶ h {adh, adhi} Nodos visitados a, b, e, f, c, g, k, d, h Vmax=3

Expandimos h ⟶ como es un nodo hoja retornamos d.

Expandimos d ⟶ i {adhi} Nodos visitados a, b, e, f, c, g, k, d, h, i Vmax= 6

Expandimos i ⟶ j {adij} Nodos visitados a, b, e, f, c, g, k, d, h, i j Vmax= 86

Finalmente, el camino solución es: a ⟶d ⟶ i ⟶ j Vmax=86

1.2. BREADTH-FIRST SEARCH

Si aplicamos el algoritmo de búsqueda Breadth-First Search para buscar la solución, indicad: el paso a paso de la
ejecución del algoritmo, mostrando el nodo que está visitando, el valor actual de Vmax en cada paso (que irá cambiando
dependiendo de los nodos que ha visitado hasta el momento), y finalmente cuál es el camino solución.

Respuesta

Se aplica el algoritmo de búsqueda (Breadth First Search - BFS) en el grafo,

El objetivo es visitar los nodos en un camino que maximice el valor de Vmax, que representa los valores de los nodos
visitados hasta el momento. Vamos a asumir que la "solución" es el camino que maximiza Vmax, teniendo en cuenta que
el método de búsqueda dará como resultado el camino más corto.

A continuación, describiremos el proceso,

Pasos Estructura de datos

Inicio: Nodo a

Visita a a {a} Nodos visitados=a Vmax=2

Expandimos de a ⟶ b {ab, ac, ad} Nodos visitados= a, b Vmax=7

Visita a b

Expandimos de a ⟶ c {ac, ad, abe, abf} Nodos visitados= a, b, c Vmax=8

Visita a c

Expandimos de a ⟶ d {ad, abe, abf, acg} Nodos visitados= a, b, c, d Vmax=8

Visita a d

Expandimos de b ⟶ e {abe, abf, acg, adh, adi} Nodos visitados= a, b, c, d, e Vmax=10

Visita a e

Expandimos de b ⟶ f {abf, acg, adh, adi} Nodos visitados= a, b, c, d, e, f Vmax=10

Visita a f

Expandimos de c ⟶ g {acg, adh, adi, acgk} Nodos visitados= a, b, c, d, e, f, g Vmax=10

Visita a g

Expandimos de d ⟶ h {adh, adi, acgk, adij} Nodos visitados= a, b, c, d, e, f, g, h Vmax=10

Visita a h

Expandimos de d ⟶i {adi, acgk} Nodos visitados= a, b, c, d, e, f, g, h, i Vmax=10

Visita a i

Expandimos de g ⟶ … k {acgk, adij} Nodos visitados= a, b, c, d, e, f, g, h, i, k Vmax=56

Teniendo en cuenta la información adicional dada sobre la representación de los puntos suspensivos de bajo de los nodos
g, y k. Para fines prácticos se realiza una suposición de finitud y se asume que los puntos suspensivos en la imagen
representan una simplificación o una representación conceptual de nodos adicionales, pero que, en la implementación
real del grafo, solo se consideran un número finito de nodos.

Por lo tanto, retornamos y continuamos con el algoritmo dejando como hipótesis que ningún nodo hijo de k tiene peso
mayor a 56, de no ser de estar forma el método BFS continuaría encolando nodos de manera infinita y el algoritmo una
condición de terminación natural.

Visita k

Expandimos i ⟶ j {adij} Nodos visitados= a, b, c, d, e, f, g, h, i, j, k

Vmax=80

Finalmente, el camino solución es: a ⟶d ⟶ i ⟶ j Vmax=80

 1.3. ITERATIVE DEEPENING SEARCH

Si aplicamos el algoritmo de búsqueda Iterative Deepening Search para buscar la solución, indicad: el paso a
paso de la ejecución del algoritmo, mostrando el nodo que está visitando, el valor actual de Vmax en cada paso
(que irá cambiando dependiendo de los nodos que ha visitado hasta el momento), y finalmente cuál es el camino
solución.

Solución

Profundidad =0

Inicio Nodo a (Vmax=2) {a}

Profundidad =1

Base nodo a (Vmax=2) {ab, ac,ad}

Hijos de a

Visita nodo b (Vmax=7)

Visita nodo c (Vmax=8)

Visita nodo d (Vmax= 8)

a⟶c

Profundidad =2

Base a, b, e , f {abe, abf, acg, adh, adi}

Visita nodo a (Vmax= 2)

Visita nodo b (Vmax=7)

DFS de b

Visita nodo e (Vmax=10)

Visita nodo f (Vmax=10)

Visita nodo c (Vmax=10)

DFS de c

Visita nodo g (Vmax=10)

DFS de d

Visita nodo d (Vmax=10)

Visita nodo h (Vmax=10)

Visita nodo i (Vmax=10)

a⟶ b ⟶ e

Profundidad 3 {adij}

Visita nodo a (Vmax=2)

Visita nodo d (Vmax=2)

Visita nodo i (Vmax= 3)

Visita nodo j (Vmax=80)

a⟶ d ⟶ i ⟶ j

Si el valor de 'j' es el máximo encontrado (Vmax=80), entonces el algoritmo concluye que 'j' es el nodo objetivo,
ya que los puntos suspensivos indican un número infinito de nodos más allá de 'k', por lo que no se puede
proceder más allá en la práctica.

2. ALGORITMOS DE BÚSQUEDA HEURÍSTICA

2.1. EJECUCIÓN– PASO A PASO

Teniendo en cuenta la heurística presentada para cada nodo del árbol. Mostrad paso a paso cual es la ejecución del
algoritmo A* del enemigo. Responded con todos los nodos que visita, qué jugador encuentra primero para atacar (nodo
objetivo) y cuál es el camino hasta este jugador.

Solución
Iniciamos recordando que el algoritmo A* toma conocimiento previo a través de heurísticas que
permite optimizar la ruta al nodo objetivo. Se toma como base f (n)=g(n)+ h(n) donde g(n) será el
costo para llegar al nodo destino (jugador) y h(n) es el costo estimado para ir al nodo n destino.
Al implementarlo en el espacio de búsqueda tendremos los siguientes pasos:
Inicio: Comienza en el nodo inicial, que es el nodo a
Nodos a evaluar: Añade el nodo inicial para ser evaluado.
Proceso: Mientras el conjunto de nodo a evaluar no esté vacío, hace lo siguiente:

 Selecciona el nodo con el menor valor de f(x) del conjunto de nodos a evaluar. Al principio, es solo el
nodo 'a'.
 Si el nodo seleccionado es un nodo objetivo (nodo con un jugador), entonces termina la búsqueda.

 Si no, mueve el nodo al conjunto cerrado (ya evaluado) y examina todos sus vecinos.

 Para cada vecino, si no está en el conjunto cerrado y no es infinito, calcula f(x) (si no está ya calculado) y
lo añade al conjunto a evaluar si no está ya en él o si el nuevo camino es mejor.

 Repite este proceso.

El algoritmo A* se ejecuta de la siguiente manera:

Inicio comienza en el nodo a. {a}
f(a)=0+2=2 Nodos vistados:a
Vecino cercanos b,c,d {ab, ac, ad}
Se evalúa el costo de cada nodo vecino.
Nodo b f(b)=1+ ∞ = ∞ (el nodo queda bloqueado, es demasiado costoso)
Nodo c f (c)= 1+6=7 Se añade para ser evaluado.
Nodo d f(d)= 1+3 =4 Se añade para ser evaluado.
Se elige el siguiente nodo, que por algorimo será aquel con menor f(x), en este caso es d. Así que visitamos a d.
Nodos visitados: a,d
Vecinos cercanos: g,h {dg, dh}
Se evalua el costo de cada vecino.
Nodo g, f(g)= 2+ 2 Se añade para ser evaluado.
Nodo h, f(h) = 2+∞ (El nodo queda bloqueado es demasiado costoso)
Se elige el siguiente nodo, que por algorimo será al que con mayor f(x), en este caso es g. Aunque podríamos
irnos por c, de nuevo revisamos el menor valor. Así que visitamos a g.
Vecinos cercanos: j {gj} Nodos visitados: a,d,g
Se evalua el costo de cada vecino.
Nodoj, f(j)=3+1=4 Se añade para ser evaluado.
Pero al ser j un nodo objetivo, el algoritmo A* se detendría aquí, ya que hemos encontrado a un jugador.
Vecinos cercanos: k {jk} Nodos visitados: a,d,g, j
Se evalua el costo de cada vecino.
Nodo k, f(k)=4+0=4 Se añade para ser evaluado.
Pero como hemos llegado un objetivo el algoritmo se detendría hay.
Resultado: El enemigo encuentra primero al jugador en el nodo j. El camino tomado es
a → d → g → j, es el camino más corto basado en la heurística dada y teniendo en cuenta los valores de
f(x) en cada nodo.

2.2. HEURÍSTICA Y CONDICIÓN

¿Al ver el jugador que encuentra primero el enemigo, creéis que el algoritmo se está ejecutando adecuadamente?
¿Porqué? Escribe la fórmula de la heurística que sigue el A* y explica cada parte de la fórmula. Además, muestra cual es
la condición que tiene que seguir la heurística para que la ejecución del A* sea la correcta.

Solución
El algoritmo A* es un algoritmo de búsqueda informada que se utiliza para encontrar caminos en un gráfico de
puntos o nodos. Busca el camino que tenga el menor coste total estimado hacia el objetivo. La fórmula de la
función de evaluación de A* es f(n) = g(n) + h(n), donde:
f(n) es el coste total estimado del nodo n al nodo objetivo.
g(n) es el coste del camino desde el nodo de inicio hasta el nodo n.
h(n) es la heurística, que estima el coste más bajo desde el nodo n hasta el objetivo.
Para que A* funcione correctamente, la heurística h(n) debe ser admisible, lo que significa que nunca
sobrestima el coste real de llegar al objetivo. Esto asegura que el algoritmo siempre encontrará la solución
óptima si existe. Además, si la heurística es consistente (o monótona), entonces A* es óptimo y completo,
significando que siempre encontrará la mejor solución posible si existe una, y siempre encontrará una solución.
Como el enemigo elige un nodo con un valor de f(n) más alto cuando hay otros nodos con un valor más bajo
disponible, entonces esto podría indicar un problema con la implementación del algoritmo o con la función
heurística. Para organizar el algoritmo se debe cambiar la heurística.
2.3. IDA*
Los programadores de la I.A. del enemigo han decidido probar con el IDA* en vez del A* como algoritmo de
búsqueda. Responded con todos los nodos que visita con el IDA*, qué jugador encuentra primero para atacar
(nodo objetivo) y cuál es el camino hasta este jugador. ¿En este caso, qué funciona mejor el A* o el IDA*?
¿Porqué?
El proceso de IDA* sería el siguiente:
Se inicia en f(a), que es 2.
Primera Iteración: Realizar una búsqueda en profundidad, visitando nodos hasta que f(n) exceda el límite
actual de 2. Con este límite, el único nodo que puede ser visitado es f, ya que tiene un valor de f(f)=2, y es un
nodo objetivo.
Si no hubiésemos encontrado un nodo objetivo, incrementaríamos el límite al mínimo f(n) que excedió el límite
actual y repetir la búsqueda. Pero dado que f es un nodo objetivo y su f(n) no excede el límite, la búsqueda se
detiene aquí.
En este caso particular, el IDA* encontraría el objetivo en el nodo f en la primera iteración sin visitar ningún
otro nodo porque el valor de f(f) no excede el límite y es un nodo objetivo con h(n)=0. Por lo tanto, el camino
sería simplemente desde a hasta f.
Comparando IDA* con A*, en este caso particular, IDA* parece ser muy eficiente, ya que encuentra un nodo
objetivo en la primera iteración sin necesidad de revisar los nodos. A* también habría encontrado este nodo
rápidamente, ya que también seleccionaría el nodo f como el mejor candidato para explorar después del nodo
inicial a, dado su bajo valor de f(n). La eficiencia comparativa entre A* e IDA* en este caso dependería de
factores adicionales como la implementación específica y las restricciones de memoria.
En un espacio de búsqueda pequeño con nodos objetivo claramente definidos, como este, ambas técnicas
pueden rendir de manera similar en términos de velocidad.
# 1. Se crea una lista de objetos vacía
L = []

# 2. Se añaden los nodos iniciales

initial_node = get_initial_node(tree)
if initial_node is None:
print("Error: There's no initial node!")
return None

L.append(initial_node)
i=1

while L:
print('----------------')
print(f'Iteration {i}')
print(f'L = {[node.name for node in L]}')

# 3. Escoger el primer nodo de la lista

n = L[0]
print(f'n is {n.name}')

# 4. ¿Es el nodo objetivo?

# Si: Parar y devolver el camino hasta el objetivo.
if n.is_goal:
print('-------Solution Found--------')
print(f'node {n.name} is goal!')
return n
 else:
print(f'node {n.name} is not goal')
print(f'remove {n.name} from L')
L.pop(0) # Elimina el nodo al principio de la lista
print(f'Inserting {[child.name for child in n.children]} at the end of L')

# 5. Añade los hijos del nodo eliminado al final de la lista.

L.extend(n.children)

# 6. Repetir el bucle hasta encontrar objetivo o hasta que no queden nodos en la lista.
i += 1

# Si sale del bucle, significa que no se ha encontrado una solución

print('-------Solution Not Found--------')
print('So sad...')
print('---------------------------------')

Cambios realizados
Paso 5: Anteriormente, los hijos se añadían al principio de la lista utilizando insert(0, child) para DFS, que
hace que el algoritmo explore el último nodo hijo añadido primero. En BFS, queremos explorar los nodos en el
orden en que fueron añadidos, por lo que en lugar de insertar al principio, simplemente extendemos la lista L
con los hijos del nodo actual usando L.extend(n.children), lo cual añade los hijos al final de la lista.