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:

      V = Número de vértices del árbol.
      E = Número de aristas del árbol.

Función BUSCA-PRIMERO-ANCHURA(problema) //devuelve solución o fallo
     Nodo <- creaNodo(config inicial, problema, 0)
     SI Nodo contiene la config objetivo ENTONCES devuelve solución de Nodo
     Frontera <- cola solo con nodo
     Explorado <- conjunto vacío 

     REPETIR
        SI Frontera está vacía ENTONCES devolver fallo
        SACAR Nodo de Frontera
        METER Nodo en Explorado
        PARA CADA op en operaciones aplicables a la config del nodo HACER
             Hijo <- resultado de expandir Nodo con operador
             SI Hijo no está ni en Frontera ni en Explorado ENTONCES    
                SI Hijo contiene la config objetivo ENTONCES devolver solución hijo
             METER Hijo en Frontera

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:

     C*-> el coste de cualquier solución óptima.
     e -> el coste mínimo de cada acción.

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:

V = Número de vértices del árbol.
E = Número de aristas del árbol.

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)