T4 prt2

Dadas la variables x, y, z con dominios Dx= {0, 1, 2} Dy ={3,4} Dz= {0,1} Con restricciones: x >= y-1 y >= z+4 x= z +2 ¿Cuál de las siguientes afirmaciones es cierta?: Aplicando el algoritmo AC3, podemos asegurar que NO tiene solución. Aplicando el algoritmo AC3, podemos asegurar que tiene una única solución. Aplicando el algoritmo AC3, podemos asegurar que tiene más de una solución.

Sobre las limitaciones de Backtracking, cuando hay una restricción binaria entre dos variables hablamos de.. Inconsistencia de arista. Inconsistencia de nodo. Ninguna de las anteriores.

En Backtracking, si No se puede extender la solución parcial: Se elimina la última decisión. Se elimina una decisión anterior. Las dos anteriores son correctas.

¿Cuál de las siguientes afirmaciones de Generación y test es correcta?. Busca la solución mediante una expansión del árbol en anchura. Busca la solución mediante una expansión del árbol en altura. Ignora ciertas soluciones para alcanzar un óptimo.

Tiene sentido que Backtracking calcule la expansión de todos los nodos: Sí, para tener todas las soluciones. Sí, porque el orden de aplicación de las acciones es conmutativo. No, porque hay conmutatividad.

En el algoritmo AC3, cuando un dominio queda vacío ¿qué significa?. Que el problema es. Inconsistente y sin solución. Consistente y sin solución. Consistente y con solución única.

Las características de la Generación de crucigramas son. Dominios continuos y restricciones binarias. Dominios discretos y restricciones múltiples. Dominios discretos y CSP binario.

Dentro de los métodos de solución, en el backtracking no cronológico. Se elimina la última decisión. Se elimina la decisión anterior. No elimina ninguna decisión.

El backjumping. hace el retroceso a la primera variable instanciada. no hace retroceso. hace el retroceso a la variable más profunda que está en conflicto con la variable actual.

¿Cuáles son las características de la generación de crucigramas?. Dominios continuos y restricciones ternarias. CSP ternario y sin restricciones. CSP Binario, discreto (dominios grandes).

De entre las siguientes limitaciones del método Backtraking selecciona aquella que es incorrecta. Trashing e inconsistencia del nodo. Sucede cuando un dominio contiene un valor que no satisface una restricción unaria. Consistencia de arista. Sucede cuando una restricción binaria entre dos variables de tal forma que para un determinado valor de la primera variable existe una asignación posible para la segunda. Dependencia de ordenación. El orden de selección de las variables es un factor crítico. Existen diferentes heurísticas de selección de variable y de valor, esto es, variables con Orden Estático y Orden Dinámico y valores p.e que conducen a CPS más simples.

(7,5,3,1,6,8,2,4). (4,7,8,3,2,1,5,6). (4,7,3,8,2,5,1,6).

El Forward checking, en cada etapa de la búsqueda, comprueba hacia delante la asignación actual con. un valor de las futuras variables que están restringidas con la variable actual. uno o varios valores de las futuras variables que están restringidas con la variable actual. todos los valores de las futuras variables que están restringidas con la variable actual.

¿Qué diferencia hay entre Backjumping y Backtracking?. Backjumping retrocede hacia la variable más profunda que está en conflicto con la actual, Backtracking realiza el retroceso hacia la variable más prometedora. Backjumping retrocede hacia la variable más profunda que está en conflicto con la actual, Backtracking realiza el retroceso hacia la variable instanciada anteriormente. Ninguna. Ambas nomenclaturas sirven para definir el mismo método de resolución.

Centrándonos en la propagación de restricciones y propiedad de consistencia de arista podemos afirmar que es correcto que: Un CSP no puede transformarse en una red consistente mediante un algoritmo sencillo (AC3). La propagación de restricciones no se suele usar porque transforma el problema en otro más complejo con inconsistencias de arco. Un CSP puede transformarse en una red consistente mediante un algoritmo sencillo (AC3).

