Breaking

Post Top Ad

Your Ad Spot

viernes, 14 de junio de 2019

Programación de restricciones con restricción de python

Introducción

Lo primero que tenemos que entender al tratar con la programación de restricciones es que la forma de pensar es muy diferente de nuestra forma habitual de pensar cuando nos sentamos a escribir código.
La programación de restricciones es un ejemplo del paradigma de programación declarativa , en oposición al paradigma imperativo habitual que usamos la mayor parte del tiempo.
¿Qué es un paradigma de programación?
Un paradigma significa "un ejemplo" o "un patrón" de algo. Un paradigma de programación a menudo se describe como una "forma de pensar" o "forma de programación". Los ejemplos más comunes incluyen la programación de procedimientos. (por ejemplo, C), programación orientada a objetos (por ejemplo, Java) y programación funcional (por ejemplo, Haskell).
La mayoría de los paradigmas de programación se pueden clasificar como miembros del imperativo o del grupo de paradigmas declarativos.
¿Cuál es la diferencia entre programación imperativa y declarativa?
  • La programación imperativa , en pocas palabras, se basa en el desarrollador que describe la solución / algoritmo para lograr un objetivo (algún tipo de resultado). Esto sucede al cambiar el estado del programa a través de las instrucciones de asignación, mientras se ejecutan las instrucciones paso a paso. Por lo tanto, hace una gran diferencia en el orden en que se escriben las instrucciones.
  • La programación declarativa hace lo contrario: no escribimos los pasos sobre cómo lograr un objetivo, describimos el objetivo y la computadora nos da una solución. Un ejemplo común con el que deberías estar familiarizado es SQL. ¿Le dice a la computadora cómo darle los resultados que necesita? No, usted describe lo que necesita: necesita los valores de alguna columna, de alguna tabla, donde se cumplen algunas condiciones.

Instalación del módulo de restricción de python

En este artículo trabajaremos con un módulo llamado. python-constraint (Nota: hay un módulo llamado "restricción" para Python, que no es lo que queremos), cuyo objetivo es llevar la idea de programación de restricciones a Python.
Para instalar este módulo, abra el terminal y ejecute:
$ pip install python-constraint

Conceptos básicos del uso de la restricción de Python

Este es el esqueleto generalizado de los programas escritos usando este módulo (Nota: usamos import constrainty no import python-constraint)
  • importar constraint
  • Definir una variable como nuestro problema.
  • Añadir variables y sus respectivos intervalos a nuestro problema.
  • añadir restricciones integradas / personalizadas a nuestro problema
  • buscar las soluciones
  • Ir a través de las soluciones para encontrar las que necesitamos.
Como se mencionó anteriormente, la programación restringida es una forma de programación declarativa. El orden de las declaraciones no importa, siempre y cuando todo esté allí al final. Generalmente se usa para resolver problemas como este:
Ejemplo A
Find all (x,y) where x ∈ {1,2,3} and 0 <= y < 10, and x + y >= 5  
Si nos fijamos en esta frase, podemos ver una serie de condiciones (llamémosles limitaciones) que xytienen que cumplir.
Por ejemplo, xestá "restringido" a los valores 1,2,3ytiene que ser menor que 10y su suma debe ser mayor o igual que 5Esto se hace en unas pocas líneas de código y en unos pocos minutos utilizando la programación de restricciones.
Viendo el problema anterior, probablemente pensó "¿Y qué? Puedo hacer esto con 2 para bucles y media taza de café en Python en menos de 10 minutos".
Tienes toda la razón, aunque a través de este ejemplo podemos tener una idea de cómo se ve la programación de restricciones:
import constraint

problem = constraint.Problem()

problem.addVariable('x', [1,2,3])  
problem.addVariable('y', range(10))

def our_constraint(x, y):  
    if x + y >= 5:
        return True

problem.addConstraint(our_constraint, ['x','y'])

solutions = problem.getSolutions()

# Easier way to print and see all solutions
# for solution in solutions:
#    print(solution)

# Prettier way to print and see all solutions
length = len(solutions)  
print("(x,y) ∈ {", end="")  
for index, solution in enumerate(solutions):  
    if index == length - 1:
        print("({},{})".format(solution['x'], solution['y']), end="")
    else:
        print("({},{}),".format(solution['x'], solution['y']), end="")
