03 - Resolución de problemas en la IA Flashcards
¿Que es un problema?
En una definicion generica podemos decir que una entidad tiene un problema cuando desea algo y no sabe como obtenerlo, es decir, no conoce los pasos o secuencia de acciones que debe ejecutar para llegar a su objetivo.
¿Como se define un problema formalmente?
Se hace especificando una terna de elementos:
E - estado inicial o punto de partida
O - operaciones o acciones validas
M - meta o punto final para terminar el problema
P = (E, O, M)
¿Qué es un árbol de espacio de estados?
A partir de una definición formal se puede construir el árbol de espacio de estados.
Ejemplo: mapa de ruta para el recorrido de un ciclista que quiere ir de A a F.
E = ciudad A
M = ciudad F
O = {AaB, AaC, AaD, BaA, BaC, BaE, CaA, CaB, CaD, CaE, CaF, DaA, DaC, EaB, EaC, EaF, FaC, FaE}
*en la definicion del problema se incluyen todas las rutas, aunque tengan los dos sentidos ej. AaB y BaA
Luego se representa el árbol sin incluir las acciones que te hacen volver a un nivel anterior.
¿Qué son los callejones sin salida en un árbol?
Son los nodos hojas que no coinciden con la meta y deben estar punteados.
¿Cuáles son los distintos tipos de búsquedas que se usan para construir los árboles?
Búsqueda ciega. (en profundidad o en amplitud)
Búsqueda informada (Acenso en colina, búsqueda en haz, primero el mejor)
Explique como funciona la búsqueda profunda
1- Se parte del estado inicial, nodo raíz nivel cero.
2- Se genera los nodos del primer nivel: B, C y D.
3- Como ninguno es la meta, la búsqueda debe continuar.
4- Se selecciona el nodo ubicado mas a la iz. de árbol para generar el nivel 2 (en el ej. C)
5- Dado que el nivel 2 tampoco coincide con el nodo meta, la búsqueda continua.
6. Se genera el siguiente nivel (3) con dos nodos D y E
7. Coo ningun es la meta, se continua
8. El modulo mas a la iz. llego a un callejon sin salida, por lo tanto se pasa al siguiente nodo.
9. …
Explique como funciona la búsqueda en amplitud
1- Se parte del estado inicial, nodo raíz, nivel 0.
2- Se generan los niveles siguientes de iz a der.
3- Si la meta no se encuentra, se pasa a expandir todos los nodos de iz a der.
4- Si no se encuentra la meta en el nivel, se expande el siguiente nivel de iz a der, etc.
Explique como funciona la búsqueda ascenso en colina
1- Se parte del estado inicial
2- Para bajar de nivel se fija en el mejor valor indicado en la información adicional
3- Para el problema del ciclista, serian la cantidad de horas, en linea recta, desde el destino hasta las distintas ciudades.
Explique como funciona la búsqueda en haz
- Se define un parámetro W que es el haz de búsqueda
- En todo momento el método mantiene w ramas simultáneas de exploración.
1- Se parte del nodo raíz y se expande el primer nivel.
2- Si la meta no se encuentra, se pasa a expandir w nodos valiendonos de la información adicional.
3. Si la meta no se encuentra en el nivel 2, se procede a repetir el paso 2) abrir w nodos teniendo en cuenta la info. adicional, etc.
Explique como funciona la búsqueda primero el mejor
- Similar a ascenso en colina
- Cuando debe generar un nuevo nivel se baja por el nodo que la info adicional indique como mas prometedor, sin considerar el nivel en que se encuentre.
-Si hay mas de 1 nodo elegible, selecciona aquel que se encuentra en la rama mas a la izquierda del árbol.
¿Cuales son las distintas formas de representar el conocimiento?
Redes semánticas, guiones, marcos y reglas de producción.
