Test 2 de heurística

Un literal l es puro en una fórmula F: Si aparece una única vez en F. Si aparece en todas las cláusulas de F. Si ¬l no aparece nunca en F.

Para resolver un problema de satisfacción de restricciones. Basta con aplicar arco consistencia y camino consistencia tantas veces como haga falta hasta que no cambie el dominio de ninguna variable de decision y ningún dominio resulte ser vacío. Es preciso aplicar un algoritmo de búsqueda que intente varias instanciaciones parciales aplicando la arco consistencia y la camino consistencia hasta que se alcance una instanciación global compatible con las restricciones del problema. Basta con aplicar arco consistencia hasta que no hay cambio en el dominio de ninguna variable de decision y ningún dominio resulta ser vacío.

En el caso del 15-puzzle (igual al 8-puzzle con matriz de 4x4 y 15 dígitos), ¿cuál sería la mejor aproximacion al valor de factor de ramificación medio?. 15. 3. 4.

Resolviendo problemas con el uso de algoritmos de búsqueda, uno de los parámetros fundamentales de complejidad es el número total de operadores definidos en el problema. Verdadero. Falso. Verdadero, siempre que además se divida por el número de estados.

si de la resolucion de dos cláusulas resulta la cláusula vacía (∅ ) durante la aplicacion del algoritmo DAvis-Putnam (DP): Es imposible que la resolución de dos cláusulas dé lugar a la cláusula vacia. El problema es satisfacible. El problema no es satisfacible.

El modelo de resolución garantiza que: El número de variables decrece monótonamente. El número de cláusulas y variables decrede monótonamente. El número de cláusulas decrece monótonamente.

La arco consistencia garantiza que: No garantiza nada. Si una relación es arco consistente entonces puede extenderse a una solución global con total seguridad. Contiene los valores que son simultáneamente legales entre todas las variables involucradas.

En satisfacción de restricciones, una restricción se define como: Una relación entre dos o más variables que establecen todos los valores simultaneamente legales para esas variables. Un grafo cuyos vértices representan valores permitidos por las variables y cuyas aristas representan las variables involucradas. Una expresion lineal de la forma ≤, = o ≥.

Una fórmula proposicional está en Forma Normal Conjuntiva (FNC). Si consiste en la disyunción de conjunciones. Si consiste en la conjunción de disyunciones. Si no tiene cuantificadores existenciales ni universales.

El número de pasos necesarios para resolver la satisfacibilidad de una fórmula en Forma Normal Conjuntiva cuando se aplica Davis-Putnam (DP): Podría ser infinito. Está limitado por el número de cláusulas de la forma lógica. Está limitado por el número de variables de la fórmula lógica.

Si se utiliza el algoritmo de Dijkstra para resolver un problema de costes arbitrarios, ¿encontrará la solución óptima en términos de número de operadores aplicados?. No se asegura. Nunca. Siempre.

El algoritmo de búsqueda de primero en profundidad tiene un consumo de memoria que crece: Exponencialmente. Linealmente. No crece y se mantiene constante.

Resolviendo problemas con el uso de algoritmos de búsqueda, uno de los parámetros fundamentales de complejidad es el número medio de operadores que pueden aplicarse en cada estado: Siempre que, además, se divida por el número de estados. Falso. Verdadero.

La arco consistencia entre dos variables Xi y Xj consiste en: Calcular la unión de los dominios Di y Dj. Restringir los dominios Di y Dj desestimando los valores imposibles. Aumentar los dominios Di y Dj hasta que exista alguna asignación factible.

Un grupo de estudiantes ha desarrollado dos clases de algoritmos de búsqueda heurística. Elija la opción preferible: Una clase A de algoritmos que aseguran ser completos pero no admisibles. Una clase B de algoritmos que aseguran ser admisibles pero no completos. Una clase C de algoritmos que aseguran ser completos y además admisibles.

¿Cuántos nodos hay en total en un árbol de búsqueda desarrollado con un factor de ramificación 4 hasta la profundidad 3?. 85. 64. 81.

La resolución unitaria de la fórmula lógica proposicional F= (x1 ∨ x2) ∧ (¬x1 ∨ x3) respecto de x1 da lugar a: La fórmula F'= x3. La fórmula F' = x2 ∨ ¬x3. La fórmula F' = x2 ∨ x3.

La resolución de las cláusulas C₁ = (x1 ∨ x2) y C₂ = (¬x1 ∨ x3) respecto del literal x1 da lugar a: La cláusula (x2 ∨ x3). La cláusula (x2 ∧ x3). La cláusula (x1 ∨ x1).