print("}")  
Salida:
(x,y) ∈ {(3,9),(3,8),(3,7),(3,6),(3,5),(3,4),(3,3),(3,2),(2,9),(2,8),(2,7),(2,6),(2,5),(2,4),(2,3),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4)}
Vayamos a través de este programa paso a paso. Teníamos dos variables, xyLos hemos agregado a nuestro problema con sus respectivos rangos aceptables.
Esas dos líneas significan lo siguiente:
I'm adding a variable x that can only have values [1,2,3], and a variable y that can only have values [1,2,..,9]  
A continuación definimos nuestra restricción personalizada (es decir, x + y >= 5). Se supone que los métodos de restricción regresan Truesi una combinación de valores variables es aceptable, y Nonesi no lo es.
En nuestro our_constraint()método, decimos que "la única situación aceptable es cuando x + y >= 5, de lo contrario, no se incluyen esos valores (x,y)en las soluciones finales".
Después de definir nuestra restricción, debemos agregarla a nuestro problema. La estructura del .addConstraint()método es:
addConstraint(which_constraint, list_of_variable_order)  
Nota : en nuestro caso, no importa si escribimos [x,y][y,x]como nuestro segundo parámetro, pero el orden sí importa en la mayoría de los casos.
Después de eso, buscamos las soluciones con problem.getSolutions()(devuelve una lista de todas las combinaciones de valores variables que satisfacen todas las condiciones) y las repasamos.
Nota : Si, por ejemplo, quisiéramos buscar solo combinaciones donde x /= y, agregaríamos una restricción incorporada antes de buscar las soluciones:
problem.addConstraint(constraint.AllDifferentConstraint())  
Puede encontrar la lista de todas las restricciones incorporadas aquí . Eso es casi todo lo que necesita saber para poder realizar cualquier tarea de este tipo.

Ejemplos de calentamiento

Ejemplo B
Aquí es divertido usar un tipo de restricción de problemas en la programación, llamado rompecabezas cryptarithmetic . En la siguiente forma de rompecabezas cryptarithmetic, cada carácter representa un dígito diferente (los caracteres principales no pueden ser 0):
TWO + TWO = FOUR  
Piensa en cómo resolverías esto usando Python regular. De hecho, lo aliento a buscar la solución para este problema que utiliza la programación imperativa.
También debe proporcionarle todo el conocimiento que necesita para resolver el Ejemplo D por su cuenta.
Tenga en cuenta que 'T' y 'F' no pueden ser cero ya que son los caracteres principales, es decir, el primer dígito en un número.
import constraint

problem = constraint.Problem()

# We're using .addVariables() this time since we're adding
# multiple variables that have the same interval.
# Since Strings are arrays of characters we can write
# "TF" instead of ['T','F'].
problem.addVariables("TF", range(1, 10))  
problem.addVariables("WOUR", range(10))

# Telling Python that we need TWO + TWO = FOUR
def sum_constraint(t, w, o, f, u, r):  
    if 2*(t*100 + w*10 + o) == f*1000 + o*100 + u*10 + r:
        return True

# Adding our custom constraint. The
# order of variables is important!
problem.addConstraint(sum_constraint, "TWOFUR")

# All the characters must represent different digits,
# there's a built-in constraint for that
problem.addConstraint(constraint.AllDifferentConstraint())

solutions = problem.getSolutions()  
print("Number of solutions found: {}\n".format(len(solutions)))

# .getSolutions() returns a dictionary
for s in solutions:  
    print("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}"
        .format(s['T'], s['W'], s['O'], s['F'], s['U'], s['R']))
Ejecutando este fragmento de código, nos encontramos con las posibles soluciones:
Number of solutions found: 7

T = 7, W = 6, O = 5, F = 1, U = 3, R = 0  
T = 7, W = 3, O = 4, F = 1, U = 6, R = 8  
T = 8, W = 6, O = 7, F = 1, U = 3, R = 4  
T = 8, W = 4, O = 6, F = 1, U = 9, R = 2  
T = 8, W = 3, O = 6, F = 1, U = 7, R = 2  
T = 9, W = 2, O = 8, F = 1, U = 5, R = 6  
T = 9, W = 3, O = 8, F = 1, U = 7, R = 6  
Ejemplo C
You recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are just SO many ways to give someone their change back! Your "friend" shakes his head, obviously not believing you. He says "It can't be that bad. How many ways can there POSSIBLY be to give someone their change back, for like 60 cents?".

