第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光.

第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光

4.4 Kuhn’s Algorithm for the Assignment Problem
頂点が V1(G) と V2(G) で分かれており、どちらの頂点数も n である(下の図は n=3 の場合) c を E(G) の重み関数とするもっとも重みが大きくなるようなマッチングを探す V1(G) V2(G)

割り当て問題を解くために線形計画法の双対定理を使う

割り当て問題を以下のような式に変形する c はコスト関数 xe は枝 e を選ぶかどうか変数 xe は整数だが特に制限しない双対定理の形にはめるため答えは必ず整数になる

主問題より双対問題を導く全ての　　　　　　の組み合わせに対し以下のような変形重み関数　　を定義する双対定理より y が実行可能解であることは　　が非正である事と等しい

Example V1(G) := {1,2,3,4}, V2(G) := {a,b,c,d} 辺の重み関数 c の行列 1 a 2 b 3 c 4 d V1(G) V2(G)

Example (y1, y2, y3, y4) = (15, 18,17, 18) (ya, yb, yc, yd) = (0, 0, 0, -2) 変形重み関数　　の行列 1 a 2 b 3 c 4 d V1(G) V2(G)

マッチングFの重みが　　に関して最大であるならば c に関しても最大であり、逆も言えるよって　を最大にするようなマッチングを考えればよい　　は非正なのでできるだけ 0 に近い方がよい

ここで紹介するアルゴリズムは常に双対実行可能解を持つこの解は十分に最適である最適解がいくつかあるかもしれないが、そのうちの一つになる同等部分グラフ(equality subgraph) G= を定義する V(G=) := V(G)

Example 変形重み行列の0の枝のみ　　残したグラフになる G= 1 a 2 b 3 c 4 d V1(G) V2(G)

y が双対実行可能解であり、Fが任意の辺の集合とすると　　　　　　であることは明白 y が双対実行可能解ならば、G=の任意の完全マッチングはGの最大重み完全マッチングであるよってG= の最大マッチング F を探す

Example 例の場合は右の実線が　　最大マッチング F G= 1 a 2 b 3 c 4 d V1(G) V2(G)

F が完全マッチングでなければ F に入らなかった頂点集合のうち、V1 (G)に入っているものを起点とした最大の alternating forest を H とする

Example この場合起点は4のみ G= 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) H

Example 起点からたどれるものを全て H とする G= H 1 a 1 a 2 b 2 b H 3 c 3 c 4 d 4 d V1(G) V2(G) H

次に以下を定義をする △は必ず 0 より大きいことに注意するそうでなければ H はまだ拡張できる

Example H 1 a 1 a 2 w b 2 b v w H 3 c 3 c 4 d w 4 d v H

最後に双対解を更新する再び G= を作るところからスタートし、アルゴリズムが停止するまで繰り返す

Example △の更新により変形重み関数の行列が変わる 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) V1(G) V2(G)

次のことがらは必ず満たされるある枝の変形重みが非負ならば y を更新した後も非負変形重みの更新は以下のとおり　　　　　　　　　　　　　　　　　　　　　　　　　　　のような枝は△だけ減少するしかし△の選び方より、前の変形重みが非負ならば、更新後も非負である

次の条件も満たされるアルゴリズムはあるステップ数で必ず停止するマッチングの増加の回数は n (= V(G1) = V(G2)) 1から出る枝のマッチングが決まる、2から出る枝のマッチングが決まる…… n から出る枝のマッチングが決まるマッチングを1つ増やすのに alternating forest H を成長させる回数は最大で n よって y は最大 n^2 回変化する

なぜマッチングを1つ増やすのに alternating forest H を成長させる回数は最大で n なのか？

Example 最小コストマッチングは左図なのに、3つ目のマッチングまでで右図のようになってしまった場合 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) V1(G) V2(G)

Example 1 a 1 a 2 b 2 b 3 c 3 c 4 H d 4 d V1(G) V2(G) V1(G) V2(G)

Example 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d H V1(G) V2(G) V1(G) V2(G)

Example y を更新しても、前の H の枝は全て G= に残る更新して新しく G= に入った全ての枝は F に適用される 1 a 2 b 3 c 4 d V1(G) V2(G)

1回の双対解の更新にかかる通常の計算機の計算量は O(n^2) よって全ての計算量は O(n^4)

