KMアルゴリズム学習ノート

二分図定義
図の頂点はちょうど2つの集合に分けることができ、同じ集合内の頂点間にはエッジが許されず、異なる集合の頂点にはエッジが接続されることが許される.
問題の分類

最大マッチング問題:ハンガリーアルゴリズム、Hopcroft–Karpアルゴリズム

最適重みマッチング問題:Kuhn-Munkrasアルゴリズム

肝心な思想.
拡張路(augmenting path):現在マッチング結果があると仮定し、非マッチングポイントのODのセットが存在し、マッチングと非マッチングのポイントが交互に現れるパスを見つけることができ、拡張路と呼ばれる
拡張パスのマッチングと未マッチングが逆になると、マッチング数は1増加します.
KMアルゴリズム
基本思想:トップスケールを導入することによって、最適重み値マッチングを最大マッチング問題に変換する.
ステップ1:エッジウェイト値をトップ/ロッドに変換します.一般的に、初期化時には、Xセットの要素は対応するウェイトの最大値を取り、Yセットの要素は0を取ります.次の条件を満たすエッジを取り出し、weight(i,j)=label(i)+label(j);この二分図を等子図と呼ぶ
ステップ2:拡張路を探して、X 0から、X 0 Y 4を見つけます;X 1では、拡張路が見つからず、トップスケールを調整し、等しいサブマップを拡大する必要がある.拡張パスが見つからない場合、探索されたパス上のXY点については、そのパス上のX頂点セットをS、Y頂点セットをTとし、S中の点xiおよびT中にない点yjすべてについてd=min{(L(xi)+L(yj)-weight(xiyj)}を計算し、SセットのXロッドからdを減算し、TセットのYのロッドに加える.本例では、拡張路を探す過程で、X 1、Y 4、X 0の3つのノードにアクセスするので、対応するエッジはX 1 Y 0である、dは2(欲張りなエッジ選択の観点から、X 0のために新しいエッジを選択して元の二分子図のマッチングエッジを捨てることもできるし、X 1のために新しいエッジを選択して元の二分子図のマッチングエッジを捨てることもできる.なぜなら、X 0 Y 4とX 1 Y 4を同時に選択することはできないからである.これは不合法なマッチングであるため、この場合、d=min{(L(xi)+L(yj)-weight(xiyj)}の意味は、私たちは新しいエッジを選択します.このエッジはマッチングサブマップに追加され、マッチングが合法になります.このエッジによって形成されたマッチングサブマップを選択すると、元のマッチングサブマップにこの不正なエッジを加えた不正なマッチングサブマップの重みと(合法であれば最大になります)よりも小さく、すなわち重みが最大になります.このとき再びX 1のために拡幅路を探す、X 1 Y 0を得る.
ステップ3:X 2に対して拡張路を探し、探索範囲は上図の青い経路に示すように、拡張路が見つからず、等しいサブ図を拡大する必要がある.ステップ2の同じ規則に従って、辺X 0 Y 2、X 2 Y 1が加える、d=1となる.
ステップ4:新しい等しいサブマップ上で、X 2に対して再び拡張路を探す.深さ優先であれば、得られた経路がX 2 Y 0->Y 0 X 1->X 1 Y 4->Y 4 X 0->X 0 Y 2であり、このときマッチング結果を逆にすると、X 2 Y 0、X 1 Y 4、X 0 Y 2の3つのマッチングが得られる.幅優先であれば、得られるマッチング結果は、X 0 Y 4、X 1 Y 0、X 2 Y 1であり、以下の図である.
Python実現

import numpy as np

#       
adj_matrix = build_graph() # np array with dimension N*N

#      
label_left = np.max(adj_matrix, axis=1)  # init label for the left set
label_right = np.zeros(N)  # init label for the right set

#        
match_right = np.empty(N) * np.nan

#        
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
slack_right = np.empty(N) * np.inf

#      ，    
def find_path(i):
  visit_left[i] = True
  for j, match_weight in enumerate(adj_matrix[i]):
    if visit_right[j]: continue  #     （        ）
    gap = label_left[i] + label_right[j] - match_weight
    if gap == 0:
      #       
      visit_right[j] = True
      if np.isnan(match_right[j]) or find_path(match_right[j]):  ## j    ，   j    ，  j             
        match_right[j] = i
          return True
        else:
      #                 
      if slack_right[j] < gap: slack_right[j] = gap
     return False

# KM   
def KM():
  for i in range(N):
      #       
      slack_right = np.empty(N) * np.inf
      while True:
        #       
        visit_left = np.empty(N) * False
                visit_right = np.empty(N) * False
        
          #        
        if find_path(i):    break
          #         ，    
        # (1)         X   label        d 
        # (2)         Y   label        d
        d = np.inf
        for j, slack in enumerate(slack_right):
          if not visit_right[j] and slack < d:
            d = slack
        for k in range(N):
          if visit_left[k]: label_left[k] -= d
        for n in range(N):
          if visit_right[n]: label_right[n] += d
    res = 0
  for j in range(N):
    if match_right[j] >=0 and match_right[j] < N:
      res += adj_matrix[match[j]][j]
  return res

参考資料
http://blog.sina.com.cn/s/blo...
https://blog.csdn.net/mosquit...