KeyError при добавлении ограничения в python-constraint

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

  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.


python constraint-programming
person benwad    schedule 13.02.2011    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Ваши переменные имеют вид (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), он выдает ошибку, потому что он не знает эту переменную (я предполагаю, что в вашем примере есть только два драйвера).

person balpha    schedule 13.02.2011