# Inteligencia artificial para videojuegos/Estrategias de búsqueda no informada

En informática, los métodos de búsqueda no informada o ciegas son estrategias de búsqueda en las cuales se evalúa el siguiente estado sin conocer a priori si este es mejor o peor que el anterior. No usan ninguna información que no pueda obtenerse de la definición del propio problema, tan sólo pueden expandir nodos, generando todos los hijos posibles, e irles haciendo la prueba objetivo a estos hijos. La única diferencia entre este tipo de estrategia estará en el orden que se van expandiendo los nodos.
Este tipo de búsqueda resulta útil para resolver problemas sencillos, si se tiene la capacidad computacional suficiente. Por otra parte, también se utiliza para hacer pruebas comparativas (benchmarking) con otras estrategias.

## Primero en anchura (BFS)

Consiste en expandir primero la raíz, luego sus hijos, luego los hijos de todos esos hijos...Es decir, hay que expandir al completo cada nivel de profundidad del árbol de búsqueda.
En el peor caso, su coste en cuanto a complejidad computacional y considerando árboles está en orden O(|V + E|) y en memoria en orden O(|V|). Siendo:

## Coste Uniforme (UCS)

Si todos los pasos cuestan lo mismo, el BFS es óptimo, pero si no, se puede modificar el algoritmo para que sea óptimo con cualquier coste. Es decir, uno por uno, expandir al completo cada ruta con cierto coste del árbol de búsqueda. En el caso peor la complejidad espacial y temporal es O(R$^{1+[C*/e]}$) Siendo:
En términos generales es considerado el mejor algoritmo de búsqueda que no utiliza heurísticas.
Nota: UCS puede transformarse en BFS si, por ejemplo, a todas las aristas se les asigna el valor 1.

## Primero en Profundidad (DFS)

Consiste en expandir siempre el nodo más profundo de la frontera. Lo primero es ir expandiendo hacia abajo hasta llegar a los niveles más profundos del árbol, después, subir lo justo para seguir expandiendo todos los hijos de los nodos profundos que todavía queden por explorar.
Al igual que BFS, en el peor caso de DFS, su coste en cuanto a complejidad computacional y considerando árboles está en orden O(|V + E|) y en memoria en orden O(|V|). Siendo:
Esta estrategia no es óptima, y tampoco será completa si hay rutas redundantes, si el espacio de búsqueda es infinito, puede que el algoritmo profundice eternamente. Lo interesante está en su baja complejidad espacial, sobre todo en árboles y puede reducir aún más el gasto de memoria. Se conoce como búsqueda con vuelta atrás, sólo genera 1 hijo a la vez, y cada nodo parcialmente expandido recuerda lo que le falta por expandir. Para ahorrar aún más tiempo y memoria, no se hacen copias de tipo configuración, sino que se modifica todo el rato una misma configuración (estas modificaciones tienen que poder deshacerse).
Por otra parte, frente a su alta eficacia en memoria, el algoritmo de vuelta atrás es considerado un algoritmo de fuerza bruta, por lo que su coste computacional no es óptimo y no es viable frente a problemas más complicados.
Profundidad limitada
Para evitar posibles “cuelgues” de primero en profundidad, se añade un límite L. Esta estrategia es completa siempre que el objetivo no esté a mayor profundidad, pero no es óptima si el límite es mayor que la profundidad del objetivo. A veces, con el problema se puede deducir el diámetro del espacio de búsqueda, un candidato a límite razonable
Profundización iterativa
Surge de combinar una estrategia como la de profundidad limitada con una técnica para encontrar el mejor límite de profundidad. (Busca con límite 0, límite 1, límite 2....) Combina la baja complejidad espacial del DFS con la completitud y optimalidad (si se dan las condiciones) del BFS. Es la estrategia no informada más utilizada cuando el espacio de búsqueda es grande y no se conoce la profundidad de la solución.

## Bidireccional

Consiste en hacer 2 búsquedas simultáneas, una desde la configuración inicial y otra hacia atrás desde el objetivo, confiando en que se encuentro en medio, terminando así la búsqueda. Puede ser muy rápido, pero lo malo es que ocupa mucho y hay que expandir padres en vez de hijos.
Por otra parte, no todos los problemas de búsqueda básicos se pueden plantear de forma sencilla como problemas de búsqueda bidireccionales, muchas veces porque no es sencillo proporcionar la función de transición inversa.

## En definitiva

Aquí vemos una tabla donde podemos comparar las distintas estrategias no informadas.
| CRITERIOS | BFS | Coste Uniforme | DFS | Profundidad limitada | Profundidad iterativa |
| Completitud | Sí | Sí | No | No | Sí |
| Optimalidad | Sí | Sí | No | No | Sí |
| Complejidad temporal | O(R$^P$) | O(R$^{1+[C*/e]}$) | O(R$^M$) | O(R$^L$) | O(R$^P$) |
| Complejidad espacial | O(R$^P$) | O(R$^{1+[C*/e]}$) | O(R*M) | O(R*L) | O(R*P) |