Pythonで解くCampus Bikes II ― マンハッタン距離の総和を最小化する自転車割り当て問題

問題概要

2次元グリッドで表現されたキャンパスに、N人のワーカーとM台の自転車があるとします。ただし、N ≤ M という条件が成り立ちます。各ワーカーと各自転車は、グリッド上の2次元座標で位置が与えられます。

このとき、すべてのワーカーに対して重複なく自転車を1台ずつ割り当て、ワーカーとその割り当て先の自転車とのマンハッタン距離の総和を最小化することを考えます。

2点 p1 と p2 のマンハッタン距離は、次の式で定義されます。

dist(p1, p2) = |p1.x − p2.x| + |p1.y − p2.y|

求めるべきは、全ワーカーとその割り当て自転車の間のマンハッタン距離の合計の最小値です。

たとえば、入力が workers = [[0,0],[2,1]]、bikes = [[1,2],[3,3]] の場合、

出力は 6 となります。

解法のアプローチ

この問題は「バックトラッキング＋メモ化」の組み合わせで効率的に解くことができます。各ワーカーに対して、まだ使用されていない自転車を順番に割り当てていき、探索途中の状態をメモ化することで同じ状態の再計算を避けるのがポイントです。

具体的な手順は以下の通りです。

• 関数 helper() を定義します。引数 a, b を受け取り、2点間のマンハッタン距離 |a[0]−b[0]| + |a[1]−b[1]| を返します。

• 関数 solve() を定義します。引数は bikes, workers, bikev, i（デフォルト値は 0）です。i は現在処理中のワーカーのインデックス、bikev は各自転車が使用済みかどうかを示すフラグ配列です。

• info := (i, bikev) というタプルを作成し、メモ化のキーとします。

• info がメモに存在する場合は、memo[info] の値をそのまま返します。

• i が workers のサイズと等しい場合（全員への割り当てが完了している場合）は、0 を返します。

• temp := 無限大 で初期化します。

• j を 0 から bikes のサイズまでループさせます。

  • bikev[j] が未使用（False）であれば、bikev[j] := 1 として使用フラグを立てます。

  • temp := min(temp, helper(workers[i], bikes[j]) + solve(bikes, workers, bikev, i+1)) で最小値を更新します。

  • 探索後は bikev[j] := 0 に戻して（バックトラック）、他の選択肢も試せるようにします。

• memo[info] := temp を保存し、temp を返します。

• 関数 assignBikes() を定義します。引数は workers, bikes です。

• bikev := bikes のサイズと同じ長さのリストで、すべて False で初期化します。

• memo := 新しい辞書（マップ）を作成します。

• solve(bikes, workers, bikev) の結果を返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution(object):
    def helper(self,a,b):
        return abs( (a[0]-b[0]) ) + abs( (a[1] - b[1]) )
    def solve(self,bikes,workers,bikev,i=0):
        info = (i,tuple(bikev))
        if info in self.memo:
            return self.memo[info]
        if i == len(workers):
            return 0
        temp = float('inf')
        for j in range(len(bikes)):
            if not bikev[j]:
                bikev[j]=1
                temp = min(temp,self.helper(workers[i],bikes[j])+self.solve(bikes,workers,bikev,i+1))
                bikev[j]=0
        self.memo[info]= temp
        return temp
    def assignBikes(self, workers, bikes):
        bikev = [False for i in range(len(bikes))]
        self.memo={}
        return self.solve(bikes,workers,bikev)
ob = Solution()
print(ob.assignBikes([[0,0],[2,1]],[[1,2],[3,3]]))

入力

[[0,0],[2,1]] [[1,2],[3,3]]

出力

6

計算量について

メモ化によって、状態数は「ワーカーのインデックス × 自転車の使用パターン（最大 2^M 通り）」に抑えられます。したがって、時間計算量はおよそ O(N × M × 2^M)、空間計算量は O(N × 2^M) となります。M が小さい範囲であれば、このアプローチでも十分に高速に動作します。