Le paradigme de programmation le plus populaire est peut-être la programmation impérative. Mais ce n'est pas le seul type de programmation, la programmation fonctionnelle et logique est largement connue. La programmation par contraintes n'est pas si populaire. Mais c'est un outil très puissant pour résoudre des problèmes combinatoires. Au lieu d'implémenter un algorithme qui résout un problème, puis de passer beaucoup de temps à le déboguer, à le refactoriser et à l'optimiser, la programmation par contraintes vous permet de décrire simplement le modèle dans une syntaxe spéciale, et un programme spécial (solveur) trouvera la solution pour vous (ou vous dira si ils ne sont pas). Impressionnant, non? Il me semble que chaque programmeur devrait être conscient de cette possibilité.
Minizinc
L'outil de programmation par contraintes le plus couramment utilisé (au moins à des fins éducatives) est le minizinc . Il fournit un IDE pour déclarer les modèles et plusieurs solveurs intégrés pour trouver une réponse. Vous pouvez télécharger le programme sur le site officiel .
Modèle simple dans Minizinc
Prenons un exemple de résolution du modèle, commençons par un problème cryptoarithmétique. Dans ce type de problème, toutes les lettres doivent être remplacées par des nombres avec deux conditions:
l'égalité doit tenir
le même numéro ne doit pas correspondre à des lettres différentes et vice versa.
Par exemple, résolvons l'équation suivante:
S E N D
+ M O R E
= M O N E Y
Structure du modèle
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 fournit un moyen d'exprimer un modèle de programmation par contraintes en python pur et de résoudre ce problème facilement. Vous pouvez voir plus d'exemples dans la documentation .
La critique constructive, l'expression de son opinion dans les commentaires, les rapports de bogues, les demandes de fonctionnalités et les relations publiques sont approuvés.
Bonne chance pour apprendre la programmation contrainte.