Your response is, of course, to sit and quickly write a program that would prove your point. You have a decent amount of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), and a lot of kinda suspicious coins worth 3 cents each. Calculate in how many ways you can return change for 60 cents.  
Nota : El orden en que se imprime nuestro resultado no es necesariamente el mismo en el que hemos agregado las variables. Es decir, si el resultado es ( a,b,c,d,e) no sabemos si tenemos amonedas de 1 centavo,b de 3 centavos, etc.
Entonces deberíamos imprimir explícitamente la variable y su valor. Una consecuencia de esto es que no podemos utilizar el built-in .ExactSumConstraint()en su forma de dos parámetros, ExactSumConstraint(50,[1,3,5,10,20]).
El segundo parámetro aquí es el "peso" de cada variable (cuántas veces se debe multiplicar), y no tenemos ninguna garantía de cuál de nuestras variables tendrá qué peso.
Es un error común asumir que los pesos se asignarán a las variables en el orden en que se agregaron las variables, en lugar de eso, usamos la forma de tres parámetros de esta restricción incorporada en el código a continuación:
import constraint

problem = constraint.Problem()

# The maximum amount of each coin type can't be more than 60
# (coin_value*num_of_coints) <= 60

problem.addVariable("1 cent", range(61))  
problem.addVariable("3 cent", range(21))  
problem.addVariable("5 cent", range(13))  
problem.addVariable("10 cent", range(7))  
problem.addVariable("20 cent", range(4))

problem.addConstraint(  
    constraint.ExactSumConstraint(60,[1,3,5,10,20]),
    ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"]
)
# Where we explicitly give the order in which the weights should be allocated

# We could've used a custom constraint instead, BUT in this case the program will
# run slightly slower - this is because built-in functions are optimized and
# they find the solution more quickly
# def custom_constraint(a, b, c, d, e):
#     if a + 3*b + 5*c + 10*d + 20*e == 60:
#         return True
#     problem.addConstraint(o, ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"])


# A function that prints out the amount of each coin
# in every acceptable combination
def print_solutions(solutions):  
    for s in sols:
        print("---")
        print("""
        1 cent: {0:d}
        3 cent: {1:d}
        5 cent: {2:d}
        10 cent: {3:d}
        20 cent: {4:d}""".format(s["1 cent"], s["3 cent"], s["5 cent"], s["10 cent"], s["20 cent"]))
        # If we wanted to we could check whether the sum was really 60
        # print("Total:", s["1 cent"] + s["3 cent"]*3 + s["5 cent"]*5 + s["10 cent"]*10 + s["20 cent"]*20)
        # print("---")

solutions = problem.getSolutions()  
#print_solutions(solutions)
print("Total number of ways: {}".format(len(solutions)))  
Ejecutar este fragmento de código dará como resultado:
Total number of ways: 535  
Ejemplo D
CRASH + ERROR + REBOOT = HACKER  
Los ejemplos B y D son casi idénticos cuando se usan restricciones, solo unas pocas variables hacia arriba y hacia abajo y restricciones más detalladas. Eso es algo bueno sobre la programación de restricciones: buena escalabilidad, al menos cuando se trata de tiempo dedicado a la codificación. Solo hay una solución para este rompecabezas y es A = 3 B = 7 C = 8 E = 2 H = 6 K = 0 O = 1 R = 5 S = 9 T = 4.
Ambos tipos de tareas (especialmente la criptaritmética) se usan más por diversión y para demostrar fácilmente cómo funciona la programación de restricciones, pero hay ciertas situaciones en las que la programación de restricciones tiene un valor práctico.
Podemos calcular el número mínimo de estaciones de transmisión para cubrir un área determinada, o averiguar cómo configurar los semáforos para que el flujo de tráfico sea óptimo. En términos generales, las restricciones se utilizan cuando hay muchas combinaciones posibles.
Estos ejemplos son demasiado complejos para el alcance de este artículo, pero sirven para mostrar que la programación de restricciones puede tener usos en el mundo real.

Ejemplos más difíciles

Ejemplo E
You wish to pack chocolates for your mother. Luckily you work in a chocolate factory that has a lot of leftover chocolate. You have a few chocolate types at your disposal.

Your goal is to bring her the sweetest chocolate possible, that you can pack in your bag and sneak through security, and that wouldn't pass a certain net value for which you'd go to prison if you got caught.

