Ограничение Python: установка ограничения, зависящего от вывода функции

Question

Я делаю систему, которая принимает данные о водителях, потенциальных пассажирах и их местонахождении, и пытается оптимизировать количество пассажиров, которые могут подвезти водителя с учетом некоторых ограничений. Я использую модуль python-constraint, и переменные решения представлены следующим образом:

p = [(passenger, driver) for driver in drivers for passenger in passengers]
driver_set = [zip(passengers, [e1]*len(drivers)) for e1 in drivers]
passenger_set = [zip([e1]*len(passengers), drivers) for e1 in passengers]
self.problem.addVariables(p, [0,1])

Таким образом, когда я печатаю значение p и driver_set и passenger_set, я получаю следующий вывод (учитывая предоставленные мною тестовые данные):

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1)] # p
[[(0, 0), (0, 1)], [(1, 0), (1, 1)], [(2, 0), (2, 1)]] # passenger_set
[[(0, 0), (1, 0)], [(0, 1), (1, 1)]] # driver_set

Итак, есть 3 пассажира и 2 водителя: переменная (2,0) будет означать, что пассажир 2 находится в автомобиле 0 и так далее. Я добавил следующие ограничения, чтобы убедиться, что ни один пассажир не едет в более чем одной машине и что у водителя не может быть больше людей, чем мест:

for passenger in passenger_set:
        self.problem.addConstraint(MaxSumConstraint(1), passenger)
for driver in driver_set:
        realdriver = self.getDriverByOpId(driver[0][1])
        self.problem.addConstraint(MaxSumConstraint(realdriver.numSeats), driver)

Это сработало - все сгенерированные решения удовлетворяли этим ограничениям. Однако теперь я хотел бы добавить ограничения, говорящие о том, что любое решение не должно включать водителей, проезжающих больше определенного расстояния. У меня есть функция, которая принимает водителя (в том же формате, что и объект из driver_set) и рассчитывает кратчайшее расстояние для водителя, чтобы забрать всех пассажиров. Я попытался добавить ограничения следующим образом:

for driver in driver_set:
        self.problem.addConstraint(MaxSumConstraint(MAX_DISTANCE), [self.getRouteDistance(self.getShortestRoute(driver))])

Это дало следующую ошибку:

KeyError: 1.8725031790578293

Я не уверен, как это ограничение должно быть определено для Python-ограничения: для каждого драйвера есть только одно кратчайшее значение расстояния. Должен ли я использовать лямбда-функцию для этого?

РЕДАКТИРОВАТЬ

Я попытался реализовать лямбда-версию этого, однако у меня нет лямбда-синтаксиса. Я искал повсюду, но не могу понять, что с этим не так. По сути, я заменил последний фрагмент кода (добавив ограничение для ограничения значения getRouteDistance(driver)) и вместо этого поместил это:

for driver in driver_set:
    self.problem.addConstraint(lambda d: self.getRouteDistance(d) <= float(MAX_DISTANCE), driver)

Но потом я получил эту ошибку (обратите внимание, что она не вызывается из строки, которую я отредактировал, это из problem.getSolutions(), которая идет после):

File "allocation.py", line 130, in buildProblem
for solution in self.problem.getSolutions():
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 236, in getSolutions
return self._solver.getSolutions(domains, constraints, vconstraints)
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 529, in getSolutions
return list(self.getSolutionIter(domains, constraints, vconstraints))
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 506, in getSolutionIter
pushdomains):
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 939, in __call__
self.forwardCheck(variables, domains, assignments)))
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 891, in forwardCheck
if not self(variables, domains, assignments):
File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 940, in __call__
return self._func(*parms)
TypeError: <lambda>() takes exactly 1 argument (3 given)

Кто-нибудь еще пытался сделать что-нибудь подобное? Я не понимаю, почему библиотека ограничений не позволяет этого.

Answer 1

Лямбда-форма в Python позволяет создавать анонимные (безымянные) функции. Следующие два определения эквивалентны:

name = lambda arguments: expression

def name(arguments):
    return expression

Поскольку тело лямбда-выражения само является выражением, тело не может содержать никаких утверждений (например, print).

При добавлении ограничения функции к проблеме необходимо убедиться, что функция принимает столько аргументов, сколько имеется переменных. Когда ограничение применяется, каждому аргументу передается значение (согласно вашему соглашению, 1 для водителя и пассажира, едущего вместе, 0 в противном случае), в настоящее время связанное с соответствующей переменной.

Поскольку число переменных, связанных с данным водителем (равно количеству пассажиров), может измениться, было бы разумно, чтобы функция в ограничении принимала произвольное количество аргументов. Это может быть достигнуто в Python с использованием позиционных аргументов. Таким образом, для данного набора переменных драйвера (здесь используется имя driver_variables) ограничение принимает следующую форму:

problem.addConstraint(FunctionConstraint(lambda *values: ...), driver_variables)

Значения аргумента привязываются к списку значений, которые в данный момент связаны с соответствующими переменными в списке driver_variables. Лямбда-тело должно быть написано так, чтобы сделать следующее:

1. Составьте список, чтобы связать каждое значение (0 или 1) в списке значений с соответствующей переменной в списке driver_variables;
2. Из этого списка выберите переменные, которые имеют значение 1 (соответствует пассажирам, едущим с водителем)- этот список формирует маршрут, пройденный водителем;
3. Найдите расстояние маршрута (используя функцию get_route_distance в этом примере) и сравните с максимумом (Maximum_distance).

Можно использовать zip для (1) (порядок значений гарантированно совпадает с порядком переменных), понимание списка для (2) и простой вызов функции и сравнение для (3). Это приводит к функции, которая принимает следующую лямбда-форму:

lambda *values: get_route_distance([variable for variable, value in zip(driver_variables, values) if value == 1]) <= maximum_distance

Для удобства чтения кода может оказаться полезным написать эту функцию явно, используя def.

С другой стороны, в коде есть ошибка для определения driver_set выше. Правильное значение для driver_set должно быть:

[[(0, 0), (1, 0), (2, 0)], [(0, 1), (1, 1), (2, 1)]]

В приведенном выше примере, поскольку len(драйверов) равно 2, zip(пассажиров, [e1]*len(водителей)) усекается только до двух элементов. Одним из способов решения этой проблемы является использование выражения zip (пассажиров, [e1]*len(пассажиров)) для driver_set (и внесите аналогичное изменение для passenger_set). Тем не менее, есть более Pythonic путь.

Можно создать правильные наборы пассажиров и водителей (в этом примере passenger_variables и drivers_variables), используя следующие операторы:

passengers_variables = [[(passenger, driver) for driver in drivers] for passenger in passengers]
drivers_variables = [[(passenger, driver) for passenger in passengers] for driver in drivers]