🤖 Inteligencia artificial

1. En un problema de búsqueda con factor de ramificación b, donde la solución más superficial se localiza en la profundidad d, ¿cuál es la complejidad en tiempo y en memoria de la búsqueda en amplitud (BFS)?

1. O(b·d), porque la memoria requerida crece de forma lineal con la profundidad
2. O(b^d), porque en el peor caso se generan todos los nodos hasta ese nivel del árbol
3. O(b·m), donde m es la profundidad máxima del árbol, sin relación con d
4. O(b^m), donde m es la profundidad máxima, en lugar de la profundidad de la solución

BFS tiene complejidad O(b^d) en tiempo y memoria porque, en el peor caso, debe generar todos los nodos hasta la profundidad d antes de hallar la meta; O(b·d) corresponde a IDDFS y O(b·m) a DFS. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.1)

2. En un árbol de búsqueda con factor de ramificación b = 3, la meta se localiza en el nivel d = 4. En el peor caso, ¿cuántos nodos existen en ese nivel del árbol, es decir, cuántos nodos como máximo debe generar la búsqueda en amplitud (BFS) en ese nivel antes de garantizar hallar la meta?

1. 12 nodos (3×4), porque el número de nodos crece linealmente con la profundidad y el factor de ramificación
2. 1.33 nodos (4/3), porque la profundidad se divide entre el factor de ramificación en cada nivel
3. 81 nodos (3^4), porque el número de nodos por nivel crece exponencialmente con la profundidad
4. 64 nodos (4^3), porque la profundidad determina la base y el factor de ramificación el exponente

El número de nodos en el nivel d es b^d = 3^4 = 81, reflejo directo de la complejidad O(b^d) de BFS; las demás opciones aplican una fórmula lineal, invertida o con base y exponente intercambiados. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.1)

3. Un espacio de estados contiene una rama de profundidad infinita que no conduce a ninguna meta, además de otras ramas finitas donde sí existe una meta. Si se aplica una búsqueda en profundidad (DFS) sin límite de profundidad, ¿qué comportamiento es característico del algoritmo?

1. Expande los nodos en orden creciente de costo de ruta g(n), por lo que evita descender por la rama infinita
2. Explora primero todas las ramas de menor profundidad antes de descender por la rama infinita, por lo que localiza la meta antes de internarse en ella
3. Puede quedar atrapada siguiendo la rama infinita y nunca llegar a explorar las ramas finitas donde está la meta
4. Detiene automáticamente su ejecución en cuanto detecta que una rama no tiene límite de profundidad definido

DFS no es completa en espacios infinitos: puede internarse indefinidamente en una rama sin meta y nunca retroceder a explorar otras ramas; la primera opción describe el comportamiento de la búsqueda de costo uniforme y la segunda el de la búsqueda en amplitud (BFS). (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.3)

4. La búsqueda de costo uniforme garantiza encontrar la solución de menor costo total siempre que se cumpla una condición sobre los costos de los pasos del problema. ¿Cuál es esa condición?

1. Que exista una heurística admisible que acote el costo restante hasta la meta
2. Que todos los costos de los pasos sean no negativos
3. Que todos los costos de los pasos sean iguales entre sí
4. Que el factor de ramificación sea finito y constante en toda la búsqueda

La búsqueda de costo uniforme, equivalente al algoritmo de Dijkstra, es óptima cuando los costos de los pasos son no negativos; la condición de costos iguales corresponde en cambio a la optimalidad de BFS. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.2)

5. En un grafo de estados existen tres rutas parciales hacia la meta con costos acumulados g(n) de 12, 9 y 15 unidades, respectivamente. Según el criterio de expansión de la búsqueda de costo uniforme, ¿cuál de esas rutas se expande primero?

1. La ruta con costo acumulado de 15, porque la búsqueda de costo uniforme prioriza descartar primero los caminos más costosos
2. La ruta con costo acumulado de 12, por ser el valor intermedio entre las tres opciones
3. Las tres rutas al mismo tiempo, porque la búsqueda de costo uniforme expande por niveles de profundidad
4. La ruta con costo acumulado de 9, por tener el menor costo de ruta g(n) entre las tres opciones