また、Hの要素は V1(G) のものが V2(G) のものより1つ多いよってこれより　　　　　が1ステップごとに減少することがわかる 1回ごとにこれはアルゴリズムが停止するという簡単な証明にもなっている

4.5 Application of Weighted Matching
グラフの最適重みマッチングを見つけるアルゴリズムの応用について議論するシンプルな応用のひとつに最小重み偶数経路を探すものがあるただしグラフは無向グラフで、枝の重みは非負であるとする

最小重み偶数経路問題グラフ G を無向グラフで枝の重みが非負であるとする v、w を G の頂点のペアとする目的は v から w までの経路のうち、枝の数が偶数で重みが最小のものを探すこと

最小重み偶数経路問題 H := G[V(G) – v] H’ は G[V(G) – w] のコピーであり V(H’) :={u’ : u∈V(G) - w} M は V(H) - w の要素 u とコピーのV(H’) – v の要素u’ との枝の集合新しいグラフ G’ を構成する G’の枝 E(H)∪E(H’) の重みはGのものと同じ G’の枝 M の重みは0

v v H’ G H w G’

Q1)　 G’の最小重み完全マッチングが分かると、v-w 経路の中から枝の数が偶数であるようなもののうち、重みが最小である経路を見つけることが出来ることを証明せよ Q2)　G の重みが負の場合どのような不都合が生じるか？

v H’ H u1’ u1 u2’ u2 u3’ u3 u4’ u4 u5’ u5 w

v H’ H u2’ u2 u3’ u3 u5’ u5 w

v H’ H u2 u3 u5 w

さらに重みつきマッチングを応用するグラフ G において T を V(G) の部分集合とし、F をE(G) の部分集合とする |T| は偶数とする F が以下の条件を満たす時、F を G の T-join と呼ぶ右図を G とし v1、v2 を T とすると　 G の T-join は{{v1, v2}} 　または {{v1, v2}, {v2, v3}, {v2, v4}, {v3, v4}} v1 v3 v2 v4

節点-枝変換行列をA(G)、 F ⊂ E(G) の特徴ベクトルをｘ(F)、集合 T ⊂ V(G)の特徴ベクトルを x(T) とする |T| は偶数とする F が T-join であることは GF(2) における A(G)x(F)=x(T) であることの必要十分条件である GF(2) は元の数が2つなので1足す1を0とする

以下のような F の場合は A(G)x(F)=x(T) を満たし、この F はG の T-join である v1 v3 v2 v4

T-join が最小とはその集合の中にそれより小さな　 T-join が含まれていないということとする全ての最小 T-join は forest である forest でない T-join からサイクルを繰り返し削除できる下の例では{{v1, v2}, {v2, v3}, {v2, v4}, {v3, v4}}からサイクルを削除した{{v1, v2}}が T-join v1 v3 v2 v4

この書では最小 T-join に注目する枝には正の重みがついているならば、最小重み T-join は最小 T-join になる非負の重みがついているならば、最小重み T-join は「最小 T-join」と「重みが0の枝で構成された 0-join」との枝を共有しない集合「重みが0の枝で構成された 0-join」とは重みが0の枝のみで出来たサイクル

|V(G)|/2 の要素を持つ V(G)-join は G の完全マッチングの集合 V(G)-join はV(G)の全ての頂点から奇数の枝が伸びている枝の数が |V(G)|/2 ならばすべての頂点は1本ずつ枝を持つよって V(G)-joinは Gの完全マッチング

大きな正の定数の重みをそれぞれの枝に加えると　新しい重みについての最小重み V(G)-join はもとの重みについての最小重み完全マッチングもし重みが0以下の枝があれば最小重み V(G)-join の頂点のうちひとつの頂点から複数本の枝が出る可能性がある大きな正の定数を加えて上げ底をすることで、ひとつの頂点から出る枝の数を1本にして、完全マッチングを作ることが出来るこれらのように T-join は完全マッチングに一般化される

無効グラフの最小重み経路 v-w を探す問題を考える d を E(G) の重み関数とするもし d が非負ならば G の枝を有効グラフ Hの別の向きの枝のペアに置き換えることが出来る新しい枝を e’、e’’とする重み関数を c とし　　c(e’) := c(e’’) := d(e)とする c に関して最小重み経路 v-w を　 H から探す問題を考えればよい i i e’ e e’’ j j

