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 和user_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) 进行比较。

可以对 (1) 使用 zip（保证值的顺序与变量的顺序相同），对 (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 的代码中存在一个错误。 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))（并对passengers_set 进行类似的更改）。然而，还有一种更Pythonic的方式。

可以使用以下语句生成正确的乘客和司机集（本例中为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]