La búsqueda de costo uniforme siempre expande el nodo de la frontera con menor g(n); entre 12, 9 y 15, el menor valor es 9. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.2)

6. En un árbol de búsqueda con factor de ramificación b = 10, la solución más superficial se localiza en la profundidad d = 5. Al aplicar una búsqueda en profundidad iterativa (IDDFS), ¿cuál es, en orden de magnitud, el número máximo de nodos que deben mantenerse en memoria en un momento dado?

1. Aproximadamente 9,765,625 nodos, del orden de d^b, un valor incluso mayor que en la búsqueda en amplitud
2. Aproximadamente 100,000 nodos, del orden de b^d, igual que en la búsqueda en amplitud
3. Aproximadamente 2 nodos, del orden de b/d, porque la profundidad reduce proporcionalmente la memoria requerida
4. Aproximadamente 50 nodos, del orden de b·d, porque IDDFS conserva la eficiencia de memoria lineal de DFS

IDDFS mantiene en memoria solo el camino actual y sus hermanos no expandidos, del orden de b·d = 10×5 = 50 nodos, aunque su complejidad en tiempo sí sea O(b^d) como en BFS. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.5)

7. Un ingeniero debe resolver un problema de planeación de rutas donde todos los caminos entre ciudades tienen el mismo costo de transición, se desconoce a qué profundidad se encuentra la solución, y el espacio de estados es demasiado grande para almacenar toda la frontera en memoria. ¿Cuál estrategia de búsqueda no informada es la más adecuada para este caso?

1. Búsqueda de costo uniforme, porque es la estrategia no informada más adecuada cuando los costos de los pasos son idénticos entre sí
2. Búsqueda en amplitud (BFS), porque garantiza optimalidad y resulta la opción más eficiente en memoria para espacios de estados grandes
3. Búsqueda en profundidad iterativa (IDDFS), porque combina la completitud y optimalidad de BFS con el bajo consumo de memoria de DFS
4. Búsqueda en profundidad (DFS) simple, porque su bajo consumo de memoria garantiza encontrar la solución de menor costo total

IDDFS es la opción preferida cuando la profundidad de la solución es desconocida y el espacio de estados es grande, pues combina la completitud y optimalidad de BFS con el consumo de memoria lineal de DFS; BFS y costo uniforme, aunque también óptimas aquí, no resuelven el problema de memoria. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.5)

8. ¿Qué característica distingue a la búsqueda en profundidad iterativa (IDDFS) de la búsqueda en profundidad (DFS) simple?

1. IDDFS utiliza una función heurística para decidir qué rama explorar primero en cada iteración
2. IDDFS mantiene en memoria todos los nodos de la frontera, igual que la búsqueda en amplitud
3. IDDFS explora los nodos en orden de menor costo acumulado, en lugar de seguir un único camino hasta el final
4. IDDFS repite la búsqueda en profundidad con límites de profundidad crecientes, lo que la hace completa y óptima cuando los costos de los pasos son iguales

IDDFS ejecuta sucesivas búsquedas en profundidad con un límite creciente en cada iteración, obteniendo así la completitud y optimalidad de BFS sin abandonar el bajo consumo de memoria de DFS. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.5)

9. ¿Cuál de las siguientes afirmaciones sobre la búsqueda en amplitud (BFS) NO es correcta?

1. Su complejidad en tiempo y en memoria es del orden de b^d, donde d es la profundidad de la solución más superficial
2. Es óptima incluso cuando los costos de los pasos son distintos entre sí, siempre que todos sean positivos
3. Expande los nodos en el orden en que fueron generados, mediante una estructura de cola (FIFO)
4. Es completa: siempre encuentra una solución si esta existe en un espacio de estados finito

BFS solo es óptima cuando todos los costos de los pasos son iguales entre sí; con costos positivos pero distintos puede devolver una solución no óptima, condición que sí garantiza la búsqueda de costo uniforme. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.1)