Security most likely won't get suspicious if you bring less than 3kg. You can fit 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $200 worth of chocolate.  
Nombre de chocolatePeso (gramos)Dimensiones (cm)DulzuraValor ($)
Chocolate a1008 × 2.5 × 0.5208
Chocolate b457 × 2 × 0.5dieciséis6.8
Chocolate c103 × 2 × 0.594
Chocolate D253 × 3 × 0.573
Ahora arremangémonos y comencemos. No debería ser demasiado difícil si has entendido los ejemplos anteriores.
Primero descubriremos cuánto de cada chocolate podemos tener si SOLAMENTE trajimos ese tipo, para que podamos tener el límite superior de nuestros intervalos. Por ejemplo, para el Chocolate A, en función del peso, podemos aportar a lo sumo 30 barras, en función del valor que podemos aportar como máximo 37, y en función del volumen podemos aportar 100.
El más pequeño de estos números es 30, y ese es el número máximo de Chocolate A que podemos traer. Los mismos pasos nos dan la cantidad máxima del resto, B -> 44, C -> 75, D -> 100 .
import constraint

problem = constraint.Problem()

problem.addVariable('A', range(31))  
problem.addVariable('B', range(45))  
problem.addVariable('C', range(76))  
problem.addVariable('D', range(101))

# We have 3kg = 3,000g available
def weight_constraint(a, b, c, d):  
    if (a*100 + b*45 + c*10 + d*25) <= 3000:
        return True

# We have 1dm^3 = 1,000cm^3 available
def volume_constraint(a, b, c, d):  
    if (a*8*2.5*0.5 + b*6*2*0.5 * c*2*2*0.5 + d*3*3*0.5) <= 1000:
        return True

# We can't exceed $200
def value_constraint(a, b, c, d):  
    if (a*8 + b*6.8 + c*4 + d*3) < 300:
        return True

problem.addConstraint(weight_constraint, "ABCD")  
problem.addConstraint(volume_constraint, "ABCD")  
problem.addConstraint(value_constraint, "ABCD")

maximum_sweetness = 0  
solution_found = {}  
solutions = problem.getSolutions()

for s in solutions:  
    current_sweetness = s['A']*10 + s['B']*8 + s['C']*4.5 + s['D']*3.5
    if current_sweetness > maximum_sweetness:
        maximum_sweetness = current_sweetness
        solution_found = s

print("""  
The maximum sweetness we can bring is: {}  
We'll bring:  
{} A Chocolates,
{} B Chocolates,
{} C Chocolates,
{} D Chocolates
""".format(maximum_sweetness, solution_found['A'], solution_found['B'], solution_found['C'], solution_found['D']))
Ejecutar este fragmento de código dará como resultado:
The maximum sweetness we can bring is: 365.0  
We'll bring:  
27 A Chocolates,  
2 B Chocolates,  
16 C Chocolates,  
2 D Chocolates  
Nota : Podemos almacenar toda la información relevante para cada tipo de chocolate en un diccionario, por ejemplo weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25}, y acceder a los valores de esa manera, en lugar de codificarlos en funciones. Sin embargo, en aras de la legibilidad, la longitud del código y el enfoque en las cosas más importantes para este tutorial, prefiero codificar las funciones de restricción en sí mismas.
Nota : Probablemente notó que tomó un tiempo calcular el resultado, esto es un inconveniente de la programación de restricciones.
Ejemplo F
Ahora, para algo más divertido: hagamos un solucionador de sudoku (clásico 9x9). Leeremos el rompecabezas de un archivo JSON y encontraremos todas las soluciones para ese rompecabezas en particular (asumiendo que el rompecabezas tiene una solución).
Si olvidaste las reglas para resolver sudoku:
  • Las celdas pueden tener valores 1 - 9.
  • Todas las celdas en la misma fila deben tener valores diferentes
  • Todas las celdas en la misma columna deben tener valores diferentes
  • Todas las celdas en un cuadrado de 3x3 (nueve en total) deben tener valores diferentes
