Mungkin paradigma pemrograman yang paling populer adalah pemrograman imperatif. Tetapi ini bukan satu-satunya jenis pemrograman, pemrograman fungsional dan logis yang dikenal luas. Constraint Programming tidak begitu populer. Tapi itu adalah alat yang sangat ampuh untuk memecahkan masalah kombinatorial. Alih-alih menerapkan algoritme yang memecahkan masalah, dan kemudian menghabiskan banyak waktu untuk men-debug, memfaktorkan ulang, dan mengoptimalkannya, pemrograman batasan memungkinkan Anda mendeskripsikan model dalam sintaks khusus, dan program khusus (pemecah) akan menemukan solusi untuk Anda (atau memberi tahu jika mereka tidak). Mengesankan, bukan? Menurut saya, setiap programmer harus menyadari kemungkinan ini.
Minizinc
Mungkin alat pemrograman kendala yang paling umum digunakan (setidaknya untuk tujuan pendidikan) adalah minizinc . Ini menyediakan IDE untuk mendeklarasikan model dan beberapa pemecah bawaan untuk menemukan jawaban. Anda dapat mengunduh program dari situs resminya .
Model sederhana di Minizinc
Mari kita pertimbangkan contoh pemecahan model, mari kita mulai dengan masalah kriptoaritmatika. Dalam jenis soal ini, semua huruf harus diganti dengan angka dengan dua syarat:
kesetaraan harus dipegang
nomor yang sama tidak boleh sesuai dengan huruf yang berbeda dan sebaliknya.
Misalnya, ayo selesaikan persamaan berikut:
S E N D
+ M O R E
= M O N E Y
Struktur model
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 menyediakan cara untuk mengekspresikan model pemrograman kendala dalam python murni dan menyelesaikan masalah ini dengan mudah. Anda dapat melihat lebih banyak contoh di dokumentasi .
Kritik yang membangun, mengutarakan pendapat di komentar, laporan bug, permintaan fitur dan PR disetujui.
Selamat mencoba belajar pemrograman terkendala.