Resolución de restricciones ultrarrápida en Python puro
nucs es un biblioteca de pitón para resolver problemas de satisfacción y optimización de restricciones (CSP y COP) que desarrollo como proyecto paralelo. Debido a que está 100% escrito en Python, NuCS es fácil de instalar y permite modelar problemas complejos en unas pocas líneas de código. El solucionador NuCS también es muy rápido porque funciona con numpy Y numba.
Muchos problemas pueden formularse como CSP. Es por eso que una biblioteca de restricciones como NuCS puede beneficiar a muchos desarrolladores o científicos de datos.
Consideremos el famoso problema de N-reinas que consiste en colocar norte reinas en un NxN un tablero de ajedrez tal que las reinas no se amenacen entre sí.
EL 14200 soluciones a 12 reinas los problemas se encuentran en menos de 2s en una MacBook Pro M2 ejecutando:
- Pitón 3.11,
- Numerosos 2.0.1,
- Número 0.60.0 y
- NuCS3.0.0.
(venv) ➜ nucs git:(main) time NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 --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 -n 12 6.65s user 0.53s system 422% cpu 1.699 total
Programación de restricciones es un paradigma para la resolución de problemas combinatorios. En la programación de restricciones, los usuarios declaran restricciones sobre soluciones factibles para un conjunto de variables de decisión. Las restricciones especifican las propiedades de una solución que se va a encontrar. El solucionador combina la propagación de restricciones y el retroceso para encontrar soluciones.
Como ejemplo, aquí hay un modelo para el Problema de secuencia mágica (encontrar una secuencia x_0,… x_n-1 para que, para cada I En [0, n-1], x_i es el número de ocurrencias de I en secuencia) usando NuCS:
class MagicSequenceProblem(Problem):
def __init__(self, n: int):
super().__init__([(0, n)] * n)
for i in range(n):
self.add_propagator((list(range(n)) + [i], ALG_COUNT_EQ, [i]))
# redundant constraints
self.add_propagator((list(range(n)), ALG_AFFINE_EQ, [1] * n + [n]))
self.add_propagator((list(range(n)), ALG_AFFINE_EQ, list(range(n)) + [n]))
En NuCS, una restricción se llama propagador.
El propagador (aquí ALG_COUNT_EQ) simplemente indica que x_i es el número de ocurrencias de I en la secuencia. Los dos siguientes ALG_AFFINE_EQ Los propagadores son redundantes, lo que significa que NuCS no los necesita para encontrar la solución, pero aceleran el proceso de solución.
Ver los documentos para obtener una lista completa de propagadores admitidos por NuCS. Tenga en cuenta que la mayoría de los propagadores en NuCS son global (alias norte-ario) e implementar lo último algoritmos de propagación.
Python es el lenguaje elegido por los científicos de datos: tiene una sintaxis simple, una comunidad en crecimiento y una gran cantidad de bibliotecas de ciencia de datos y aprendizaje automático.
Pero, por otro lado, Python es conocido por ser un lenguaje lento: quizás entre 50 y 100 veces más lento que C según los puntos de referencia.
La elección de Python para desarrollar una biblioteca de programación de restricciones de alto rendimiento no fue tan obvia pero veremos que el uso combinado de Numpy (paquete de computación de alto rendimiento) y Numba (compilación Just-In-Time para Python) ayuda mucho.
Se han hecho muchos intentos de escribir solucionadores de restricciones en Python, pero son lentos o solo embalaje y depender de externo solucionadores escritos en Java o C/C++.
NumPy trae la potencia informática de lenguajes como C y Fortran a Python.
En NuCS todo es una matriz Numpy.
Esto hace posible explotar las capacidades de indexación y transmisión de Numpy y escribir propagadores compactos como Max_i x_i <= y
def compute_domains_max_leq(domains: NDArray, parameters: NDArray) -> int:
x = domains[:-1]
y = domains[-1]
if np.max(x[:, MAX]) <= y[MIN]:
return PROP_ENTAILMENT
y[MIN] = max(y[MIN], np.max(x[:, MIN]))
if y[MIN] > y[MAX]:
return PROP_INCONSISTENCY
for i in range(len(x)):
x[i, MAX] = min(x[i, MAX], y[MAX])
if x[i, MAX] < x[i, MIN]:
return PROP_INCONSISTENCY
return PROP_CONSISTENCY
Numba es un software de código abierto Justo a tiempo compilador que traduce un subconjunto de código Python y NumPy en código de máquina rápido.
En el siguiente ejemplo, encontramos las 14200 soluciones de 12 reinas problemas (tenga en cuenta que aquí estamos usando un solo procesador).
NUMBA_DISABLE_JIT=1 python -m nucs.examples.queens -n 12 --log_level=ERROR 179.89s user 0.31s system 99% cpu 3:00.57 total
Llegamos a un x60 acelere habilitando la compilación justo a tiempo:
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 3.03s user 0.06s system 99% cpu 3.095 total
Para permitir que Numba JIT compile su código, debe:
- evitar la programación orientada a objetos,
- utilizar tipos compatibles o matrices Numpy,
- utilizar un subconjunto del lenguaje Python,
- utilice un subconjunto de las funciones de Numpy.
En NuCS, estas directrices se han implementado con éxito para:
Gracias a Numpy y Numba, NuCS logra un rendimiento similar al de los solucionadores escritos en Java o C/C++.
Tenga en cuenta que debido a que el código Python se compila y el resultado se almacena en caché, el rendimiento siempre será significativamente mejor cuando ejecute su programa por segunda vez.
NuCS viene con muchos modelos para problemas clásicos de programación con restricciones como:
- algunos acertijos criptoaritméticos: Alfa, donald,
- EL Diseño de bloques incompletos equilibrados. asunto,
- EL Regla de Golomb asunto,
- EL mochila asunto,
- EL secuencia magicael problema,
- EL cuadrado magico asunto,
- EL cuasigrupo asunto,
- EL n-reinas asunto,
- EL Lema de Schur asunto,
- EL programación de torneos deportivos asunto,
- EL Sudokus asunto.
Algunos de estos ejemplos requieren técnicas avanzadas:
- restricciones redundantes,
- heurística personalizada,
- algoritmos de consistencia personalizados
La mayoría de estos modelos también están disponibles en CSPLibla biblia de todo lo relacionado con CSP.
Cuando se buscan soluciones, NuCS también reúne algunas estadística:
{
'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
}
Aquí podemos ver que:
- la consistencia ligada se calculó 262006 veces,
- Se aplicaron 2268895 propagadores pero sin efecto 990435 veces mientras que se detectaron inconsistencias 116806 veces.
- había 131.000 opciones y retrocesos, con una profundidad máxima de elección de 10,
- al final se encontraron 14.200 soluciones.
Jugar con el modelo y comprender cómo afecta a las estadísticas resultó ser un ejercicio muy útil para aprovechar al máximo NuCS.
NuCS también viene con capacidades básicas de registro.
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.golomb -n 10 --symmetry_breaking --log_level=INFO
2024-11-12 17:27:45,110 - INFO - nucs.solvers.solver - Problem has 82 propagators
2024-11-12 17:27:45,110 - INFO - nucs.solvers.solver - Problem has 45 variables
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses variable heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses domain heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses consistency algorithm 2
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - Choice points stack has a maximal height of 128
2024-11-12 17:27:45,172 - INFO - nucs.solvers.backtrack_solver - Minimizing variable 8
2024-11-12 17:27:45,644 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 80
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 75
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 73
2024-11-12 17:27:45,678 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 72
2024-11-12 17:27:45,679 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 70
2024-11-12 17:27:45,682 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 68
2024-11-12 17:27:45,687 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 66
2024-11-12 17:27:45,693 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 62
2024-11-12 17:27:45,717 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 60
2024-11-12 17: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
}
[ 1 6 10 23 26 34 41 53 55]
Finalmente, NuCS es una plataforma muy abierta donde se puede personalizar casi todo:
- propagadores,
- algoritmos de consistencia,
- heurística,
- solucionadores.
En lo que sigue Regla de Golomb Por ejemplo, un algoritmo de coherencia personalizado se guarda antes de utilizarlo:
consistency_alg_golomb = register_consistency_algorithm(golomb_consistency_algorithm)
solver = BacktrackSolver(problem, consistency_alg_idx=consistency_alg_golomb)
En conclusión, NuCS es una biblioteca de solución de restricciones rica en funciones. Aunque está escrito íntegramente en Python, es muy rápido y puede utilizarse para una amplia gama de aplicaciones: investigación, enseñanza y producción.
¡No dudes en contactarme en Github si deseas participar en el desarrollo de NuCS!
Algunos enlaces útiles para ir más allá:
Si te ha gustado este artículo sobre NuCS, aplaude 50 veces!
