python - OR-Tools 和 Python 中的 NoCycle 约束

Question

我正在用 Python 中的 OR-Tools 实现 Knight Tour 问题，但我正在努力解决无循环约束。在 C++ 中，存在 MakeNoCycle 全局约束，我假设在 Python 包装器中，与此等效的是 TreeNoCycle 约束。

到目前为止我拥有的简化代码(我从一些损坏的示例中复制了 TreeNoCycle 部分):

# side length of board
n = 5

# where the knight jumps to from field i, starting at 0, ending at n*n
jump_to = [solver.IntVar(1, n*n) for i in range(n*n)]

# snip other constraints

# the no cycle constraint
active = [solver.IntVar(1, 1) for i in range(dim * dim)]
for t in active:
    solver.Add(t == 1)
solver.Add(solver.TreeNoCycle(jump_to, active, lambda: None))

执行时，最后一部分出现以下错误:

python3.6/site-packages/ortools/constraint_solver/pywrapcp.py", line 337, in NextSolution return _pywrapcp.Solver_NextSolution(self) SystemError: returned a result with an error set

我的代码的其余部分有效，即当我省略具有 TreeNoCycle 约束的部分时，我得到了许多解决方案，但有些解决方案具有断开连接的图形。

我的假设是否正确，即 TreeNoCycle 是 MakeNoCycle 的 Python 方法？如果是，我如何正确使用TreeNoCycle？如果。如果我不能使用 TreeNoCycle，有什么想法如何以不同的方式实现它？

Answer 1

请使用 CP-SAT 求解器。

请注意，在这种情况下，建模应该有点不同，因为电路约束采用 bool 文字( bool 变量或其否定)标记的图形。 您不需要整数变量。

一些文档:

https://github.com/google/or-tools/tree/stable/ortools/sat/doc

https://developers.google.com/optimization/cp/cp_solver#cp-sat_example

和 python 示例(查找 _sat.py 后缀):

https://github.com/google/or-tools/tree/stable/examples/python