CSP: estados, consistencias locales y heurísticas clave para resolución

¿Qué se entiende por juego de suma cero?

Juego de suma cero: Es un escenario donde los agentes compiten entre sí y el total de ganancias y pérdidas entre los agentes es constante; la ganancia de uno es la pérdida del otro. Un ejemplo es el ajedrez, porque si un jugador gana, el otro pierde y no hay posibilidad de un beneficio mutuo.

¿Cómo se define un estado en un CSP?

Un estado se define por una asignación de valores a algunas o todas las variables. Las asignaciones pueden clasificarse como:

Tipos de asignación

• Asignación legal: Es un estado donde la asignación no viola ninguna restricción.
• Asignación completa: Es aquella en la que se asigna cada variable; una solución a un CSP es una asignación consistente y completa.
• Asignación parcial: Asigna valores solo a algunas de las variables, no a todas.

Ejemplo de las 3 asignaciones

Si tenemos un problema con 3 variables X1, X2, X3, cada una con dominios D1 = D2 = D3 = {A, B, C}, y la restricción dada por la relación X1 != X2:

• La asignación {X1 = A, X2 = B} es una asignación legal y parcial (ya que no viola la restricción).
• La asignación {X1 = a, X2 = B, X3 = A} es una asignación ilegal y completa (observe que a en minúscula no pertenece al dominio {A, B, C}).
• La asignación {X1 = A, X2 = B, X3 = C} es una asignación legal y completa.

Mencione y explique los diferentes tipos de consistencia local

A continuación se describen las principales nociones de consistencia local en CSPs:

• Nodo consistencia (unaria):

  Cada variable individualmente debe tener un dominio que cumpla con las restricciones unarias aplicadas a ella. Por ejemplo, si una variable tiene dominio {1,2,3} y la restricción unaria exige que la variable sea par, entonces su dominio debe reducirse a {2}.

• Arco consistencia (binaria):

  Una variable es arco-consistente respecto a otra si, para cada valor en su dominio, existe al menos un valor en el dominio de la otra variable que no viole la restricción binaria entre ellas. En otras palabras, cada valor tiene un apoyo válido en la variable vecina.

• Consistencia de camino:

  Extiende la idea de arco-consistencia a secuencias de variables. Un conjunto de variables es consistente en camino con respecto a una tercera variable si, para cada asignación de valores a ese conjunto, existe una asignación a la tercera variable que no viole las restricciones.

• K-consistencia:

  Generaliza aún más la consistencia de camino. Un CSP es k-consistente si, para cualquier conjunto de k − 1 variables y cualquier asignación consistente a esas variables, siempre se puede encontrar un valor consistente para una k-ésima variable.

¿Qué algoritmo busca mejorar backjumping? ¿Cómo lo hace?

Backjumping mejora la eficiencia del backtracking al identificar los conflictos recientes y retroceder de manera más inteligente. En lugar de retroceder paso a paso, el backjumping salta hacia atrás hasta la variable responsable del conflicto, evitando explorar ramas de búsqueda que se sabe que conducirán a contradicciones. Esto puede ser especialmente útil en problemas CSP complejos.

¿Cómo se puede saber cuál es la variable más restringida y qué es la heurística de grado?

La variable más restringida (también llamada MRV, Minimum Remaining Values) es la que tiene menos valores en su dominio. La heurística de grado selecciona la variable que participa en más restricciones con otras variables (es decir, la de mayor grado en el grafo de restricciones).

¿Cuáles son los tres componentes principales de un problema de satisfacción de restricciones (CSP)?

• Las variables: un conjunto de variables.
• Los dominios: un conjunto de dominios, uno para cada variable.
• Las restricciones: un conjunto de restricciones que especifican combinaciones permisibles de valores para las variables.

¿Qué es la consistencia de nodo en un CSP? Proporcione un ejemplo

Consistencia de nodo: Una variable es nodo-consistente si todos los valores en su dominio satisfacen las restricciones unarias impuestas sobre esa variable.

Ejemplo: Si una variable X tiene el dominio {1,2,3} y la restricción es que X debe ser par, entonces X será nodo-consistente si su dominio se reduce a {2}.

¿Qué heurísticas se pueden usar para seleccionar las variables y los valores en un CSP? Describa al menos dos.

• Variable más restringida (MRV):

  Selecciona la variable con el menor número de valores en su dominio (intenta reducir el branching factor lo antes posible).

• Valor menos restrictivo (least-constraining value):

  Selecciona el valor que elimina la menor cantidad de valores en los dominios de las variables futuras, con la intención de mantener abiertas más opciones para las asignaciones posteriores.

¿En qué consiste la heurística min-conflicts en la búsqueda local para CSPs?

Min-conflicts es una heurística utilizada en búsqueda local para CSPs. En cada paso, asigna a una variable un valor que minimiza el número de restricciones violadas (conflictos) con las demás variables. Es especialmente eficaz cuando se parte de una asignación completa y se intenta reducir gradualmente el número de conflictos.