Uno de los problemas en este programa es: ¿cómo almacenamos los valores? No podemos simplemente agregar una matriz como variable a nuestro problema y hacer que Python descubra mágicamente lo que queremos.
Vamos a utilizar un sistema en el que trataremos los números como nombres de variables (eso está permitido) y simularemos que tenemos una matriz. Los índices comienzan desde (1,1) en lugar de los habituales (0,0). Usando eso, accederemos a los elementos del tablero de la manera en que estamos acostumbrados.
A continuación, debemos hacer la parte fácil de decirle a Python que todas esas celdas pueden tener valores entre 1 y 9.
Luego notamos que las celdas en la misma fila tienen el mismo primer índice, por ejemplo (1, x) para la primera fila. Podemos iterar fácilmente a través de todas las filas y decir que todas las celdas tienen que contener valores diferentes. Lo mismo ocurre con las columnas. El resto es más fácil de entender cuando se mira el código.
Echemos un vistazo a un archivo JSON de ejemplo:
[[0, 9, 0, 7, 0, 0, 8, 6, 0],
 [0, 3, 1, 0, 0, 5, 0, 2, 0],
 [8, 0, 6, 0, 0, 0, 0, 0, 0],
 [0, 0, 7, 0, 5, 0, 0, 0, 6],
 [0, 0, 0, 3, 0, 7, 0, 0, 0],
 [5, 0, 0, 0, 1, 0, 7, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 9],
 [0, 2, 0, 6, 0, 0, 0, 5, 0],
 [0, 5, 4, 0, 0, 8, 0, 7, 0]]
# 1 - - - - - - - - -
# 2 - - - - - - - - -
# 3 - - - - - - - - -
# 4 - - - - - - - - -
# 5 - - - - - - - - -
# 6 - - - - - - - - -
# 7 - - - - - - - - -
# 8 - - - - - - - - -
# 9 - - - - - - - - -
#   1 2 3 4 5 6 7 8 9

import constraint  
import json

problem = constraint.Problem()

# We're letting VARIABLES 11 through 99 have an interval of [1..9]
for i in range(1, 10):  
    problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))

# We're adding the constraint that all values in a row must be different
# 11 through 19 must be different, 21 through 29 must be all different,...
for i in range(1, 10):  
    problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))

# Also all values in a column must be different
# 11,21,31...91 must be different, also 12,22,32...92 must be different,...
for i in range(1, 10):  
    problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))

# The last rule in a sudoku 9x9 puzzle is that those nine 3x3 squares must have all different values,
# we start off by noting that each square "starts" at row indices 1, 4, 7
for i in [1,4,7]:  
    # Then we note that it's the same for columns, the squares start at indices 1, 4, 7 as well
    # basically one square starts at 11, the other at 14, another at 41, etc
    for j in [1,4,7]:
        square = [10*i+j,10*i+j+1,10*i+j+2,10*(i+1)+j,10*(i+1)+j+1,10*(i+1)+j+2,10*(i+2)+j,10*(i+2)+j+1,10*(i+2)+j+2]
        # As an example, for i = 1 and j = 1 (bottom left square), the cells 11,12,13,
        # 21,22,23, 31,32,33 have to be all different
        problem.addConstraint(constraint.AllDifferentConstraint(), square)

file_name = input("Enter the name of the .json file containing the sudoku puzzle: ")  
try:  
    f = open(file_name, "r")
    board = json.load(f)
    f.close()
except IOError:  
    print ("Couldn't open file.")
    sys.exit()

# We're adding a constraint for each number on the board (0 is an "empty" cell),
# Since they're already solved, we don't need to solve them
for i in range(9):  
    for j in range(9):
        if board[i][j] != 0:
            def c(variable_value, value_in_table = board[i][j]):
                if variable_value == value_in_table:
                    return True

            # Basically we're making sure that our program doesn't change the values already on the board
            # By telling it that the values NEED to equal the corresponding ones at the base board
            problem.addConstraint(c, [((i+1)*10 + (j+1))])

solutions = problem.getSolutions()

for s in solutions:  
    print("==================")
    for i in range(1,10):
        print("|", end='')
        for j in range(1,10):
            if j%3 == 0:
                print(str(s[i*10+j])+" | ", end='')
            else:
                print(str(s[i*10+j]), end='')
        print("")
        if i%3 == 0 and i!=9:
            print("------------------")
    print("==================")

if len(solutions) == 0:  
    print("No solutions found.")
Salida (cuando usamos nuestro archivo JSON de ejemplo como entrada):
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 783 |
------------------
|768 | 524 | 139 |
|923 | 671 | 458 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 453 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 543 |
------------------
|387 | 459 | 216 |
|612 | 387 | 495 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 354 |
|154 | 938 | 672 |
==================
Nota : Es muy fácil pasar por alto la parte del código que se asegura de no tocar los valores que ya se encuentran en el rompecabezas.
Si intentáramos ejecutar el código sin esa parte, el programa intentaría crear TODOS LOS ROMPECABLES SUDOKU IMAGINABLES. Lo que bien podría ser un bucle sin fin.

