在python-constraint中添加约束时出现KeyError

Question

我正在写一个函数，这个函数接收一个司机和乘客的列表，里面包含他们的位置，然后返回一个乘客分配给司机的列表，目的是让尽可能多的乘客被分配给司机，同时要遵循以下几个规则：

1. 一个乘客只能坐一辆车

2. 每辆车上分配的乘客数量不能超过车的座位数

3. 每位司机接送所有乘客的行程距离不能超过某个固定的限制

我遇到的问题是如何添加第一个规则。我在看一个教程，地址是 http://uswaretech.com/blog/2009/03/constraint-programming-in-python/，我用了一种类似的方式来解决他们的魔方问题：把乘客分配给车的方式存储为一个元组（司机，乘客），这些元组被放在一个列表里。司机和乘客的具体信息则存储在包含他们的ID、经纬度以及每位司机车上座位数的类中。以下是我用来构建这个问题的代码，我是从一个文件中提取的测试数据：

self.problem = Problem()
drivers = range(len(self.drivers))
passengers = range(len(self.passengers))
p = [(driver, passenger) for driver in drivers for passenger in passengers]
driver_set = [zip([e1]*len(passengers), passengers) for e1 in drivers]
passenger_set = [zip([e1]*len(drivers), drivers) for e1 in passengers]
self.problem.addVariables(p, [0,1])
for passenger in passenger_set:
    self.problem.addConstraint(MaxSumConstraint(1), passenger)
print self.problem.getSolutions()

我在交互式环境中运行这个代码时，发现我可以在添加规则之前运行 getSolutions()，但在运行整个程序时却出现了以下错误：

Traceback (most recent call last):
  File "allocation.py", line 84, in <module>
    obj1.buildProblem("testdata.txt")
  File "allocation.py", line 81, in buildProblem
    self.problem.getSolutions()
  File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 233, in getSolutions
    domains, constraints, vconstraints = self._getArgs()
  File "/Users/wadben/Documents/Dev/Python/sp-allocation/constraint.py", line 275, in _getArgs
    vconstraints[variable].append((constraint, variables))
KeyError: (2, 0)

看起来在 getSolutions() 方法执行的某个时刻，它试图查找 (2,0)，尽管第一个元组的最大值是 1（我的数据集中只有 2 位司机）。我运行了教程中的代码，结果很好，但我不太确定我的代码和他们的代码有什么不同，导致了这个错误，除了我使用了 MaxSumConstraint 而不是 ExactSumConstraint。

Answer 1

你的变量是这样的形式 (driver, passenger)：

p = [(driver, passenger) for driver in drivers for passenger in passengers]
self.problem.addVariables(p, [0,1])

但是你传给 addConstraint() 的变量却是这样的形式 (passenger, driver)：

passenger_set = [zip([e1]*len(drivers), drivers) for e1 in passengers]
for passenger in passenger_set:
    self.problem.addConstraint(MaxSumConstraint(1), passenger)

所以当求解器试图根据变量来分组约束时，遇到变量 (2, 0) 的约束时，它会报错，因为它不知道这个变量是什么（我猜你的例子中只有两个司机）。