Quizás el paradigma de programación más popular es la programación imperativa. Pero este no es el único tipo de programación, la programación funcional y lógica es ampliamente conocida. La programación de restricciones no es tan popular. Pero es una herramienta muy poderosa para resolver problemas combinatorios. En lugar de implementar un algoritmo que resuelve un problema y luego dedicar mucho tiempo a depurarlo, refactorizarlo y optimizarlo, la programación de restricciones le permite simplemente describir el modelo en una sintaxis especial, y un programa especial (solucionador) encontrará la solución por usted (o le dirá si ellos no son). Impresionante, ¿no? Me parece que todo programador debería ser consciente de esta posibilidad.
Minizinc
Probablemente la herramienta de programación de restricciones más utilizada (al menos con fines educativos) es minizinc . Proporciona un IDE para declarar modelos y varios solucionadores integrados para encontrar una respuesta. Puede descargar el programa desde el sitio web oficial .
Modelo simple en Minizinc
Consideremos un ejemplo de resolución del modelo, comencemos con un problema criptoaritmético. En este tipo de problema, todas las letras deben reemplazarse por números con dos condiciones:
la igualdad debe sostenerse
el mismo número no debe corresponder a letras diferentes y viceversa.
Por ejemplo, resolvamos la siguiente ecuación:
S E N D
+ M O R E
= M O N E Y
Estructura del modelo
minizinc , . - , , - , , , , , .
, , . , .
- :), .
. 8 (S, E, N, D, M, O, R, Y), , 0 9 (S M 1 9, ).
minizinc :
var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;
, minizinc :
constraint 1000 * S + 100 * E + 10 * N + D
+ 1000 * M + 100 * O + 10 * R + E
== 10000 * M + 1000 * O + 100 * N + 10 * E + Y;
, . Minizinc alldifferent
, , include "alldifferent.mzn";
.
, , , , 3 : (satisfy), (minimize) (maximize) - , , :).
:
include "alldifferent.mzn";
var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;
constraint 1000 * S + 100 * E + 10 * N + D
+ 1000 * M + 100 * O + 10 * R + E
= 10000 * M + 1000 * O + 100 * N + 10 * E + Y;
constraint alldifferent([S,E,N,D,M,O,R,Y]);
solve satisfy;
output [" ",show(S),show(E),show(N),show(D),"\n",
"+ ",show(M),show(O),show(R),show(E),"\n",
"= ",show(M),show(O),show(N),show(E),show(Y),"\n"];
Minizinc :
9567
+ 1085
= 10652
minizinc satisfy , , minizinc , , :).
Minizinc , constraint programming. , .
Python
minizinc-python , minizinc python, minizinc, , - . :
Spoiler
drop-down , - , , .
import minizinc
# Create a MiniZinc model
model = minizinc.Model()
model.add_string("""
var -100..100: x;
int: a; int: b; int: c;
constraint a*(x*x) + b*x = c;
solve satisfy;
""")
# Transform Model into a instance
gecode = minizinc.Solver.lookup("gecode")
inst = minizinc.Instance(gecode, model)
inst["a"] = 1
inst["b"] = 4
inst["c"] = 0
# Solve the instance
result = inst.solve(all_solutions=True)
for i in range(len(result)):
print("x = {}".format(result[i, "x"]))
, minizinc ( 4 ) string, IDE python .
Zython
, , Python?
, zython (miniZinc pYTHON). *.
Spoiler
* ,
* , Python. :)
zython, python 3.6+ minizinc $PATH
.
pip install zython
python
>>> import zython as zn
, . constraint programming zython.
Send More Money
— "Send More Money"
import zython as zn
class MoneyModel(zn.Model):
def __init__(self):
self.S = zn.var(range(1, 10))
self.E = zn.var(range(0, 10))
self.N = zn.var(range(0, 10))
self.D = zn.var(range(0, 10))
self.M = zn.var(range(1, 10))
self.O = zn.var(range(0, 10))
self.R = zn.var(range(0, 10))
self.Y = zn.var(range(0, 10))
self.constraints = [(self.S * 1000 + self.E * 100 + self.N * 10 + self.D +
self.M * 1000 + self.O * 100 + self.R * 10 + self.E ==
self.M * 10000 + self.O * 1000 + self.N * 100 + self.E * 10 + self.Y),
zn.alldifferent((self.S, self.E, self.N, self.D, self.M, self.O, self.R, self.Y))]
model = MoneyModel()
result = model.solve_satisfy()
print(" ", result["S"], result["E"], result["N"], result["D"])
print(" ", result["M"], result["O"], result["R"], result["E"])
print(result["M"], result["O"], result["N"], result["E"], result["Y"])
, .
, . , , , zython , , , , , python. , , . , zython Python , IDE . Zython .
. zn.Array
. , . .
import zython as zn
class MyModel(zn.Model):
def __init__(self):
self.a = zn.Array(zn.var(range(1, 10)), shape=(9, 9))
self.constraints = \
[zn.forall(range(9),
lambda i: zn.alldifferent(self.a[i])),
zn.forall(range(9),
lambda i: zn.alldifferent(self.a[:, i])),
zn.forall(range(3),
lambda i: zn.forall(range(3),
lambda j: zn.alldifferent(self.a[i * 3: i * 3 + 3, j * 3: j * 3 + 3]))),
]
model = MyModel()
result = model.solve_satisfy()
print(result["a"])
, minizinc, :
, , . :
import zython as zn
class TSP(zn.Model):
def __init__(self, distances):
self.distances = zn.Array(distances)
self.path = zn.Array(zn.var(range(len(distances))),
shape=len(distances))
self.cost = (self._cost(distances))
self.constraints = [zn.circuit(self.path)]
def _cost(self, distances):
return (zn.sum(range(1, len(distances)),
lambda i: self.distances[self.path[i - 1],
self.path[i]]) +
self.distances[self.path[len(distances) - 1],
self.path[0]])
distances = [[0, 6, 4, 5, 8],
[6, 0, 4, 7, 6],
[4, 4, 0, 3, 4],
[5, 7, 3, 0, 5],
[8, 6, 4, 5, 0]]
model = TSP(distances)
result = model.solve_minimize(model.cost)
print(result)
, , , .
Constraint programming - , , : , , , , , , , , .
Zython proporciona una forma de expresar el modelo de programación de restricciones en python puro y resolver este problema fácilmente. Puedes ver más ejemplos en la documentación .
Se aprueban críticas constructivas, expresar la opinión de uno en los comentarios, informes de errores, solicitudes de funciones y relaciones públicas.
Buena suerte aprendiendo programación limitada.