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 に対してどのように定義する必要があるかわかりません。各ドライバーには最短距離の値が 1 つしかありません。これにはラムダ関数を使用する必要がありますか?

編集

これのラムダバージョンを実装しようとしましたが、ラムダ構文がダウンしていないようです。私はいたるところを見てきましたが、これの何が問題なのかを見つけることができないようです。基本的に、コードの最後のスニペットを置き換え (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)

他の誰かがこのようなことをしようとしましたか? 制約ライブラリがこれを許可しない理由がわかりません。

4

1 に答える 1

3

Pythonのラムダ形式は、匿名（名前のない）関数を作成する方法を提供します。次の2つの定義は同等です。

name = lambda arguments: expression

def name(arguments):
    return expression

ラムダ式の本体はそれ自体が式であるため、本体にステートメント（printなど）を含めることはできません。

問題に関数制約を追加するときは、関数が変数と同じ数の引数を受け入れることを確認する必要があります。制約が適用されると、各引数には、対応する変数に現在バインドされている値（規則に従って、運転手と同乗者が一緒に乗る場合は1、それ以外の場合は0）が渡されます。

特定のドライバーに関連付けられた変数の数（乗客の数に等しい）が変更される可能性があるため、制約内の関数が任意の数の引数を受け入れることが賢明です。これは、Pythonで位置引数を使用して実行できます。したがって、特定のドライバー変数のセット（ここではdriver_variablesという名前を使用します）の場合、制約は次の形式になります。

problem.addConstraint(FunctionConstraint(lambda *values: ...), driver_variables)

引数の値は、driver_variablesリスト内の対応する変数に現在バインドされている値のリストにバインドされます。ラムダ本体は、次のように記述する必要があります。

  1. 値リストの各値（0または1）をdriver_variablesリストの対応する変数に関連付けるリストを作成します。
  2. このリストから、値が1（ドライバーと一緒に乗る乗客に対応）の変数を選択します。このリストは、ドライバーがたどるルートを形成します。
  3. ルート距離を見つけ（この例ではget_route_distance関数を使用）、最大値（maximum_distance）と比較します。

（1）にはzipを使用し（値の順序は変数の順序と同じであることが保証されます）、（2）にはリスト内包表記を使用し、（3）には単純な関数呼び出しと比較を使用できます。これにより、次のラムダ形式をとる関数が生成されます。

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））は2つの項目のみに切り捨てられます。これを修正する1つの方法は、driver_setに式zip（passengers、[e1] * len（passengers））を使用することです（passenger_setにも同様の変更を加えます）。ただし、よりPython的な方法があります。

次のステートメントを使用して、正しい乗客とドライバーのセット（この例では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]
于 2011-02-19T04:24:57.393 に答える