GecodeProgramación con restricciones

Gecode es una herramienta para el desarrollo de sistemas basados en restricciones◦ Abierto◦ Gratuito◦ Portable◦ Eficiente◦ ConcurrenteEstá disponible para Linux, Windows y Mac OS

www.gecode.org

¿Qué es Gecode?

Primera aproximación Secuencia mágica

Constructura:◦ En la constructora se inicializan las variables de

decisión, se declaran las restricciones y el branching

◦ El branching es, a grandes rasgos, la definición de por dónde debe empezar y hacia dónde debe ir la búsqueda de una solución al problema

Estructura de un modelo

Todo modelo debe incluir:◦ Constructora adicional que actualiza el valor de

las variables de decisión

◦ Función Copy() que devuelve una copia del espacio apoyándose en la constructora anterior

Soporte de búsqueda

Las variables de decisión se pueden imprimir como si fueran variables de C++

Impresión de la solución

En el main se deben seguir los siguientes pasos:

◦ Se crea el modelo◦ se crea el motor de búsqueda para el modelo◦ se obtiene una (o varias) de las soluciónes y se

imprimen.

Main

#include <gecode/int.hh>

IntVar◦ Son el equivalente a los var int de Minizinc.

◦ Constructora: IntVar(home, liminf, limsup)

Tipos de datos para enteros

IntSet◦ Son el equivalente a los conjuntos de minizinc.

◦ Constructora: IntSet(home, minDom, maxDom)

◦ Se puede construir una variable entera pasándole un IntSet como dominio: IntVar x(home, IntSet(-10, 10)

IntVarArray◦ Son el equivalente a los array of var de Minizinc

◦ Constructoras: IntVarArray(home, n, liminf, limsup)

◦ Acceso: IntVarArray x(home, 10, 0, 9) x[i] será la posición i-ésima del array siendo i un

entero.

Matrices◦ Las matrices en Gecode son algo especiales.

◦ Creación: IntVarArray x(home, N*M, a, b) Matrix<IntVarArray> m(x, N, M)

◦ Acceso: m(i,j) m.row(i): Fila i-ésima de la matriz m.col(i): Columna i-ésima de la matriz

Sudoku

Restricciones

Devuelven “trozos” de la matriz que cumplen ciertas condiciones

Tienen su versión para arrays

Slices

Relaciones:◦ Las relaciones en Gecode se definen de una

manera especial: rel(home, var1, rel_type, var2)Ejemplo:

rel(home, x, ITR_LE, y) => x< y

Tipos de relaciones:

Restricciones y operaciones

Count(home, var1, var2, rel_type, c)◦ c será igual al número de veces que aparece var2

en el vector var1. Member(home,x,y):

◦ El valor y debe aparecer por lo menos una vez en el array x

Distinct(home, x): ◦ Todos los valores del array x deben ser distintos

Operaciones aritméticas

Heredan de la clase Space.

Junto con la clase Options permiten parametrizar problemas de tamaño variable

Scripts

Script secuencia mágica

Soporte de búsqueda

Main

Es una herramienta gráfica que incluye Gecode.

Permite ver gráficamente cómo progresa la búsqueda de una solución.

Gist

¿Cómo usar Gist en un modelo?

◦ Solo hace falta cambiar el main:

Se crea el modelo Se crea la instancia de Gist para el modelo Se elige el motor de búsqueda y se le pasa el modelo

y las opciones de Gist

Para la secuencia mágica:

Descargar el ejecutable correspondiente a la versión de Visual Studio del sistema.

Al crear un proyecto nuevo acceder a propiedades del proyecto->C/C++ y agregar la carpeta /Gecode/include en Directorios de inclusión adicionales

¿Cómo instalar Gecode?

En las opciones del vinculador añadir la carpeta /Gecode/lib en Directorios de bibliotecas adicionales

Es útil para aplicaciones reales

Es extremadamente rápido

Es intuitivo

La documentación disponible es excelente

Muy recomendable aprender a usarlo

Conclusiones