10. Una base de conocimiento contiene la sentencia 'Si llueve, entonces el suelo está mojado' y el hecho 'Llueve'. ¿Qué regla de inferencia permite derivar la conclusión 'El suelo está mojado'?

1. La regla de resolución
2. El silogismo disyuntivo
3. El Modus Ponens
4. El Modus Tollens

Modus Ponens permite inferir β a partir de la implicación α → β y del antecedente α; en este caso α es 'Llueve' y β es 'El suelo está mojado'. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 7.5)

11. Dada la implicación 'Si un algoritmo es NP-completo, entonces pertenece a NP' y el hecho 'Este algoritmo NO pertenece a NP', ¿qué conclusión puede inferirse válidamente mediante Modus Tollens?

1. Que el algoritmo pertenece a NP, porque se niega el antecedente de la implicación
2. Que el algoritmo es NP-completo, porque se conoce el consecuente de la implicación
3. No puede inferirse nada, porque Modus Tollens requiere conocer primero el valor de verdad del antecedente
4. Que el algoritmo no es NP-completo, porque se niega el consecuente de la implicación

Modus Tollens infiere ¬α a partir de α → β y ¬β; al negar 'pertenece a NP' se concluye válidamente que el algoritmo no es NP-completo. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 7.5)

12. ¿Qué forma deben tener las sentencias de una base de conocimiento para poder aplicarles la regla de inferencia de resolución?

1. Forma de Horn, en la que cada cláusula contiene como máximo un literal positivo
2. Forma normal conjuntiva (FNC), es decir, una conjunción de cláusulas disyuntivas
3. Forma normal disyuntiva (FND), es decir, una disyunción de cláusulas conjuntivas
4. Forma prenexa, con todos los cuantificadores agrupados al inicio de la sentencia

La resolución requiere que las sentencias estén en forma normal conjuntiva (FNC), una conjunción de cláusulas disyuntivas de literales; la forma de Horn es un caso particular más restrictivo, no el requisito general. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., caps. 7.5 y 9.5)

13. En una demostración por refutación mediante resolución, ¿qué indica que el conjunto de cláusulas original es insatisfacible?

1. La obtención de una cláusula idéntica a la sentencia que se desea refutar
2. La imposibilidad de generar nuevas cláusulas después de un número finito de pasos, sin llegar a ninguna conclusión
3. La derivación de una cláusula que contiene únicamente literales positivos
4. La derivación de la cláusula vacía a partir del conjunto de cláusulas

La resolución es refutacionalmente completa: si un conjunto de cláusulas es insatisfacible, siempre es posible derivar de él la cláusula vacía. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., caps. 7.5 y 9.5)

14. Para demostrar mediante resolución que una base de conocimiento KB implica lógicamente una sentencia β (KB ⊨ β), ¿cuál es el procedimiento correcto?

1. Convertir β a forma normal conjuntiva y verificar que sea una tautología, sin modificar la base de conocimiento
2. Agregar la negación de β a la base de conocimiento, convertir todo a forma normal conjuntiva y aplicar resolución hasta derivar la cláusula vacía
3. Eliminar de la base de conocimiento las cláusulas que no comparten literales con β antes de aplicar resolución
4. Agregar β directamente a la base de conocimiento y aplicar Modus Ponens hasta derivar una contradicción

La resolución demuestra KB ⊨ β por refutación: se añade ¬β a KB, se convierte todo a FNC y se busca derivar la cláusula vacía, lo que confirma que KB ∧ ¬β es insatisfacible. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 7.5)

15. En la arquitectura clásica de un sistema basado en conocimiento, ¿qué componente aplica las reglas de inferencia sobre los hechos almacenados para derivar nuevas conclusiones?

1. El módulo de adquisición de conocimiento, que incorpora nuevas reglas proporcionadas por el experto humano
2. La base de hechos (working memory), que únicamente almacena los datos del problema actual
3. El motor de inferencia (inference engine)
4. La interfaz de usuario, que traduce las consultas del usuario a un lenguaje formal

El motor de inferencia es el componente que aplica las reglas de la base de conocimiento sobre los hechos disponibles para derivar nuevas conclusiones; la base de hechos solo almacena datos, sin razonar sobre ellos. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 7 (arquitectura de sistemas basados en conocimiento))

