原文：
towardsdatascience.com/nucs-7b260afc2fe4?source=collection_archive---------11-----------------------#2024-11-22
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/495306191bc8964f9fe64b4124ca060f.png
照片来自 Eric Prouzet 在 Unsplash
纯 Python 的极速约束求解
https://medium.com/@yangeorget?source=post_page---byline--7b260afc2fe4--------------------------------https://towardsdatascience.com/?source=post_page---byline--7b260afc2fe4-------------------------------- Yan Georget
·发表于 Towards Data Science ·阅读时间 6 分钟·2024 年 11 月 22 日
–
TLDR
NuCS是一个Python 库，用于求解约束满足和优化问题（CSP 和 COP），是我作为副项目开发的。由于它完全用 Python 编写，NuCS 易于安装，并且可以用几行代码建模复杂问题。NuCS 求解器非常快速，因为它得益于Numpy和Numba的支持。
许多问题都可以形式化为 CSP（约束满足问题）。这也是为什么像 NuCS 这样的约束库对开发者或数据科学家来说非常有帮助。
让我们考虑著名的 N 皇后问题，其要求在一个N x N的棋盘上放置N个皇后，使得它们互不威胁。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/12beb4d111f5e0a9295ba09c194decc5.png
8 皇后问题的解法。来源：Yue Guo
14200个12 皇后问题的解法在不到2 秒的时间内，在一台运行以下程序的 MacBook Pro M2 上被找到：
Python 3.11，
Numpy 2.0.1，
Numba 0.60.0 和
NuCS 3.0.0.
(venv)➜ nucs git:(main)time NUMBA_CACHE_DIR=.numba/cache python-m nucs.examples.queens-n12--log_level=ERROR--processors=6{'ALG_BC_NB':262006,'ALG_BC_WITH_SHAVING_NB':0,'ALG_SHAVING_NB':0,'ALG_SHAVING_CHANGE_NB':0,'ALG_SHAVING_NO_CHANGE_NB':0,'PROPAGATOR_ENTAILMENT_NB':0,'PROPAGATOR_FILTER_NB':2269965,'PROPAGATOR_FILTER_NO_CHANGE_NB':990435,'PROPAGATOR_INCONSISTENCY_NB':116806,'SOLVER_BACKTRACK_NB':131000,'SOLVER_CHOICE_NB':131000,'SOLVER_CHOICE_DEPTH':10,'SOLVER_SOLUTION_NB':14200}NUMBA_CACHE_DIR=.numba/cache python-m nucs.examples.queens-n126.65s user0.53s system422%cpu1.699total什么是约束编程？
约束编程是一种求解组合优化问题的范式。在约束编程中，用户通过声明约束条件来明确可行解的限制，这些约束指定了解决方案所需的属性。求解器结合约束传播和回溯算法来寻找解决方案。
作为示例，以下是使用 NuCS 的魔法序列问题模型（找到一个序列x_0, … x_n-1，使得对于每个i在*[0, n-1]中，x_i是i*在序列中出现的次数）：
classMagicSequenceProblem(Problem):def__init__(self,n:int):super().__init__([(0,n)]*n)foriinrange(n):self.add_propagator((list(range(n))+[i],ALG_COUNT_EQ,[i]))# redundant constraintsself.add_propagator((list(range(n)),ALG_AFFINE_EQ,[1]*n+[n]))self.add_propagator((list(range(n)),ALG_AFFINE_EQ,list(range(n))+[n]))在 NuCS 中，约束被称为传播器。
传播器（这里是ALG_COUNT_EQ）简单地表明x_i是序列中i出现的次数。以下两个ALG_AFFINE_EQ传播器是冗余的，这意味着它们对于 NuCS 找到解并不是必需的，但它们加速了求解过程。
查看文档以获取 NuCS 支持的传播器完整列表。请注意，NuCS 中的大多数传播器是全局（即n元）并实现了最先进的传播算法。
Python
Python 是数据科学家首选的编程语言：它具有简单的语法，日益壮大的社区以及大量的数据科学和机器学习库。
但另一方面，Python 被认为是一种较慢的语言：根据基准测试，它的速度可能比 C 慢 50 到 100 倍。
选择 Python 来开发高性能的约束编程库并非显而易见，但我们将看到，Numpy（高性能计算包）和 Numba（Python 的即时编译）结合使用，极大地提升了性能。
已经有许多尝试在 Python 中编写约束求解器，但这些要么很慢，要么只是封装器，并依赖于用 Java 或 C/C++编写的外部求解器。
Numpy
NumPy将类似 C 和 Fortran 的语言的计算能力带到了 Python 中。
[## NumPy
强大的 N 维数组 NumPy 的向量化、索引和广播概念使其既快速又多功能…
numpy.org](https://numpy.org/?source=post_page-----7b260afc2fe4--------------------------------)
在 NuCS 中，一切都是 Numpy 数组。
这使得可以利用 Numpy 的索引和广播能力，并编写紧凑的传播器，例如Max_i x_i <= y
defcompute_domains_max_leq(domains:NDArray,parameters:NDArray)->int:x=domains[:-1]y=domains[-1]ifnp.max(x[:,MAX])<=y[MIN]:returnPROP_ENTAILMENT y[MIN]=max(y[MIN],np.max(x[:,MIN]))ify[MIN]>y[MAX]:returnPROP_INCONSISTENCYforiinrange(len(x)):x[i,MAX]=min(x[i,MAX],y[MAX])ifx[i,MAX]<x[i,MIN]:returnPROP_INCONSISTENCYreturnPROP_CONSISTENCYNumba
Numba 是一个开源的**即时编译（Just-In-Time）**编译器，它将 Python 和 NumPy 代码的子集转换为快速的机器码。
[## Numba：高性能 Python 编译器
@njit(parallel=True) def simulator(out): # 并行迭代循环 for i in prange(out.shape[0]): out[i] = run_sim()…
numba.pydata.org](https://numba.pydata.org/?source=post_page-----7b260afc2fe4--------------------------------)
在以下示例中，我们找到了12 皇后问题的 14200 个解（请注意，我们在这里使用的是单处理器）。
NUMBA_DISABLE_JIT=1python-m nucs.examples.queens-n12--log_level=ERROR179.89s user0.31s system99%cpu3:00.57total通过启用即时编译（Just-In-Time compilation），我们实现了x60的加速：
NUMBA_CACHE_DIR=.numba/cache python-m nucs.examples.queens-n123.03s user0.06s system99%cpu3.095total为了让 Numba JIT 编译你的代码，你应该：
避免面向对象编程（OOP），
使用支持的类型或 Numpy 数组，
使用 Python 语言的子集，
使用 Numpy 函数的子集。
在 NuCS 中，这些指南已经成功地为以下问题实现：
传播器（参见
nucs.readthedocs.io/en/latest/reference.html#propagators了解在 NuCS 中实现的传播器列表），一致性算法（参见
nucs.readthedocs.io/en/latest/reference.html#consistency-algorithms了解在 NuCS 中实现的一致性算法列表），启发式方法（参见
nucs.readthedocs.io/en/latest/reference.html#heuristics了解在 NuCS 中实现的启发式方法列表）。
得益于 Numpy 和 Numba，NuCS 在性能上与用 Java 或 C/C++编写的解算器相当。
请注意，由于 Python 代码是编译的且结果被缓存，当你第二次运行程序时，性能将显著提高。
示例
NuCS 提供了许多模型，用于经典的约束编程问题，如：
一些加密算术谜题：Alpha，Donald，
平衡不完全区组设计问题，
Golomb 标尺问题，
背包问题，
魔术序列问题，
魔方问题，
准群问题，
n 皇后问题，
舒尔引理问题，
体育赛事调度问题，
数独问题。
其中一些示例需要一些高级技术：
冗余约束，
自定义启发式方法，
自定义一致性算法
大多数这些模型也可以在CSPLib中找到，它是 CSP 相关问题的宝典。
统计与日志记录
在搜索解决方案时，NuCS 还会聚合一些统计数据：
{'ALG_BC_NB':262006,'ALG_BC_WITH_SHAVING_NB':0,'ALG_SHAVING_NB':0,'ALG_SHAVING_CHANGE_NB':0,'ALG_SHAVING_NO_CHANGE_NB':0,'PROPAGATOR_ENTAILMENT_NB':0,'PROPAGATOR_FILTER_NB':2269965,'PROPAGATOR_FILTER_NO_CHANGE_NB':990435,'PROPAGATOR_INCONSISTENCY_NB':116806,'SOLVER_BACKTRACK_NB':131000,'SOLVER_CHOICE_NB':131000,'SOLVER_CHOICE_DEPTH':10,'SOLVER_SOLUTION_NB':14200}在这里我们可以看到：
约束一致性计算了 262006 次，
2268895 个传播器被应用，但其中 990435 次无效，同时发现不一致 116806 次，
共计 131000 次选择和回溯，最大选择深度为 10，
最终，找到了 14200 个解。
通过与模型互动并理解它如何影响统计数据，已被证明是一种非常有用的练习，能够最大化利用 NuCS。
NuCS 还提供了一些基本的日志记录功能。
NUMBA_CACHE_DIR=.numba/cache python-m nucs.examples.golomb-n10--symmetry_breaking--log_level=INFO2024-11-1217:27:45,110-INFO-nucs.solvers.solver-Problem has82propagators2024-11-1217:27:45,110-INFO-nucs.solvers.solver-Problem has45variables2024-11-1217:27:45,110-INFO-nucs.solvers.backtrack_solver-BacktrackSolver uses variable heuristic02024-11-1217:27:45,110-INFO-nucs.solvers.backtrack_solver-BacktrackSolver uses domain heuristic02024-11-1217:27:45,110-INFO-nucs.solvers.backtrack_solver-BacktrackSolver uses consistency algorithm22024-11-1217:27:45,110-INFO-nucs.solvers.backtrack_solver-Choice points stack has a maximal height of1282024-11-1217:27:45,172-INFO-nucs.solvers.backtrack_solver-Minimizing variable82024-11-1217:27:45,644-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:802024-11-1217:27:45,677-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:752024-11-1217:27:45,677-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:732024-11-1217:27:45,678-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:722024-11-1217:27:45,679-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:702024-11-1217:27:45,682-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:682024-11-1217:27:45,687-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:662024-11-1217:27:45,693-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:622024-11-1217:27:45,717-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:602024-11-1217:27:45,977-INFO-nucs.solvers.backtrack_solver-Found a(new)solution:55{'ALG_BC_NB':22652,'ALG_BC_WITH_SHAVING_NB':0,'ALG_SHAVING_NB':0,'ALG_SHAVING_CHANGE_NB':0,'ALG_SHAVING_NO_CHANGE_NB':0,'PROPAGATOR_ENTAILMENT_NB':107911,'PROPAGATOR_FILTER_NB':2813035,'PROPAGATOR_FILTER_NO_CHANGE_NB':1745836,'PROPAGATOR_INCONSISTENCY_NB':11289,'SOLVER_BACKTRACK_NB':11288,'SOLVER_CHOICE_NB':11353,'SOLVER_CHOICE_DEPTH':9,'SOLVER_SOLUTION_NB':10}[1610232634415355]定制化
最后，NuCS 是一个非常开放的平台，几乎可以定制任何内容：
传播器，
一致性算法，
启发式方法，
解算器。
在以下Golomb 标尺示例中，在使用之前注册了一个自定义一致性算法：
consistency_alg_golomb=register_consistency_algorithm(golomb_consistency_algorithm)solver=BacktrackSolver(problem,consistency_alg_idx=consistency_alg_golomb)结论
总结来说，NuCS 是一个功能丰富的约束解算器库。尽管它完全用 Python 编写，但性能非常快，可以应用于广泛的领域：研究、教学和生产。
如果你想参与 NuCS 的开发，欢迎随时在 Github 上联系我！
一些有用的链接，供进一步了解：
源代码：
github.com/yangeorget/nucs文档：
nucs.readthedocs.io/en/latest/index.htmlPip 包：
pypi.org/project/NUCS/
如果你喜欢这篇关于 NuCS 的文章，请拍手50 次！
