python-constraint：根据函数输出设置约束

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-constraint中定义：每个司机只有一个最短距离值。我应该使用lambda函数吗？

编辑

我尝试实现一个lambda版本的这个功能，但我似乎对lambda语法不太熟悉。我到处查找，但找不到问题出在哪里。基本上，我替换了最后一段代码（添加限制以限制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中，lambda表达式是一种创建匿名（没有名字的）函数的方法。下面这两个定义是等价的：

name = lambda arguments: expression

def name(arguments):
    return expression

因为lambda表达式的主体本身就是一个表达式，所以里面不能包含任何语句（比如print）。

在给问题添加函数约束时，必须确保这个函数接受的参数数量和变量数量一致。当约束被应用时，每个参数会接收到一个值（根据你的约定，1表示司机和乘客一起，0则表示不一起）与相应的变量绑定。

由于与特定司机相关的变量数量（也就是乘客数量）可能会变化，所以让约束中的函数接受任意数量的参数是比较合理的。在Python中，可以使用位置参数来实现这一点。因此，对于一组司机变量（这里称为driver_variables），约束的形式如下：

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

参数值会绑定到当前与driver_variables列表中相应变量绑定的值列表上。lambda的主体应该这样写：

1. 创建一个列表，将值列表中的每个值（0或1）与driver_variables列表中的相应变量关联起来；
2. 从这个列表中选择值为1的变量（表示乘客和司机一起）——这个列表就是司机的行驶路线；
3. 找到路线的距离（在这个例子中使用get_route_distance函数），并与最大距离（maximum_distance）进行比较。

可以使用zip来完成第（1）步（值的顺序和变量的顺序是一样的），使用列表推导式来完成第（2）步，简单的函数调用和比较来完成第（3）步。这样就得到了一个如下形式的lambda函数：

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

为了提高代码的可读性，显式地使用def来写这个函数可能会更好。

另外，关于上面定义driver_set的代码，有一个bug。driver_set的正确值应该是：

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

在上面的例子中，由于len(drivers)是2，zip(passengers, [e1]*len(drivers))被截断为只有两个项目。解决这个问题的一种方法是将driver_set改为zip(passengers, [e1]*len(passengers))（同时对passenger_set做类似的修改）。不过，还有一种更符合Python风格的方法。

可以使用以下语句生成正确的乘客和司机集合（在这个例子中是passengers_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]