16. Un sistema experto médico parte de los síntomas observados en un paciente y aplica reglas hacia adelante hasta derivar un posible diagnóstico. ¿Qué estrategia de razonamiento está utilizando?

1. Resolución por refutación, que niega la conclusión deseada y busca derivar una contradicción
2. Encadenamiento hacia atrás (backward chaining), dirigido por una hipótesis de meta que se busca confirmar
3. Búsqueda de costo uniforme sobre el espacio de posibles diagnósticos
4. Encadenamiento hacia adelante (forward chaining), dirigido por los datos disponibles

El encadenamiento hacia adelante parte de los hechos conocidos y aplica reglas hasta derivar nuevas conclusiones, a diferencia del encadenamiento hacia atrás, que parte de una hipótesis de meta. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 9.4)

17. Una base de conocimiento no contiene ninguna sentencia que afirme que 'Juan es programador'. Bajo la suposición de mundo cerrado (closed-world assumption), ¿qué se concluye acerca de esa proposición?

1. Que la base de conocimiento es inconsistente, porque toda proposición debe estar representada explícitamente
2. Que 'Juan es programador' se considera falsa, porque no aparece explícitamente como verdadera en la base de conocimiento
3. Que la proposición permanece indefinida hasta que se agregue explícitamente a la base de conocimiento
4. Que 'Juan es programador' se considera verdadera, porque no existe evidencia que la contradiga

Bajo la suposición de mundo cerrado, toda proposición que no se conoce explícitamente como verdadera se asume falsa; esto contrasta con la suposición de mundo abierto, donde la proposición quedaría indefinida. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 9 (programación lógica y negación como fallo))

18. En el marco del aprendizaje por concepto (concept learning), ¿cómo se define formalmente la tarea de aprendizaje?

1. Como la búsqueda de la hipótesis con menor costo de ruta g(n) dentro del espacio de hipótesis
2. Como la construcción de un árbol de decisión que clasifique los ejemplos en más de dos categorías
3. Como la inferencia de una función booleana c: X → {0,1} a partir de ejemplos de entrenamiento de su entrada y salida
4. Como la estimación de una función de valores continuos que minimiza el error cuadrático medio sobre los ejemplos

El aprendizaje de conceptos se define como la inferencia de una función objetivo booleana c: X → {0,1} a partir de ejemplos de entrenamiento etiquetados como positivos o negativos. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.1)

19. ¿Qué hace el algoritmo Find-S al recorrer los ejemplos de entrenamiento?

1. Mantiene simultáneamente las fronteras general y específica del espacio de versiones, actualizándolas con cada ejemplo
2. Busca la hipótesis más general del espacio de hipótesis que sea consistente con los ejemplos negativos, ignorando los positivos
3. Descarta cualquier hipótesis que sea consistente con más de un ejemplo positivo, para evitar el sobreajuste
4. Busca la hipótesis más específica del espacio de hipótesis que sea consistente con todos los ejemplos positivos, ignorando los negativos

Find-S recorre únicamente los ejemplos positivos y va generalizando la hipótesis más específica posible que los cubra, ignorando por completo los ejemplos negativos. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.4)

20. Durante la ejecución del algoritmo Find-S se procesa un nuevo ejemplo de entrenamiento etiquetado como NEGATIVO. ¿Qué acción realiza el algoritmo con este ejemplo?

1. Se reinicia la hipótesis a la más específica posible (∅) y se reprocesan todos los ejemplos positivos anteriores
2. Se especializa la hipótesis actual agregando una restricción que excluya explícitamente ese ejemplo negativo
3. Se generaliza la hipótesis actual para dejar de cubrir ese ejemplo negativo, sustituyendo un atributo específico por el símbolo '?'
4. Se descarta el ejemplo sin modificar la hipótesis actual, ya que Find-S solo aprende a partir de ejemplos positivos

Find-S ignora los ejemplos negativos por completo; ajustar la frontera G para excluirlos explícitamente es, en cambio, lo que hace el algoritmo Candidate-Elimination. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.4)

