ortools系列：約束規劃2
ortools系列：約束規劃2
1. Original-CP求解器
在上一篇文章中，我們講解了ortools的CP-SAT求解器，接下來我們講original-CP求解器。但是需要注意，一般情況下我們優先選擇CP-SAT求解器。
看下面這個例子，這個例子在CP-SAT中也說到過，其實很簡單，有x,y,z三個變數，取值範圍都是[0,1,2]的整數，約束條件是 ，求
x,y,z的所有可能組合。
我們還是看代碼吧。
import sys
from ortools.constraint_solver import pywrapcp
def main():
solver = pywrapcp.Solver("simple_example")
# 定義3個整數變數，指定其取值範圍
num_vals = 3
x = solver.IntVar(0, 2, "x")
y = solver.IntVar(0, 2, "y")
z = solver.IntVar(0, 2, "z")
# 添加約束方程
solver.Add(x != y)
# 調用求解器求解
db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
solver.Solve(db)
print_solution(solver, x, y, z)
def print_solution(solver, x, y, z):
"""為了能列印全部的可行解，需要另外寫一個函數"""
count = 0
while solver.NextSolution(): # NextSolution表示下一個可行解的意思
count += 1
print("x =", x.Value(), "y =", y.Value(), "z =", z.Value())
print("
Number of solutions found:", count)
if __name__ == "__main__":
main()
# 結果如下：
x = 0 y = 1 z = 0
x = 0 y = 1 z = 1
x = 0 y = 1 z = 2
x = 0 y = 2 z = 0
x = 0 y = 2 z = 1
x = 0 y = 2 z = 2
x = 1 y = 0 z = 0
x = 1 y = 0 z = 1
x = 1 y = 0 z = 2
x = 1 y = 2 z = 0
x = 1 y = 2 z = 1
x = 1 y = 2 z = 2
x = 2 y = 0 z = 0
x = 2 y = 0 z = 1
x = 2 y = 0 z = 2
x = 2 y = 1 z = 0
x = 2 y = 1 z = 1
x = 2 y = 1 z = 2
original-CP和CP-SAT的使用區別：
首先是引用模塊不同
# cp-sat
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# original-cp
from ortools.constraint_solver import pywrapcp
solver = pywrapcp.Solver("simple_example")
其次是定義整數變數的方式也不同，因為二者所引用的求解模塊是不同的，說到這裡不得不吐槽一下，既然是在同一個軟體中，為什麼要設計不同的介面呢，明明做的是同一件事情。
# cp-sat
x = model.NewIntVar(0, 2, x)
# original-cp
x = solver.IntVar(0, 2, "x")
調用求解器的方式也不同，
# cp-sat
solver = cp_model.CpSolver()
status = solver.SolveWithSolutionCallback(model, solution_printer)
# original-cp
db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
solver.Solve(db)
我們來看求解器的這兩行代碼：
db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
solver.Solve(db)
求解器的輸入是decision builder(db)(此處應該如何翻譯？)，該db包含了需要求解的變數以及求解器的參數。在這裡我們使用Phase方法來創建一個decision builder，術語Phase表示一個階段的意思，在這個例子中只有一個階段，但是在一些複雜問題中，decision builder是包含多個階段的，所以，求解器可以從一個階段到下一個階段使用不同的搜索策略。
Phase方法有三個參數：
vars：變數數組，在上面的問題中是[x,y,z]IntVarStrategy：選擇下一個未綁定變數來賦值的規則，在本例子中CHOOSE_FIRST_UNBOUND表示，在每一步中，求解器將按照傳遞給Phase方法的變數數組中第一個未綁定變數的出現順序進行選擇。IntValueStrategy：選擇下一個賦值給變數的規則，在本例子中ASSIGN_MIN_VALUE表示，選擇尚未嘗試的變數的最小值，這將按遞增順序分配值。另外一個選項是ASSIGN_MAX_VALUE，剛好是以相反的順序。
上面這一段話有點抽象，官方文檔中也沒有給出太多的例子，先這樣吧，畢竟ortools本身推薦的首選是cp-sat.
2. 參考
ortools-Original-CP-Solver
大家看完記得關注點贊.
推薦閱讀：