Considerese que se dispone de dos funciones heurísticas admisibles h₁(n) y h₂(n) que no están ordenadas entre sí. ¿Qué combinación es mejor?. h₃(n) = min{h₁(n), h₂(n)}. h₃(n) = max{h₁(n), h₂(n)}. h₃(n) = h₁(n) + h₂(n).

La profundidad del árbol desarrollado para resolver la satisfabilidad de una fórmula en Forma Normal Conjuntiva cuando se aplica DPLL: Está limitado por el número de cláusulas de la fórmula lógica. Podría ser infinito. Está limitado por el número de variables de la fórmula lógica.

Carreteras de dos sentidos y 60 ciudades de las que parten/llegan 2 carreteras de 2 sentidos. ¿Cuál sería el factor de ramificacion?. 2.33. 2. 1.25.

Si después de aplicar cualquier modelo de consistencia (ya sea arco consistencia o camino consistencia) resulta el conjunto vacío para el dominio de alguna variable: La asignación parcial actual es infactible pero podría haber solución. El problema es infactible. El problema se ha resuelto, la solución es la asignación actual.

Se denomina resolución unitaria: A la resolución de dos clausulas que resulta en una clausula unitaria. A la resolución de una clausula consigo mima. A la resolucion que se practica cuando una de las cláusulas madre es unitaria.

La camino consistencia entre dos variables Xi y Xj respecto de una tercera Xk consiste en: La suma de los dominios Di, Dj y Dk. Calcular los valores simultáneamente legales de Xi para los que hay valores compatibles en Xk que, a su vez, tienen valores legales permitidos para Xj. La unión del resultado de aplicar la arco consistencia entre Xi y Xk y entre Xk y Xj.

En cualquier árbol de búsqueda hay más nodos expandidos que generados: Es siempre cierto si b > 1. Es falso, a menos que el factor de ramificacion sea menor que 2, b<2. Es siempre cierto si la profundidad del árbol es mayor que 1, d>1.

Considerese una función heuristica h(n) = k que devuelve para cualquier estado n el mismo valor constante k. Marque la respuesta correcta: Su uso convierte a cualquier algoritmo de búsqueda heurística en otro de fuerza bruta. Es una función heurística perfecta. Es buena heurística para usar en escalada, pero tal vez no con otros algoritmos.

La profundidad del árbol desarrollado para resolver la satisfabilidad de una fórmula en Forma Normal Conjuntiva cuando se aplica Davis-Putnam_logemann_loveland (DPLL): Está limitado por el número de cláusulas. Podría ser infinito. Está limitado por el número de variables.

Se dice que una forma de propagación de la consistencia es direccional cuando solo afecta a una de las variables de decisión involucradas. En particular, la camino consistencia: Es direccional. No tiene sentido hablar de direcciónalidad en el caso específico de la camino consistencia. No es direccional.

La técnica de relajación de restricciones sirve para obtener funciones heuristicas metodicamente y de una forma sencilla. Marque la afirmación correcta: Las mejores estimaciones se obtienen relajando la mayor cantidad de restricciones. Las mejores estimaciones se obtienen relajando la menor cantidad de restricciones. Si se relajan todas las restricciones se obtiene una heurística perfecta.

Escoja, de entre las siguientes opciones, el árbol de búsqueda que se recorrerá más fácilmente con el uso de un algoritmo de fuerza bruta (siendo b el factor de ramificación y d la profundidad del árbol): b = 4 y d = 4. b = 10 y d = 3. b = 3 y d = 10.

Si el factor de ramificación de un árbol de búsqueda es 3 y se usa búsqueda en amplitud, ¿cuántos nodos habrá en memoria cuando los nodos de la profundidad 4 se estén generando?. 27. 81. 3.

La arco-consistencia es direccional si afecta únicamente a una de las variables de decisión involucradas. En particular la arco-consistencia: No es direccional. Es direccional. No tiene sentido considerarla direccional.

Si el problema no tiene costes asociados a los operadores, ¿qué algoritmo se usa para obtener una solución óptima?. depth-first. breadth-first. depth-first branch and bound.

Resolviendo problemas con el uso de algoritmos de búsqueda, uno de los parámetros fundamentales de complejidad es el coste de la solución óptima: Multiplicado por el número de estados de la solución. Verdadero. Falso.