Conclusión y desventajas

Tan divertido y diferente como es la programación de restricciones, ciertamente tiene sus inconvenientes. Todos los problemas resueltos mediante la programación de restricciones se pueden escribir en un estilo imperativo con un tiempo de ejecución igual o (como en la mayoría de los casos) mejor.
Es natural que el desarrollador entienda el problema mejor de lo que puede describirlo python-constraintUna nota muy importante que se debe hacer es que la programación restringida puede, en algunas situaciones, ahorrar horas y horas de tiempo de desarrollo a cambio de un tiempo de ejecución ligeramente peor.
Recientemente tuve un ejemplo real de esto. Una amiga mía, alguien que solo se enteró de la existencia de Python unos meses antes, necesitaba resolver un problema para un proyecto de investigación de química física en el que estaba trabajando.
Ese amigo necesitaba resolver el siguiente problema:
Generate all combinations (that have a length equal to the number of keys) of values stored in a dictionary (the order of output doesn't matter). The dictionary is {String : List_of_Strings}. In such a way that every combination has exactly one value from the List_of_Strings of a key.

You don't know the number of keys in the dictionary in advance, nor do you know how long a List_of_String is, every List_of_String can be of different length. I.e. the dictionary is dynamically generated via user input.

Example input: dictionary = {"A" : [1,2], "B" -> [4], "C" -> [5,6,7], "D" -> [8,9]}  
Example output: (1,4,5,8), (1,4,5,8), (1,4,6,8), (1,4,6,9), (1,4,7,8)....  
Intenta y piensa cómo resolverías esto usando la programación imperativa.
Ni siquiera se me ocurrió una idea de una buena solución en imperativo. Al menos no en los 5 minutos que tardé en resolver su problema en la programación de restricciones, literalmente en unas pocas líneas de código.
import constraint

# input example
generated_dictionary = {'A' : [1,2], 'B' : [4], 'C' : [5,6,7], 'D' : [8,9]}

problem = constraint.Problem()

for key, value in generated_dictionary.items():  
    problem.addVariable(key, value)

solutions = problem.getSolutions()

for solution in solutions:  
    print(solution)
Eso es. Simplemente no agregamos ninguna restricción y el programa generó todas las combinaciones aceptables para nosotros. En su caso, la mínima diferencia en el tiempo de ejecución de este programa no importa de forma remota tanto como la rapidez con la que se escribió y lo legible que es.
Una cosa más a tener en cuenta es que python-constraintpuede hacer más que solo probar si una combinación se ajusta a todas las restricciones sin pensar.
Se implementan capacidades de retroceso (y retroceso recursivo), así como un solucionador de problemas basado en la teoría de conflictos mínimos. Estos pueden pasarse como un argumento al .Problem()método, por ejemplo .Problem(BacktrackingSolver), el resto se realiza de la misma manera que en los ejemplos anteriores.

Lista de restricciones incorporadas

Nombre de restricciónRestricción Descripción
AllDifferentConstraintHace que los valores de todas las variables dadas sean diferentes
AllEqualConstraintHace que los valores de todas las variables dadas sean iguales
MaxSumConstraintImplica que los valores de las variables dadas sumen una cantidad dada
ExactSumConstraintImplica que los valores de las variables dadas se suman exactamente a una cantidad dada
MinSumConstraintRestricción que obliga a que los valores de las variables dadas se sumen al menos a una cantidad dada
InSetConstraintRestricción que obliga a que los valores de las variables dadas estén presentes en el conjunto dado
NotInSetConstraintRestricción que obliga a que los valores de las variables dadas no estén presentes en el conjunto dado
SomeInSetConstraintRestricción que obliga a que al menos algunos de los valores de las variables dadas deben estar presentes en un conjunto dado
SomeNotInSetConstraintRestricción que obliga a que al menos algunos de los valores de las variables dadas no deben estar presentes en un conjunto dado
Al usar restricciones que pueden tomar una lista de multiplicadores como parámetro (Me gusta ExactSumMinSum), tenga cuidado de decir explícitamente el orden o las variables si es necesario, como hicimos en el Ejemplo E

Conclusión

La programación de restricciones es sorprendente en lo que respecta a la facilidad de lectura y la facilidad para desarrollar ciertos programas, pero lo hace a costa del tiempo de ejecución. Depende del desarrollador decidir qué es más importante para él en un problema en particular.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas