2

我一直在制作一个系统，该系统可以接收有关驾驶员、潜在乘客及其位置的数据，并尝试在某些限制条件下优化可以与驾驶员一起乘坐电梯的乘客数量。我正在使用 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)

但后来我得到了这个错误（注意它不是从我编辑的行中调用的，它来自之后的问题.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)

有没有其他人试图做这样的事情？我不明白为什么约束库不允许这样做。

4

1 回答 1

3

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. 制作一个列表，将 values 列表中的每个值（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)) （并对passenger_set 进行类似的更改）。但是，还有一种更 Pythonic 的方式。

可以使用以下语句生成正确的乘客和驱动程序集（本示例中的乘客变量和驱动程序变量）：

passengers_variables = [[(passenger, driver) for driver in drivers] for passenger in passengers]
drivers_variables = [[(passenger, driver) for passenger in passengers] for driver in drivers]
于 2011-02-19T04:24:57.393 回答