Resolución de Problemas con Búsquedas

1. Explica brevemente en qué consiste la formalización de un problema para ser resuelto mediante búsquedas:

La formalización de un problema consiste en definir los 4 elementos básicos para el planteamiento del mismo, es necesario tener un estado inicial para saber de dónde partir, es necesario conocer las posibles acciones que se pueden llevar a cabo, debe haber un objetivo y a su vez compararlo con otro objetivo para saber cuál es el mejor.

2. Describe brevemente cada uno de los siguientes elementos de la formalización de un problema:

a. Estado: Es una situación en el cual se encuentra algo.

b. Operadores: La acción que se va a tomar en términos de los estados que queremos alcanzar.

c. Estado objetivo: Cuando el agente logro el resultado esperado.

d. Espacio de estados: Un set de operadores que especifican la acción de cada estado.

e. Costo de ruta: Es la suma de los costos de las acciones individuales que se tomaron durante la solución del problema.

f. Prueba del objetivo: Es una descripción del estado para saber cómo terminó satisfactoriamente.

3. Explica en qué consiste el método “Generar y Probar” (generate and test). ¿Por qué este método es considerado exhaustivo?

Porque es un método que trata de probar cada una de las posibilidades para saber si es cierto o no, es un método de fuerza bruta.

4. Explica las diferencias entre los métodos de búsqueda en profundidad primero (DFS) y búsqueda en amplitud primero (BFS).

BFS primero expande todo y el DFS va de nodo por nodo y los expande hasta que no puede más, entonces regresa y busca en el nodo anterior, este último es como una búsqueda binaria.

5. Explica qué significa cada uno de estos términos en relación a los métodos de búsqueda:

a. Complejidad: Los recursos que tomara el resolver el problema, tiempo y espacio.

b. Completud: La estrategia para encontrar la solución.

c. Optimalidad: La estrategia para encontrar la mejor solución.

6. ¿Qué significa que un método de búsqueda sea no-monotonico?

Que no sigue la heurística y esto consiste en que no sigue el fenómeno como se esperaba, como se explica en el ejemplo la suma de los valores nunca disminuye y eso es algo esperado en el caso de que es no-monotonico indicaría lo contrario que en vez de incrementar los valores, estos disminuyen.

7. Explica brevemente los siguientes algoritmos:

a. DFS (Depth-first search): Se trata de un algoritmo de búsqueda utilizado comúnmente en la búsqueda de árboles o grafos que consiste en recorrer desde el nodo raíz hasta la primer hoja encontrada para después regresar y hacer lo mismo con las demás ramas.

b. BFS (Breadth-first search): Se trata de un algoritmo de búsqueda utilizado en las mismas circunstancias que consiste en recorrer los vecinos del nodo raíz y a su vez los vecinos de las siguientes ramas, así hasta encontrar el resultado.

c. Profundidad iterativa: Consiste en recorrer el árbol hasta cierta profundidad. Si no se encuentra el resultado deseado se puede incrementar el límite en la profundidad para continuar haciendo esto sucesivamente.