Cuál de las siguientes afirmaciones es verdadera: en el Árbol de interpretaciones cada nodo identifica una posibilidad de asignación,cada hoja es una interpretación de la solución y esta misma supervisa todo el proceso comparando su resultado volviendo a el nodo raíz . en el árbol de interpretaciones el orden de descenso viene especificado por a, todos los nodo se evalúa si puede existir una posibilidad de asignación según su valor y va haber tantos niveles como asignaciones de datos. el nodo raíz supervisa el proceso de asignación, solo se especifica una posibilidad de especificación cuando hemos expandido todo el árbol en profundidad asignando una variable por cada nivel del árbol.

Cuál de las siguientes opciones es correcta: Backjumping construye la solución de forma gradual y su retroceso se hace a la variable instanciada anteriormente. Backtracking construye la solución de forma gradual y su retroceso se hace a la variable más profunda que está en conflicto con la variable actual. Generación y test genera de forma sistemática y exhaustiva cada una de las posibles asignaciones y comprueba que satisfacen todas las restricciones.

Indica cuál de las siguientes afirmaciones es cierta sobre al algoritmo AC3: Si el grafo es consistente obligatoriamente tiene que tener solución. Si el grafo es consistente puede tener una solución o más. Si el grafo es inconsistente podemos encontrar solución.

En lo referente a los métodos de resolución, podemos afirmar que Generación y test: Construye la solución de forma gradual, instanciando varia les en el orden definido por la permutaci n dada. Construye la soluci n de forma gradual, instanciando la varia le m s profunda que est en conflicto con la varia le actual. Genera cada una de las posibles asignaciones a las variables y comprueba si satisfacen todas las restricciones.

Si hablamos de Forward checking podemos afirmar que: Los valores de las variables futuras que son inconsistentes con la asignación actual no son eliminados de sus dominios. Si ningún valor es consistente, entonces se lleva a cabo el backtracking no cronológico. Ninguna de las anteriores.

Dentro de los métodos de resolución tenemos los Algoritmos híbridos. ¿Cuál de los siguientes es un algoritmo híbrido?: Forward Checking. Maintaining Arc Consistency. Las respuestas anteriores son ambas correctas.

CSP busca: La relación N-aria que satisface todas las restricciones del problema. Según los requerimientos del problema hay que encontrar todas las soluciones o sólo una. Ambas son correctas.

¿Qué método de búsqueda para problemas de satisfacción de restricciones, construye la solución de forma gradual, instanciando variables en el orden definido por la permutación dada?. Generación y test. Backjumping. Backtracking.

Tras la utilización del algoritmo AC3 hemos logrado eliminar todos los valores que causan inconsistencia del dominio de cada variable. Con este exitoso resultado podemos afirmar que: Como hemos logrado eliminar toda inconsistencia no nos hará falta hacer backtracking nunca. Tendremos que concluir utilizando backtracking siempre. Usaremos backtracking únicamente cuando la eliminación de inconsistencias de lugar a más de una solución.

En búsqueda para problemas de satisfacción de restricciones las limitaciones de "inconsistencia de arista", "trashing e inconsistencia de nodo" y "dependencia de la ordenación" pertenecen al método de resolución. Esquema de propagación de restricciones. Esquema backtracking. Esquema forward checking.

¿Cuál de entre los siguientes podría considerarse como método de inferencia puro?. Heurísticas. Consistencia de caminos. Forward Checking.

En un problema de satisfacción de restricciones (CSP). Cada restricción implica al conjunto de variables y especifica las combinaciones aceptables de valores para dicho conjunto. La solución es una relación n-aria que satisface algunas restricciones del problema. Visualizarlo como un grafo de restricciones puede usarse para simplificar el proceso de solución.

x = 5, y= 4, z = 3. Es una posible solución. x = 3, y = 1, z = 4. Es una posible solución. x = 5, y = 4, z = 3. Es solución única.

Es consistente sin solución. Consistente con dos soluciones. Inconsistente con dos soluciones.

Respecto al Forward checking…. En cada etapa de la búsqueda, comprueba hacia atrás la asignación actual con algunos de los valores de las futuras variables que están restringidas con la variable actual. En cada etapa de la búsqueda, comprueba hacia adelante la asignación actual. con algunos de los valores de las futuras variables que están restringidas con la variable actual. Ninguna de las anteriores es correcta.