21. El algoritmo Candidate-Elimination representa el conjunto de todas las hipótesis consistentes con los ejemplos de entrenamiento observados hasta el momento. ¿Cómo se conoce a este conjunto y mediante qué fronteras se delimita?

1. Conjunto de entrenamiento aumentado, delimitado por los ejemplos positivos y los ejemplos negativos observados
2. Árbol de búsqueda de hipótesis, delimitado por la profundidad máxima m y el factor de ramificación b
3. Espacio de versiones (version space), delimitado por la frontera general G y la frontera específica S
4. Espacio de hipótesis completo, delimitado por el conjunto de todos los atributos posibles y sus valores

El espacio de versiones es el subconjunto de hipótesis consistentes con los ejemplos observados, representado de forma compacta mediante las fronteras G (más general) y S (más específica). (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, caps. 2.4 y 2.5)

22. ¿Qué establece la hipótesis del aprendizaje inductivo (inductive learning hypothesis)?

1. Que un algoritmo de aprendizaje converge a una única hipótesis si el conjunto de entrenamiento contiene al menos un ejemplo positivo y uno negativo
2. Que toda hipótesis consistente con los ejemplos de entrenamiento es necesariamente la función objetivo verdadera
3. Que el tamaño del espacio de hipótesis debe ser mayor que el número de ejemplos de entrenamiento para garantizar el aprendizaje
4. Que cualquier hipótesis que aproxime bien la función objetivo sobre un conjunto de entrenamiento suficientemente grande también la aproximará bien sobre ejemplos no observados

La hipótesis del aprendizaje inductivo asume que una buena aproximación sobre los datos de entrenamiento se traducirá en una buena aproximación sobre ejemplos futuros no vistos; no garantiza que la hipótesis sea la función objetivo exacta. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.2)

23. El algoritmo Candidate-Elimination termina de procesar todos los ejemplos de entrenamiento con las fronteras G y S conteniendo, cada una, una única hipótesis idéntica entre sí. ¿Qué se puede concluir de este resultado?

1. Que se requieren más ejemplos negativos para poder especializar aún más la frontera G
2. Que el algoritmo ha fallado, porque una hipótesis idéntica en ambas fronteras indica un error en el procesamiento de los ejemplos
3. Que el espacio de versiones ha convergido a una única hipótesis consistente con todos los ejemplos observados
4. Que el espacio de hipótesis es demasiado pequeño para representar el concepto objetivo y debe ampliarse

Cuando G y S convergen a la misma hipótesis única, el espacio de versiones se ha reducido a esa sola hipótesis, la cual coincide con el concepto objetivo si los ejemplos de entrenamiento no contienen ruido. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.5)

24. ¿Cuál de las siguientes afirmaciones sobre el algoritmo Find-S NO es correcta?

1. No detecta si el conjunto de ejemplos de entrenamiento contiene contradicciones (ejemplos inconsistentes)
2. Devuelve la hipótesis más específica del espacio de hipótesis que es consistente con los ejemplos positivos
3. Ignora por completo los ejemplos de entrenamiento negativos durante su ejecución
4. Mantiene y actualiza simultáneamente las fronteras general G y específica S del espacio de versiones

Mantener y actualizar simultáneamente las fronteras G y S es lo que hace el algoritmo Candidate-Elimination, no Find-S, que solo conserva una única hipótesis específica basada en los ejemplos positivos. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, caps. 2.4 y 2.5)

25. Un desarrollador entrena un sistema que decide si un correo electrónico es spam a partir de atributos como el remitente, la longitud del texto y la presencia de ciertas palabras clave. Dentro del marco del aprendizaje por concepto, ¿qué representa el conjunto de todos los correos electrónicos posibles descritos por esos atributos?

1. El conjunto de entrenamiento, formado únicamente por los correos ya etiquetados como positivos o negativos
2. El espacio de versiones, delimitado por las fronteras general G y específica S tras procesar los ejemplos
3. El espacio de hipótesis H, del cual se selecciona la hipótesis más consistente con los ejemplos de entrenamiento
4. El espacio de instancias X, sobre el cual se define la función objetivo booleana que se desea aprender