La consistencia de un camino entre dos variables Xi y Xj con respecto a una tercera variable Xk consiste en: Calcular simultáneamente los valores de Xi que son compatibles ocn los de Xk, que a la vez tienen valores compatibles con Xj. La suma de los dominios Di, Dj y Dk. La unión de los resultados de arco-consistencia de Xi y Xk por una parte, y Xk y Xj por otra.

La técnica de relajación de restricciones se usa para obtener funciones heurísticas metodologicas y simples. Marca la respuesta correcta: Las mejores estimaciones se obtienen relajando más restricciones. Las mejores estimaciones se obtienen relajando menos restricciones. Si todas las restricciones están relajadas se obtiene la heurística perfecta.

La resolución de las cláusulas: C1: (x1 ∨ x2) y C2: (¬x1 ∨ ¬x3) respecto del literal x1 da lugar a: (x2 ∧ ¬x3). (x1 ∨ ¬x1). (x2 ∨ ¬x3).

La resolución de las cláusulas: C1: (x1 ∨ x2) y C2: (¬x2 ∨ ¬x4) respecto del literal x2 da lugar a: (x4 ∧ ¬x1). (x1 ∨ ¬x4). (x2 ∨ ¬x3).

El objetivo de la satisfacción de restricciones es: Encontrar una asignación parcial. Identificar restricciones inconsistentes. Encontrar instanciaciones globales consistentes. Simplificar la red.

Una instancia parcial es: Afecta a todas las variables. Asigna valores a un subconjunto de variables. Siempre inconsistente. Equivalente a solución global.

En el grafo de restricciones, los nodos representan: Variables. Restricciones. Dominios. Arcos consistentes.

Definición de arco consistencia: Todas las variables deben tener valor. Cada valor de Di debe tener uno compatible en Dj. La red es globalmente consistente. Solo se aplica a variables adyacentes.

AC-REVISE elimina valores cuando: No tienen valores compatibles en otra variable. No forman parte de la solucion. Son incompatibles globalmente. Están duplicados.

AC-1 garantiza arco consistencia en: Una variable. Un subconjunto. Toda la red. Nodos terminales.

La camino consistencia verifica: Solo pares. Consistencia entre tres variables. Que todos los valores sean compatibles. Que no existan redundancias.

Próposito de CC-REVISE: Eliminar valores no camino-consistentes. Detectar todas las inconsistencias. Asignar valores. Simplificar globalmente.

Si una restricción Rij no es camino consistente respecto a Xk se elimina: Valores en domino de Xk. Valores incompatibles de Rij. La restriccion completa. Restricciones entre Xk y Xi.

La programación por restricciones es útil porque: Siempre encuentra solución óptima. Simplifica problemas complejos con consistencia. Elimina restricciones innecesarias. No depende de los dominios.

Si Xi no es arco consistente con Xj: Se eliminan valores de Xj. Se eliminan valores de Xi sin soporte en Xj. Se eliminan ambas. Se elimina la restricción.

Camino consistencia es mejor que arco consistencia porque. Detecta inconsistencias entre tres variables. Elimina todas las redundantes. Encuentra solución global. Garantiza dominios finales consistentes.

La eliminación de valores de dominios ocurre cuando: No satisfacen alguna restricción. Tienen muchos compatibles. No forman parte de solucion parcial. La restricción es redundante.

¿Qué algoritmo fuerza camino consistencia en toda la red?. AC-1. CC-1. CC-REVISE. AC-REVISE.

Si Rxy = ∅ tras aplicar camino consistencia: Se elimina la restricción. No hay valores legales para x e y. Se eliminan dominios. No afecta.

La resolución unitaria consiste en operar con: Cláusulas con varios literales. Cláusulas con un único literal. Cláusulas sin literales. Cualquier cláusula que contenga un literal puro.

Una cláusula es una tautología si: Es siempre falsa. Es siempre verdadera. Tiene exactamente dos literales. No contiene literales negados.

Una fórmula es satisfacible si: Tiene al menos una cláusula unitaria. Existe una asignación que la hace verdadera. No contiene literales puros. Siempre puede convertirse a CNF.

En DPLL, ante un literal puro se debe: Ignorarlo y continuar. Sustituirlo por su negación. Asignarlo como verdadero y eliminar las cláusulas que lo contienen. Convertir la fórmula a forma disyuntiva.

Un modelo es: Una fórmula equivalente con menos cláusulas. Una asignacion de verdad que satisface la fórmula. Una combinación de cláusulas sin literales vacíos. Un conjunto de literales obtenidos tras resolución.

En DPLL hay backtracking cuando: Hay un literal puro. Se llega a una asignación inconsistente. Se elimina una cláusula tautológica. Se encuentra una cláusula unitaria.

DPLL declara una fórmula satisfacible cuando: Todas las cláusulas tienen al menos dos literales. La fórmula se reduce al conjunto vacío {}. No tiene literales negados. No hay literales puros pero sí unitarios.

La resolucion unitaria sirve para: Aumentar el espacio de búsqueda. Reducirlo propagando asignaciones. Obtener una CNF equivalente. Identificar tautologías automáticamente.

Ventaja de DPLL sobre resolución estándar: No requiere CNF. Es más eficiente por heurísticas y propagación. Siempre evita backtracking. Produce modelos únicos para cada fórmula.

Una tautología puede. Eliminarse sin afectar la satisfacibilidad. Convertirse en cláusula vacía. Invalidar el modelo parcial. Cambiar los literales puros.

Si no hay literales puros ni unitarios, DPLL: Termina el algoritmo. Selecciona un literal arbitrario. Convierte la fórmula a forma DNF. Elimina todas las cláusulas.

El rendimiento de DPLL depende. Linealmente del número de variables. Exponencialmente de variables y cláusulas. Solo del número de literales puros. Del número de cláusulas unitarias.

El factor de ramificación b es: El número promedio de sucesores. La profundidad del árbol. El coste de un operador. El número total de estados.

En búsqueda no informada, la amplitud es óptima si: El factor de ramificación es 1. Todos los operadores tienen el mismo coste. No existen ciclos. Se poda el árbol en cada nivel.

Una desventaja de la búsqueda en profundidad es. Consume mucha memoria. No encuentra el camino más corto. Puede no ser completa. No explora suficiente el espacio.

La profundidad iterativa mejora profundidad porque. Evita estados repetidos siempre. Combina baja memoria con completitud. Genera soluciones óptimas siempre. Solo analiza nodos terminales.

Una heurística es. Un algoritmo óptimo. Conocimiento parcial que guía la búsqueda. Una función que garantiza solución. Una técnica para eliminar restricciones.

Una heurística es admisible si. Siempre sobreestima. Es igual al coste real. Nunca sobreestima el coste. Evita ciclos automáticamente.

Mejor primero ordena nodos según. g(n). El número de sucesores. f(n). Cantidad de ciclos detectados.

En A*, la función de evaluación es: g(n) + h(n). h(n) - g(n). Solo h(n). g(n) x h(n).

En el 8-puzzle, una heurística común es: Profundidad del árbol. Número de piezas mal colocadas. Factor de ramificación. Coste de operadores.

En la búsqueda en escalada, un problema común es. Generar estados repetidos. Quedar atrapado en máximos locales. Consumir mucha memoria. No poder llegar a la meta.

Beam Search se diferencia en escalada porque: Considera un subconjunto de nodos en cada nivel. Garantiza optimalidad. No usa heurísticas. Solo expande un nodo por nivel.

IDA mejora A* porque: Reduce siempre el tiempo. Usa memoria proporcional a la profundidad. No necesita heurísticas. Evita llamadas recursivas.

BFS se caracteriza por. Usar muy poca memoria. Usar memoria proporcional al nivel más profundo. No ser completa. Ser óptima sin condiciones.

En Torres de Hanoi, el factor de ramificación depende de. Profundidad máxima. Número de discos. Coste de operadores. Número de movimientos mínimos.

La heurística Manhattan en 8-puzzle es útil porque: Da el coste exacto. Estima distancia total en movimientos. Elimina estados no óptimos. No depende de la meta.

Ventaja de profundidad iterativa: Es más rápida que amplitud. No repite nodos. Combina memoria baja con completitud. Encuentra siempre el camino óptimo.

La complejidad de un problema depende del número total de operadores. Verdadero. Falso.

Árbol más fácil de explorar por fuerza bruta: b = 4, d = 4. b = 10, d = 3. b = 3, d = 10. b = 2, d = 6.

¿La arco consistencia es direccional?. Si. No. No tiene sentido plantearlo. Sólo en redes binarias.

Una heurística h(n)=k constante: Es buena para hill climbing. Convierte búsqueda en no informada. Heurística perfecta. Reduce el espacio de búsqueda.

En BFS con b=3, generando nodos a profundidad 4, memoria ≈. 27. 81. 9. 243.