Я бы порекомендовал решить эту проблему как проблему удовлетворения ограничений , используя смоделированную как проблему логического удовлетворения / SAT .
. Для этого определите K * N булевы переменные для каждой комбинации эксперимента и лаборатории.Если переменная имеет значение true, это означает, что данный эксперимент должен быть выполнен в данной лаборатории.
Введенные вами ограничения могут быть смоделированы с использованием этих переменных.Например, если переменные названы x (эксперимент, лаборатория) , и у нас есть три лаборатории, и мы хотим провести эксперимент 1 на двух из них, это подразумевает ограничение:
( x(1,1) & x(1,2) & !x(1,3) ) | ( x(1,1) & !x(1,2) & x(1,3) ) | ( !x(1,1) & x(1,2) & x(1,3) )
Все остальные ваши ограничения могут быть записаны аналогично.Однако этот экспоненциальный взрыв статей вызывает беспокойство.К счастью, хорошие инструменты моделирования могут автоматически вставлять дополнительные переменные, чтобы сделать такие ограничения кардинальности гораздо более эффективными.
Ниже я разработал полную реализацию для решения вашей проблемы с помощью решателя Z3:
#!/usr/bin/env python3
#Richard Barnes (https://stackoverflow.com/users/752843/richard)
#May need to run `pip3 install z3-solver`
import functools
import itertools
import sys
import z3
class ExpLab:
def __init__(self, num_experiments, num_labs):
"""Create binary indicator variables for each lab-experiment combination"""
self.num_labs = num_labs #Number of labs
self.num_experiments = num_experiments #Number of experiments
#Create variables
self.bvars = []
for e in range(num_experiments):
for l in range(num_labs):
self.bvars += [ {"exp":e, "lab":l, "yn": z3.Bool("Run Experiment {0} at Lab {1}".format(e,l))} ]
def getExpLab(self, exp, lab):
"""Get the variable indicating whether a particular experiment should be
performed at a particular lab"""
return [x['yn'] for x in self.bvars if x['exp']==exp and x['lab']==lab][0]
def getExp(self, exp):
"""For a given experiment, get the indicator variables for all the labs the
experiment might be performed at"""
return [x['yn'] for x in self.bvars if x['exp']==exp]
def getLab(self, lab):
"""For a given lab, get the variables associated for all of the experiments
that might be performed at the lab"""
return [x['yn'] for x in self.bvars if x['lab']==lab]
def numExperiments(self):
return self.num_experiments
def numLabs(self):
return self.num_labs
#Create the binary indicator variables
el = ExpLab(num_experiments=6, num_labs=4)
s = z3.Solver()
R = 3 #Number of labs at which the experiment must be performed
M = 6 #Maximum number of experiments per lab
#See: https://stackoverflow.com/questions/43081929/k-out-of-n-constraint-in-z3py
#(1) each experiment has to be allocated to exactly 3 labs,
for e in range(el.numExperiments()):
s.add( z3.PbEq([(x,1) for x in el.getExp(e)], R) )
for l in range(el.numLabs()):
#(2) there's a maximum number of experiments per lab (around 6)
#NOTE: To make distributions more even, decreae the maximum number of
#experiments a lab can perform. This isn't a perfect way of creating a smooth
#distribution, but it will push solutions in that direction.
experiments_at_this_lab = el.getLab(l)
s.add( z3.PbLe([(x,1) for x in experiments_at_this_lab], M) )
#(3) no lab is left out.
s.add( z3.PbGe([(x,1) for x in experiments_at_this_lab], 1) )
#Example of a specific constraint
#Don't run Experiment 3 at Lab 2
s.add( z3.Not(el.getExpLab(3,2)) )
#Check to see if the model
if s.check()!=z3.sat:
print("The problem has no solution!")
sys.exit(-1)
#A solution to the problem exists... get it. Note: the solution generated is
#arbitrarily chosen from the set of all possible solutions.
m = s.model()
print(m)
Решение, созданное выше, выбирается «случайным образом» из всех возможных решений проблемы.Если вы недовольны решением, вы можете исключить его, собрав вместе все выходные данные решения, отрицая и добавив его в качестве нового ограничения.