El espacio de instancias X es el conjunto de todos los objetos posibles descritos por los atributos del problema, sobre el cual se define la función objetivo booleana c; el espacio de hipótesis H es, en cambio, el conjunto de reglas candidatas para aproximar c. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.1)

26. En el aprendizaje por concepto, se dice que una hipótesis h1 es 'más general que o igual a' otra hipótesis h2 cuando toda instancia clasificada como positiva por h2 también lo es por h1. ¿Para qué se utiliza principalmente esta relación de orden entre hipótesis?

1. Para calcular el costo de ruta g(n) entre dos hipótesis dentro de un árbol de búsqueda de estados
2. Para decidir qué ejemplos de entrenamiento deben eliminarse antes de aplicar la regla de resolución
3. Para estructurar el espacio de hipótesis y permitir que algoritmos como Find-S y Candidate-Elimination naveguen entre hipótesis más generales o más específicas
4. Para determinar cuál de dos hipótesis tiene mayor probabilidad a priori dentro de un enfoque bayesiano de clasificación

La relación 'más general que o igual a' impone una estructura de orden parcial sobre el espacio de hipótesis que Find-S y Candidate-Elimination explotan para generalizar o especializar hipótesis de manera sistemática. (Mitchell, T., 'Machine Learning', McGraw-Hill, 1997, cap. 2.3)

27. En el algoritmo de búsqueda A*, la función de evaluación f(n) utilizada para seleccionar el siguiente nodo a expandir combina el costo ya recorrido y una estimación del costo restante hasta la meta. ¿Cuál es la expresión correcta de f(n)?

1. f(n) = g(n) × h(n)
2. f(n) = g(n) + h(n)
3. f(n) = h(n) − g(n)
4. f(n) = g(n) − h(n)

A* combina el costo real acumulado g(n) con la estimación heurística h(n) mediante f(n) = g(n) + h(n); las demás operaciones (multiplicación o resta) no corresponden a la definición estándar del algoritmo. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.5 (Búsqueda informada A*))

28. En el algoritmo de búsqueda A*, se dice que una heurística h(n) es admisible cuando cumple una condición específica respecto al costo real h*(n) de alcanzar la meta desde el nodo n. ¿Cuál es esa condición?

1. h(n) nunca subestima el costo real h*(n)
2. h(n) siempre es igual al costo real h*(n)
3. h(n) nunca sobreestima el costo real h*(n)
4. h(n) siempre sobreestima el costo real h*(n)

La admisibilidad exige que h(n) nunca sobreestime el costo real, es decir h(n) ≤ h*(n); 'nunca subestima' invierte la desigualdad (subestimar sí está permitido), 'siempre igual' describiría una heurística perfecta y 'siempre sobreestima' la haría inadmisible. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.5)

29. En un problema de búsqueda con grafo, donde los nodos ya expandidos no se vuelven a expandir, la heurística h(n) cumple la condición h(n) ≤ c(n, a, n') + h(n') para todo sucesor n' generado por una acción a. ¿Cómo se denomina esta propiedad de la heurística, necesaria para que A* sea óptima en este caso?

1. una heurística consistente
2. una heurística admisible
3. una heurística dominante
4. una heurística inadmisible

La desigualdad h(n) ≤ c(n, a, n') + h(n') define la consistencia (monotonicidad), necesaria para que A* sea óptima con búsqueda en grafo; la admisibilidad, h(n) ≤ h*(n), es una condición más débil que la consistencia implica, por lo que es el distractor más tentador. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.5)

30. En una búsqueda A* sobre un mapa de rutas, el nodo actual A tiene un costo acumulado g(A) = 5. Sus dos sucesores son B, alcanzable con un costo de paso de 3 y heurística h(B) = 4, y C, alcanzable con un costo de paso de 2 y heurística h(C) = 8. Considerando solo estos dos sucesores, ¿cuál debe expandirse primero según el valor f(n)?

