Estrategias de búsqueda en ia

En el campo de la inteligencia artificial, las estrategias de búsqueda juegan un papel fundamental en la resolución de problemas y la toma de decisiones. Estas estrategias permiten a los agentes racionales encontrar la mejor solución posible para un problema dado.

¿Por qué son importantes las estrategias de búsqueda?

Imaginemos un juego simple como el Tic-Tac-Toe, que tiene 362880 (9!) estados posibles diferentes, y solo unos pocos de ellos nos llevan a la victoria. De manera similar, el famoso problema de los Misioneros y Caníbales también tiene muchos estados posibles. ¿Necesito mencionar el ajedrez? Lmao.

Las estrategias de búsqueda son métodos estructurados para resolver problemas. Los agentes racionales o de resolución de problemas en IA suelen utilizar estas estrategias de búsqueda para encontrar la mejor solución posible para un problema dado.

Las estrategias de búsqueda se clasifican en dos categorías principales:

• Búsqueda no informada: Estas estrategias no tienen ningún conocimiento previo más allá de lo que está definido en las restricciones del problema. Funcionan investigando ciegamente los diferentes estados y encontrando el camino hacia la solución.
• Búsqueda informada: Estas estrategias utilizan información adicional para guiar la búsqueda hacia la solución óptima. Se basan en heurísticas y conocimiento específico del dominio para tomar decisiones más informadas.

Búsqueda no informada

Las estrategias de búsqueda no informada funcionan utilizando un enfoque de fuerza bruta. No tienen ningún conocimiento más allá de lo que está definido en las restricciones del problema. Simplemente exploran ciegamente los diferentes estados y encuentran el camino hacia la solución.

Las estrategias de búsqueda no informada se evalúan en función de los siguientes parámetros:

• Completitud: Si una estrategia de búsqueda puede identificar el camino hacia la meta del agente, entonces podemos llamarla completa.
• Complejidad temporal: Medida del tiempo requerido para encontrar la solución.
• Complejidad espacial: Almacenamiento máximo necesario en condiciones de peor caso.
• Solución óptima: Se refiere a una solución que tiene el costo más bajo posible.

Búsqueda en anchura (Breadth-first Search)

El método de búsqueda más popular para recorrer un árbol o un grafo es la búsqueda en anchura, que sigue el método de recorrido por niveles. El algoritmo de búsqueda en anchura realiza búsquedas nivel por nivel en un árbol o grafo. Comienza su búsqueda en el nodo raíz del árbol y expande todos los nodos hijos del nivel actual antes de pasar a los nodos del siguiente nivel. Se utiliza una cola para implementar BFS.

BFS promete encontrar una solución si existe. Sin embargo, esto aumenta la complejidad temporal y espacial cuando los estados objetivo están situados muy profundamente en un árbol o grafo.

Búsqueda en profundidad (Depth-first Search)

Un enfoque recursivo para explorar un árbol o grafo se conoce como búsqueda en profundidad. La búsqueda en profundidad comienza en el nodo raíz, recorre cada camino hasta la profundidad del árbol expandiendo uno de sus hijos, y luego pasa al siguiente camino. Se utiliza una pila para implementar DFS.

DFS solo necesita almacenar una pila de los nodos en el camino desde el nodo raíz hasta el nodo actual, por lo que utiliza relativamente poca memoria en comparación con otras estrategias. Sin embargo, como DFS va hacia las profundidades primero, a veces entra en un bucle infinito. Por lo tanto, DFS no garantiza una solución completa.

Búsqueda de costo uniforme (Uniform-cost Search)

La búsqueda de costo uniforme se utiliza cuando los grafos tienen vértices ponderados. Ayuda a encontrar la meta de una manera óptima para un agente basado en utilidad. La idea es expandir el nodo más barato en cada momento, manteniendo una frontera, es decir, una cola de prioridad ordenada por el costo del camino (los estados más bajos tienen mayor prioridad).

Se puede resolver cualquier grafo o árbol que requiera el costo óptimo con esta estrategia. A veces, esta estrategia se pierde en un bucle infinito, ya que se enfoca únicamente en el costo del camino.

Búsqueda con límite de profundidad (Depth-limited Search)

La búsqueda con límite de profundidad es similar a la búsqueda en profundidad, pero se establece un límite de profundidad predeterminado (por ejemplo, l). Los nodos por debajo de la profundidad l se consideran como si no tuvieran sucesores, es decir, nodos hoja. Esto nos ayuda a resolver el problema de la ruta infinita de DFS. Sin embargo, esta estrategia tampoco garantiza una solución completa, ya que puede fallar si nuestro estado objetivo se encuentra en uno de los niveles por debajo de l.

La búsqueda con límite de profundidad se mueve de manera recursiva para recorrer la profundidad del grafo hasta que se alcance el límite. Si se alcanza el límite, se corta y retrocede hacia los otros nodos para buscar.

Búsqueda en profundidad con aumento iterativo (Iterative deepening depth-first search)

Esta es una de las estrategias más utilizadas, ya que busca combinar los beneficios de DFS y BFS. Es beneficioso en casos en los que el espacio de búsqueda es demasiado grande y la profundidad de la solución es desconocida. Comienza con un límite de profundidad de 0 en el árbol y explora todos sus nodos antes de aumentar el límite en 1 cada vez. Esto se repite hasta que se encuentre una de las metas.

Al igual que DFS, sus requisitos de memoria son modestos. Al igual que BFS, promete una solución completa y óptima cuando el costo del camino es una función no decreciente de la profundidad del nodo.

Para un grafo o árbol con un factor de ramificación de 10 y una profundidad de 5, la búsqueda en anchura recorre 111110 nodos en el peor de los casos. Al mismo tiempo, la búsqueda en profundidad con aumento iterativo recorre 123450 nodos.

Búsqueda bidireccional (Bidirectional Search)

La búsqueda bidireccional es una búsqueda en dos direcciones, es decir, una búsqueda hacia adelante desde el estado inicial y otra búsqueda hacia atrás desde el estado objetivo. Se espera que las dos búsquedas se encuentren en algún punto intermedio de uno de los estados.

La idea de usar esta búsqueda es que b^(d/2) + b^(d/2) es mucho menor que b^d. Se reemplaza la prueba de objetivo y se determina si las fronteras de las dos búsquedas se intersectan, si lo hacen, se ha encontrado una solución. Una vista esquemática de una búsqueda bidireccional está a punto de tener éxito cuando una rama desde el nodo de inicio se encuentra con una rama desde el nodo objetivo.

El cuadro de comparación anterior compara las diferentes estrategias de búsqueda no informada en función de los 4 parámetros mencionados anteriormente. Esto ayuda a comprender y elegir correctamente la estrategia adecuada para nuestro agente y el problema que estamos abordando. Con base en los requisitos y expectativas del agente, podemos elegir una estrategia y trabajar en consecuencia.

¿Y si te dijera que podríamos explorar, experimentar y utilizar heurísticas para obtener mejores estrategias? Veamos en el próximo artículo.

Si quieres conocer otras notas parecidas a Estrategias de búsqueda en ia puedes visitar la categoría Inteligencia.