Clever Geek Handbook

制約プログラミングまたは単にそれを説明することによって旅行セールスマンの問題を解決する方法

おそらく最も人気のあるプログラミングパラダイムは、必須のプログラミングです。しかし、これだけがプログラミングの種類ではなく、機能的および論理的なプログラミングが広く知られています。制約プログラミングはそれほど人気が​​ありません。しかし、それは組み合わせの問題を解決するための非常に強力なツールです。問題を解決するアルゴリズムを実装してから、デバッグ、リファクタリング、最適化に多くの時間を費やす代わりに、制約プログラミングを使用すると、モデルを特別な構文で簡単に記述でき、特別なプログラム（ソルバー）が解決策を見つけます（またはではない）。印象的ですね。すべてのプログラマーがこの可能性を認識している必要があるように私には思えます。





ミニ亜鉛

おそらく（少なくとも教育目的で）最も一般的に使用される制約プログラミングツールはminizincです。モデルを宣言するためのIDEと、答えを見つけるためのいくつかの組み込みソルバーを提供します。プログラムは公式サイトからダウンロードできます。





Minizincのシンプルなモデル

モデルを解く例を考えてみましょう。暗号算術問題から始めましょう。このタイプの問題では、すべての文字を次の2つの条件の数字に置き換える必要があります。





  • 平等が保たれなければならない





  • 同じ番号が異なる文字に対応していてはならず、その逆も同様です。





たとえば、次の方程式を解いてみましょう。





    S E N D
+   M O R E
= M O N E Y

モデル構造

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は、制約プログラミングモデルを純粋なPythonで表現し、この問題を簡単に解決する方法を提供します。ドキュメントで他の例を見ることができます。





コメント、バグレポート、機能リクエスト、PRで自分の意見を表明する建設的な批判が承認されます。





制約のあるプログラミングを学ぶ幸運。







More articles:


All Articles