T := {v, w} とすると最小 T-join の枝集合は G の(無向の) {v, w} の経路の枝集合 Gが負の重みの枝のサイクルを含んでいないならば　G の最小重み T-joinは v-w 経路と重みが0の枝で構成された 0-joinとの枝を共有しない枝集合よって最小重み T-join を見つける効果的なアルゴリズムは無向グラフの最小重み v-w 経路を見つける効果的なアルゴリズム

二つの補題を使って、最小重み T-join を探す問題は、非負の重みの場合のみを考えればよいことを示す

補題[T-joinの排他的論理和] F’を G の T’-join とし、F⊂E(G) 、T⊂V(G) とする F が G のT-join であることはFΔF’がGのTΔT’-joinであることの必要十分条件である

証明 F’が T’-join ということは A(G)x(F’)=x(T’) であると言うことと同等であった FとFΔF’も同じ FΔF’がGのTΔT’-joinであるとする x(FΔF’) = x(F) + x（F’）、 x(TΔT’) = x(T) + x（T’）なのでA(G)x(FΔF’) = x(TΔT’) ということは　　A(G)x(F)+ A(G)x(F’) = x(T) + x(T’) ということと同等　　よって A(G)x(F) = x(T) なので F は G の T-joinである　　逆も同様にして証明できる

補題[T-joinの目的関数のシフト] F’をGのT’-join とし c を E(G) の重み関数とする E(G) の新しい重み関数を d とし全ての F⊂E(G)に対して d(F) := c(FΔF’) – c(F’) とする F が d(F) を最大にする T-join ということは FΔF’が　　　　　 c（FΔF’) を最大にする TΔT’-join であるということの必要十分条件である証明先の補題より、F が T-join ということは FΔF’が TΔT’-joinであるということの必要十分条件であったさらに目的関数 d(F) が c(FΔF’) から定数 c(F’)だけシフトしている

定理 [非負重み T-join への変形] E_ := {e∈E(G) : c(e) < 0} O_ := {v∈V(G) : |E_∩δG(v)| is odd} E(G) に対して非負重み関数 c+ を定義する全ての e∈E(G) に対して c+(e) := |c(e)| c に対して FΔE_ が最小重みTΔO_-join ということは c+ に対して F が最小重み T-join であることの必要十分条件

証明先の補題の T’を E_、F’をO_ とする F’は T’-join d(F) = c(FΔF’) - c(F’) 　　= c(F　F’) + c(F’　F) - c(F’) 　　= c(F　F’) - c(F’∩F) 　　= c+(F)

G の最小重み T-join を探す問題に戻る重み関数 c は非負と考える補題[Structure of repeated edges] P を G の最小重み T-join とする Pは次のようなパスの枝集合に分割される端点を共有しない端点が T に入っている

証明 P の枝の数に関する帰納法で考える P の中のパス H を選ぶ H の枝はサイクルを持たないよってその枝は次数1の頂点を(少なくとも) 2つ含むこれらの頂点は必ず T に入っている P の2つの頂点間の経路は一つだけ存在するこの経路を P から削除する

補題より次のアルゴリズムを導く事ができる Edmonds-Jonson 最小重み T-join アルゴリズム G をグラフ、T を V(G) の部分集合、c を E(G)の非負の重み関数とする Tの要素数は偶数とする i, j　が T の要素である時、P{i, j} を G の最小重み i-j 経路とする K を V(K) := T であるような完全グラフとする c’を次のように定義する

重み関数c’に関して、S を K の最小重み完全マッチングとするこの時 P を {i, j}∈S における P{i, j} の排他的論理和とするとP は G の最小重み T-join である経路 {i, j} のうち最小重みのものが T = {{i, j}} の最小T-joinであることはすでに述べたさらにこれらのT-joinの排他的論理和を取る事で T と T-joinを増やしていっている

T-join はオイラーグラフと呼ばれる巡回問題にも応用される無向グラフのオイラー閉路とは E(G) を1回ずつ通るようなグラフのたどり方の事を指す無効グラフがオイラリアンであるということはグラフがオイラー閉路を持っている事の必要十分条件である

