Talvez o paradigma de programação mais popular seja a programação imperativa. Mas este não é o único tipo de programação, a programação funcional e lógica são amplamente conhecidas. A programação de restrições não é tão popular. Mas é uma ferramenta muito poderosa para resolver problemas combinatórios. Em vez de implementar um algoritmo que resolve um problema e, em seguida, gastar muito tempo depurando, refatorando e otimizando-o, a programação de restrição permite que você simplesmente descreva o modelo em uma sintaxe especial e um programa especial (solucionador) encontrará a solução para você (ou dirá se eles não são). Impressionante, não é? Parece-me que todo programador deve estar ciente dessa possibilidade.
Minizinc
Provavelmente, a ferramenta de programação de restrição mais comumente usada (pelo menos para fins educacionais) é o minizinco . Ele fornece um IDE para declarar modelos e vários solucionadores integrados para encontrar uma resposta. Você pode baixar o programa do site oficial .
Modelo simples em Minizinc
Vamos considerar um exemplo de solução do modelo, vamos começar com um problema criptoaritmético. Nesse tipo de problema, todas as letras devem ser substituídas por números com duas condições:
igualdade deve manter
o mesmo número não deve corresponder a letras diferentes e vice-versa.
Por exemplo, vamos resolver a seguinte equação:
S E N D
+ M O R E
= M O N E Y
Estrutura do 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 fornece uma maneira de expressar o modelo de programação de restrição em Python puro e resolver esse problema facilmente. Você pode ver mais exemplos na documentação .
São aprovadas críticas construtivas, expressando sua opinião nos comentários, relatórios de bugs, solicitações de recursos e PR.
Boa sorte ao aprender programação restrita.