Preguntas etiquetadas con csp

CSP representa el problema de la satisfacción con las limitaciones.

17
Satisfacción de restricciones abierta o interactiva

En el pasado, implementé modelos de coordinación utilizando SAT y satisfacción de restricciones regulares como el caballo de batalla principal en sus motores. Continuando en esta línea de trabajo, me gustaría hacer que los modelos sean más interactivos, y la mejor manera que veo de hacerlo es abrir...

15
Mantener el orden en una lista en

El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...

12
Teorema de Schaefer y CSP de ancho ilimitado

El teorema de la dicotomía de Schaefer muestra que cada problema de CSP sobre puede resolverse en tiempo polinómico o es NP completo. Esto aplica solo para problemas CSP de ancho acotado, excluyendo SAT y Horn-SAT, por ejemplo. Los problemas generales de CSP de ancho ilimitado pueden ser muy...

11
¿El problema de N Queens es NP-duro?

El problema de N-queen es este: Entrada: N Salida: una colocación de N "reinas" en un tablero de ajedrez de NXN de modo que no haya dos reinas en la misma fila, columna o diagonal. Al hacer una búsqueda en Google sobre esto, descubrí que muchas diapositivas de muchos profesores afirman que este...