オイラーの定理 G がオイラリアンであることの必要十分条件は G がつながっており、E(G) が 0-join であることである証明「 G がオイラリアンである⇒ G がつながっており、E(G) が 0-join であることである」ということは明らかオイラー閉路は全ての枝を通り、そのたび頂点 v を通る v を通るときに2本の枝が使われる

「 G がつながっており、E(G) が 0-join であることである ⇒ G がオイラリアンである」　を示す枝の数に関する帰納法で証明する G がつながっていて、 E(G) が 0-join だとする E(G) がサイクル C を持つ事はすぐわかる枝が2本の場合、G は1つのサイクルなので明らかにオイラリアン頂点の次数が2より大きいものがある場合、C とつながっているグラフを G1, G2, … , Gk とする E(G) から C を除いても、グラフの全ての頂点の次数は偶数である帰納法の仮定より Gi は全てオイラー閉路を持つサイクル C をたどりつつ、Gi に寄り道をすればオイラー閉路ができる

全ての頂点の次数が2の場合 G はつながっているので1つのサイクルになる

頂点の次数が２より大きいものがある場合 Gkはそれぞれ「つながっており枝が 0-join」であるので、帰納法の仮定よりオイラリアン G1 G4 G3 G2

グラフ G がつながっており E(G) の非負重み関数を c とする郵便配達人経路 G の全ての枝を通る同じ枝を何回通っても良い最後はスタート地点に帰ってくる郵便配達人グラフをオイラーグラフ G＾とする V(G) = V(G^) E(G) ⊂ E(G^)

補題 [繰り返し枝の forest] オイラー閉路 G^ が G の最小重み郵便配達人経路になりうるならばE(G^) 　E(G)はサイクルを持たない証明(対偶) E(G^) 　E(G) からサイクルを除いてもオイラリアンの性質は失われない全ての枝が非負なので G^ は最小重み郵便配達人経路にはなりえない

コストは6 E(G^) E(G) (曲線の枝集合)はサイクルではない B 1 B A A 1 1 G 1 G^ 1 C C D D 1 1

E(G^) E(G) (曲線の枝集合) はサイクル G の最小重み郵便配達人経路は 4 G^ のコストは8 1 1 B B A A 1 1 G 1 1 G^ C C D D 1 1

グラフ G の各枝を2本ずつにした重みつきグラフを G(2) と呼ぶことにする特に次のようなグラフを G’と呼ぶことにする V(G’) := V(G) E(G’) := E(G(2)) E(G) 要するに G の複製最小重み郵便配達人経路探索問題を最小重みを持つオイラーグラフ G^ を見つける問題とする E(G^) ⊆ E(G(2)) E(G) ⊆ E(G^) G G^ G(2)

奇数の次数を持つ G の頂点集合を T とする (G^　G)⊂G’はG’の最小重み T-join これらより郵便配達人経路の探し方を導くグラフ G の中の奇数の次数を持つ頂点を見つけるそれらの頂点を通る G の最小重みグラフを見つける(最小重みT-join) それらの枝をそれぞれ二つに増やしグラフ G^ を作る G^ の最小重みオイラー閉路を探す見つけたオイラー閉路のうち、途中で増やした枝を2回通るような道筋が G の郵便配達人経路

Exercise 4 4 3 3 1 1 1 1 2 1 3 4 4 3

Exercise 4 4 3 3 1 1 1 1 1 2 2 1 1 1 1 1 3 4 4 3

Exercise 9 10 1 18 4 17 19 16 20 2 3 11 15 12 14 13 6 8 7 5

Exercise 9 10 1 17 18 4 19 16 20 2 3 15 12 11 6 14 13 8 7 5

同じ発想をハミルトン閉路の問題に適用できるハミルトン閉路は全ての頂点を1度だけ通るような閉路 N を有限個の点の集合とする G を V(G) = N であるような完全グラフとする G の枝 e が存在するとき c(e) を e 間の距離とする G の最小重みハミルトン閉路を探す問題を巡回セールスマン問題と呼ぶ

オイラリアンであるようないかなる H⊂E(G(2)) に対しても、「圧縮」することにより H の重み以下の重みのハミルトン閉路を探すことが出来る重複する頂点に対して三角不等式を使う

