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

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

1 голос
/ 13 февраля 2011

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

  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.

1 Ответ

4 голосов
/ 13 февраля 2011

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

...