1. C, porque f(C) = 15 debe explorarse antes para descartarla
2. B, porque su heurística h(B) = 4 es la única que importa
3. C, porque su costo de paso g = 2 es menor que el de B
4. B, porque f(B) = 12 es menor que f(C) = 15

f(B) = g(A)+3+h(B) = 5+3+4 = 12 y f(C) = 5+2+8 = 15; como A* expande siempre el nodo de menor f(n), corresponde expandir B primero, no un criterio basado solo en g o en h. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.5 (Algoritmo A*))

31. En un problema de búsqueda con factor de ramificación b = 4, donde la solución más superficial se encuentra a profundidad d = 3, la búsqueda en anchura (BFS) puede necesitar generar, en el peor caso, un número de nodos del orden de:

1. 3^4 = 81 nodos
2. 4^3 = 64 nodos
3. 4×3 = 12 nodos
4. 4+3 = 7 nodos

La complejidad de BFS en el peor caso es O(b^d); sustituyendo b=4 y d=3 se obtiene 4^3 = 64, mientras que invertir base y exponente o usar una relación lineal son errores típicos de sustitución. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.1)

32. A diferencia de la búsqueda en anchura, la búsqueda en profundidad (DFS) utiliza una cantidad de memoria mucho menor, del orden de O(b·m), pero presenta dos desventajas importantes frente a BFS en espacios de estados infinitos o con ciclos. ¿Cuáles son estas desventajas?

1. No es completa, aunque siempre garantiza la solución óptima
2. Requiere más memoria que BFS aunque sea más rápida
3. No es completa ni garantiza encontrar la solución óptima
4. Es completa, pero nunca garantiza la solución óptima

DFS puede quedar atrapada en ramas infinitas o ciclos (no es completa) y expande nodos sin considerar el costo acumulado (no garantiza optimalidad); además usa menos memoria que BFS, no más. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.3)

33. La búsqueda de costo uniforme es equivalente al algoritmo de Dijkstra cuando los costos de paso son no negativos. ¿Qué criterio determina cuál nodo de la frontera se expande en cada iteración?

1. el menor costo de ruta acumulado g(n)
2. la menor estimación heurística h(n)
3. la mayor profundidad en el árbol de búsqueda
4. el menor valor combinado f(n) = g(n) + h(n)

La búsqueda de costo uniforme expande siempre el nodo con menor g(n) acumulado, sin usar heurística; usar h(n) corresponde a la búsqueda voraz y usar f(n)=g+h corresponde a A*. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.2)

34. Un agente de búsqueda utiliza únicamente la estimación heurística h(n) para decidir qué nodo expandir a continuación, sin considerar el costo ya recorrido g(n). Esta estrategia, conocida como búsqueda voraz primero el mejor, no garantiza en general dos propiedades importantes de los algoritmos de búsqueda. ¿Cuáles son?

1. admisibilidad y consistencia
2. completitud y consistencia
3. optimalidad y admisibilidad
4. optimalidad y completitud

Al usar f(n) = h(n), la búsqueda voraz puede seguir rutas costosas o ciclos indefinidamente, por lo que no garantiza optimalidad ni completitud; admisibilidad y consistencia son propiedades de la heurística, no del algoritmo. (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.5.1)

35. Cuando se desconoce de antemano la profundidad de la solución en un espacio de estados muy grande, se prefiere un método de búsqueda sin información que combine la completitud y optimalidad de BFS con los bajos requisitos de memoria de DFS. ¿Cómo se llama este método y cuál es su complejidad en memoria?

1. búsqueda de costo uniforme, con memoria O(b^d)
2. búsqueda en profundidad iterativa, con memoria O(b·d)
3. búsqueda en anchura, con memoria O(b·d)
4. búsqueda bidireccional, con memoria O(b^(d/2))

IDDFS repite búsquedas DFS con límites de profundidad crecientes, logrando memoria lineal O(b·d) junto con la completitud y optimalidad de BFS, que requiere memoria exponencial O(b^d). (Russell, S. y Norvig, P., 'Inteligencia Artificial: Un Enfoque Moderno', 3ª ed., cap. 3.4.5)