次に示す手法では、最小重みハミルトン閉路より50%未満だけ大きい重みのハミルトン閉路が見つかる(近似度1.5) クリストフィード・ヒューリスティック S を G の最小重み全域木とし、T を以下のような集合とする F をG’[T] の最小重み完全マッチングとする G(2) の部分グラフ H を V(H) := V(G) であり E(H) は S∪Fから構成されるようなグラフとし、H のオイラー閉路を探すオイラー閉路を圧縮してハミルトン閉路にする

例：点集合が与えられる

例：最小重み全域木Sを求める

例：G’[T]の最小重み完全マッチングFを求める

例：SとFを合わせてHとする

例：最小重みハミルトン閉路

クリストフィードの定理クリストフィードの手法は最小重みハミルトン閉路の重みと近似度1.5の重みのハミルトン閉路を見つけることが出来る

証明ハミルトン閉路は全域木の一種なので、S の重みは G の最小重みハミルトン閉路の重みより大きくなることはない S は G の最小重み全域木三角不等式より、G[T] の最小重みハミルトン閉路の重みは G の最小重みハミルトン閉路の重みより小さい頂点数が少ないことから明らか G[T] のハミルトン閉路の枝集合は、2つのG[T] の完全マッチングに分けられるこのうち重みが小さいマッチングが F になるよって F の重みは、 G[T] の最小重みハミルトン閉路の重みの半分未満

証明続きよって E(H) の重みは V(G) の最小重みハミルトン閉路の重みの1.5倍未満 E(H) := E(S∪F) オイラーの定理より、H はオイラー閉路で、この道筋を圧縮して得られるハミルトン閉路の重みはオイラー閉路より小さくなる

問： [クリストフィード･ヒューリスティックの最悪の場合] ε>0 が与えられたとき、次のような二次元のユークリッド空間における点集合が存在することを示せ最小より少なくとも (50 -ε)% だけ大きい重みのハミルトン閉路がクリストフィードの手法によって見つかるつまり近似度が1.5に限りなく近くなる最悪の場合を考える

答：次のような正三角形の集合を考える辺の長さは1とする 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

最小全域木は以下のようになる 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

次数が奇数の頂点は 1 と m だけなので T := {{1,m}} とし、G[T]の最小重みマッチング F は以下のようになる 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

次数が奇数の頂点はないのでこれがハミルトン閉路となるこの閉路の重みは 3m-3 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

最小重みハミルトン閉路は以下のようになるこの閉路の重みは 2m-1 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

最小重みハミルトン経路問題は最適重みマッチングにも利用できる S⊂E(G) が全ての v∈V(G) に対し |S∩δG(v)| = 2ならば S を 2-factor と呼ぶ明らかにハミルトン閉路は 2-factor であり、最小重み2-factor は最小重みハミルトン閉路より重みが大きくなることはない

Gの最小重み 2-factor を探す問題を別のグラフ G’’の最小重み完全マッチングを探す問題に還元する隣接した頂点に行くことの出来る枝の数を頂点要求と呼ぶ 2-factor の頂点要求は全て2 完全マッチングの頂点要求は全て１よって頂点要求が2のグラフ G の問題を頂点要求が1のグラフG’’の問題に変換すればよい

ステップ1 v w 間に頂点を増やす {v, w} ∈S ならば {v, w’}, {v’, w} ∈S’ {v, w} ∈S ならば {v’, w’} ∈S’ (2) (2) cvw G v w (2) (1) (1) (2) cvw/2 cvw/2 G’ v w’ v’ w

ステップ2 (1) (1) cvr/2 r’ cvr/2 cvr/2 r’ (2) (1) (1) cvs/2 (1) (1) cvs/2 cvs/2 s’ v s’ v v’’ cvt/2 (1) (1) cvt/2 cvt/2 t’ t’ G’ G’’

これらの操作により、最小重み 2-factor を探す問題を最小重み完全マッチングを探す問題に還元することができる

第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光.

Similar presentations

Presentation on theme: "第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光."— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

第4章 Matching(後半) 情報学研究科 湯浅研究室M1 藤川浩光.

Similar presentations

Presentation on theme: "第4章 Matching(後半) 情報学研究科 湯浅研究室M1 藤川浩光."— Presentation transcript:

Similar presentations

About project

フィードバック

第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光.

Presentation on theme: "第4章　Matching(後半) 情報学研究科湯浅研究室M1 藤川浩光."— Presentation transcript: