KM(Kuhn-Munnkres)アルゴリズムは、帯域権の二分割図の最適なマッチングを求めます.
5311 ワード
KM(Kuhn-Munnkres)アルゴリズムは、帯域権の二分割図の最適なマッチングを求めます.
関連概念
このアルゴリズムは個人的には最初はちょっと分かりにくいと思います.特に新しく定義されたものは何をするか分かりません.しかし、アルゴリズムの実行過程と原理を知ると、これらの概念の意味と背後の役割がだんだん明らかになります.ですから、とりあえず関連概念を並べてみて、大体のイメージがあればいいです.アルゴリズムの流れを知ると、原理の中にこれらの概念があります.その時に帰ってきて詳しく見ればいいです.
完全一致:定義設定G＝二部図、|V1|≦𞓜V2|、MはGの中で一番大きなマッチングで、かつ|M124;V 1𞓜＝124; V 1|である.MはV 1からV 2までの完璧なマッチングと称される.つまり、一つのセットの点を全部別のセットに合わせるということです.(最初にこの概念を紹介したのは、多くの概念の中で完璧なマッチングが言及されていたからです.しかし、完璧なマッチングとは何か分かりませんでした.)上記の定義では、124 V 2 124＝124 V 1𞓜を見れば、完璧にマッチすることができます.
二分割図の最適なマッチング:二分割図の各辺に対して一つの権利(非負)があり、すべての整合辺の権利と最大、最適な完全なマッチングを行うように、完璧なマッチングスキームが要求される.(特殊なのは、すべての辺の権利が1の場合、最大の整合問題である)
二分割図の帯域権整合と最適整合:何が二分割図の帯域権整合ですか?二分割図の帯域権整合は、セットの中の辺の権利値の和が最大または最小になるように、一致セットを求めることである.二分割図の最適なマッチングは、必ず完全に一致するものであり、これに基づいて、一致するサイド重みの和が最大または最小であることが要求される.二分割図の帯域権整合は最適整合と等価ではなく、互いに含まれていない.
以下はいくつかの変換の考え方です.
KMアルゴリズムは最も大きな権力と完全なマッチングを求めていますが、もし最小権の完全なマッチングが要求されたら、どうすればいいですか?方法はとても簡単で、すべてのサイドの権利の値をその反対の数だけ取って、最も大きい権力が完全に一致することを求めて、一致する値は更に反対の数を取ります.
KMアルゴリズムの運行要求は完全なマッチングが必要です.もし一番大きな権力整合を求めたら、どうすればいいですか?依然としてとても簡単で、存在しない辺権を0に与えます.
KMアルゴリズムで求められた最も大きな権利整合は、エッジの値と最大であり、もし私がサイド権の積が最大であれば、どのように転化しますか?やはり難しくないです.一つ一つの辺権は自然対数を取って、そして最大の和権整合を求めて、求めた結果aはまたe^aを算出します.これは最大積マッチングです.精度の問題に至っては、もっといい方法はない.
以下はアルゴリズムが必要として確立された概念である.
トップフラグ:各ノードと別のセットにおけるノードとの間の最大値
実行可能トップラベル:元の図のいずれかの結点に対して、結点の最上位の値を求める関数L(node)を与えます.配列lx(x)を用いて集合Xにおける接合点の最上位値を記録し,集合Yにおける接合点の最上位値を配列ly(y)で記録した.また、原図のいずれかの辺\(edge(x,y)\)については、\(lx(x)+ly(x)>=weight(x,y)\)が満足されます.
等価子図:G(V,E)を二部図、G'(V,E')を二部図の子図とする.G'のどの辺に対しても満足するなら、\(lx)+ly(y)==weight(x,y)\)と言います.G'(V,E')はG(V,E)の等価子図または等しい子図(Gの生成子図です.
アルゴリズムフロー
ここには比較的に良い男女が対象のガイドブログを持っています.KMアルゴリズムの実行過程を説明しました.生き生きとしています.どのようにペアリング条件を満たしていますか?満足していない場合はどうすればいいですか?途中で期待値を下げるdはどのように求められますか?ペアリング失敗の期待値を変更した後にこれらの変化が発生しましたか?これらの変化は新しいラウンドのマッチングに何をもたらしましたか?
ここにリンクがあります
アルゴリズムの原理:
アルゴリズムの流れを知ると、アルゴリズムの原理が気になります.なぜこのようにして、なぜこのような変化が起きたのですか?なぜこれらの変化を利用すれば最終的な結果が得られますか?
原理を詳しく紹介する前に、まずこのブログを見てもいいです.アルゴリズムの流れによって原理を紹介します.直感的に感じられます.書いたのはやはりはっきりしています.字がちょっと小さいです.
ここにリンクがあります
アルゴリズムの正確性は以下の定理に基づいています.
二分割図中のすべての満足\(lx)+ly(y)==weight(x,y)\)の辺(x,y)からなるサブ図(等子図という)が完全に一致すると、この完璧なマッチングは二分割図の最大の権利マッチングです.
なぜなら、二分割図のいずれかの一致について、等しいサブ図に含めると、その辺権は、すべての頂点に等しいトップ・スケールとなるからである.それがある辺がイコールのサブマップに含まれていない場合、その辺権とすべての頂点より小さいトップ・スケールと(すなわち最適なマッチングではない).従って、等分子図の完全一致は、必ず二分割図の最大の一致である.
初期時は\(lx(x)+ly(y)==weight(x,y)\)恒を成立させるために、lx(x)を頂点Xiに関連する辺の最大権、ly(y)=0とする.現在の等しいサブダイアグラムが完全に一致していない場合、等しいサブダイアグラムが完全に一致するまで、トップスケールを以下の方法で修正する.
現在の等しいサブ図の完全なマッチングが失敗したのは、あるX頂点に対して、私たちはそれから出発するインターリーブの道が見つからないからです.この時、私達は一本のインタリーブツリーを獲得しました.葉の結点は全部X頂点です.今、私たちはインタリーブツリーの中のX頂点のトップマークを全部ある値dに減らして、Y頂点のトップマークは全部同じ値dを増加します.
1)両端はインタリーブツリーの中の辺(x,y)であり、lx(x)＋ly(y)の値は変化しない.つまり、元はイコールの子図で、今もイコールの子図です.
2)両側はインタリーブツリーの中にない辺(x,y)、lx(x)、ly(y)は変わりません.つまり、元はイコールのサブ図に属していますが、現在はイコールのサブ図に属しています.
3)X端はインターリーブツリーの中ではなく、Y端はインターリーブツリーの中の辺(x,y)であり、そのlx(x)＋ly(y)の値は増加する.もとは同じ子図ではなかったが、今は相等子図ではない.
4)X端はインターリーブツリーの中で、Y端はインターリーブツリーの中の辺(x,y)ではなく、そのlx(x)＋ly(y)の値は減少している.つまり、もともとは等子図ではなかったが、現在は等子図に入る可能性があり、等子図が拡大されている.
今の問題はd値を求めることです.ずっと成立させ、かつ少なくとも一つの辺が等しいサブ図に入るため、dは「\(Minlx(x)+ly(y)-weight(x,y)|xはインターリーブツリーにあり、yはインターリーブツリーにない」と等しいはずである.
以上はKMアルゴリズムの基本思想です.しかし、素朴な実現方法では、時間の複雑さはO(n 4)である.\(O(n)\)を探して拡大していく必要があります.拡大するたびに、最大で変更が必要です.\(O(n)\)のトップは毎回、トップを修正するたびに、列挙しながらd値を求めます.複雑さは\(O(n^2)\)です.実際のKMアルゴリズムの複雑さは\((n^3)\)までできます.私たちはY頂点ごとに「緩和量」関数slackを与え、成長路を探し始めるたびに無限大に初期化します.拡大路を探していますが、検査しながら(x,y)、等子図でなければ、slack[y]を元の値とweight(x,y)-lx(x)-ly(y)の小さい値に変えます.このようにして、トップフラグを変更する際に、インターリーブツリーのY頂点ではないすべてのslack値の中の最小値をd値として取れれば良い.ただ、トップマークを修正したら、インターリーブツリーのY頂点にないすべてのslack値をマイナスします.
コード
以下のコードはHU 2255に基づいて小康に走って大金を儲けます.
x_y_q_,帯域権二分割図の最適整合(KMアルゴリズム)は、https://blog.csdn.net/x_y_q_/uarticale/details/51927054(偏向原理)
SixDayCoder,二分割図の最適な完璧なマッチング――KMアルゴリズム,https://blog.csdn.net/sixdaycoder/article/details/47720471 (概念に向かって)
wenr,KMアルゴリズム詳細解+テンプレート、https://www.cnblogs.com/wenruo/p/5264235.html (アルゴリズムフローの紹介)
kuangbin、Kuhn-Munnkresアルゴリズム(二分割図の最大権マッチ)、https://www.cnblogs.com/kuangbin/archive/2012/08/19/2646535.html (まとめに向けて)
転載先:https://www.cnblogs.com/zhanhonhao/p/11326466.html
関連概念
このアルゴリズムは個人的には最初はちょっと分かりにくいと思います.特に新しく定義されたものは何をするか分かりません.しかし、アルゴリズムの実行過程と原理を知ると、これらの概念の意味と背後の役割がだんだん明らかになります.ですから、とりあえず関連概念を並べてみて、大体のイメージがあればいいです.アルゴリズムの流れを知ると、原理の中にこれらの概念があります.その時に帰ってきて詳しく見ればいいです.
完全一致:定義設定G＝二部図、|V1|≦𞓜V2|、MはGの中で一番大きなマッチングで、かつ|M124;V 1𞓜＝124; V 1|である.MはV 1からV 2までの完璧なマッチングと称される.つまり、一つのセットの点を全部別のセットに合わせるということです.(最初にこの概念を紹介したのは、多くの概念の中で完璧なマッチングが言及されていたからです.しかし、完璧なマッチングとは何か分かりませんでした.)上記の定義では、124 V 2 124＝124 V 1𞓜を見れば、完璧にマッチすることができます.
二分割図の最適なマッチング:二分割図の各辺に対して一つの権利(非負)があり、すべての整合辺の権利と最大、最適な完全なマッチングを行うように、完璧なマッチングスキームが要求される.(特殊なのは、すべての辺の権利が1の場合、最大の整合問題である)
二分割図の帯域権整合と最適整合:何が二分割図の帯域権整合ですか?二分割図の帯域権整合は、セットの中の辺の権利値の和が最大または最小になるように、一致セットを求めることである.二分割図の最適なマッチングは、必ず完全に一致するものであり、これに基づいて、一致するサイド重みの和が最大または最小であることが要求される.二分割図の帯域権整合は最適整合と等価ではなく、互いに含まれていない.
以下はいくつかの変換の考え方です.
KMアルゴリズムは最も大きな権力と完全なマッチングを求めていますが、もし最小権の完全なマッチングが要求されたら、どうすればいいですか?方法はとても簡単で、すべてのサイドの権利の値をその反対の数だけ取って、最も大きい権力が完全に一致することを求めて、一致する値は更に反対の数を取ります.
KMアルゴリズムの運行要求は完全なマッチングが必要です.もし一番大きな権力整合を求めたら、どうすればいいですか?依然としてとても簡単で、存在しない辺権を0に与えます.
KMアルゴリズムで求められた最も大きな権利整合は、エッジの値と最大であり、もし私がサイド権の積が最大であれば、どのように転化しますか?やはり難しくないです.一つ一つの辺権は自然対数を取って、そして最大の和権整合を求めて、求めた結果aはまたe^aを算出します.これは最大積マッチングです.精度の問題に至っては、もっといい方法はない.
以下はアルゴリズムが必要として確立された概念である.
トップフラグ:各ノードと別のセットにおけるノードとの間の最大値
実行可能トップラベル:元の図のいずれかの結点に対して、結点の最上位の値を求める関数L(node)を与えます.配列lx(x)を用いて集合Xにおける接合点の最上位値を記録し,集合Yにおける接合点の最上位値を配列ly(y)で記録した.また、原図のいずれかの辺\(edge(x,y)\)については、\(lx(x)+ly(x)>=weight(x,y)\)が満足されます.
等価子図:G(V,E)を二部図、G'(V,E')を二部図の子図とする.G'のどの辺に対しても満足するなら、\(lx)+ly(y)==weight(x,y)\)と言います.G'(V,E')はG(V,E)の等価子図または等しい子図(Gの生成子図です.
アルゴリズムフロー
ここには比較的に良い男女が対象のガイドブログを持っています.KMアルゴリズムの実行過程を説明しました.生き生きとしています.どのようにペアリング条件を満たしていますか?満足していない場合はどうすればいいですか?途中で期待値を下げるdはどのように求められますか?ペアリング失敗の期待値を変更した後にこれらの変化が発生しましたか?これらの変化は新しいラウンドのマッチングに何をもたらしましたか?
ここにリンクがあります
アルゴリズムの原理:
アルゴリズムの流れを知ると、アルゴリズムの原理が気になります.なぜこのようにして、なぜこのような変化が起きたのですか?なぜこれらの変化を利用すれば最終的な結果が得られますか?
原理を詳しく紹介する前に、まずこのブログを見てもいいです.アルゴリズムの流れによって原理を紹介します.直感的に感じられます.書いたのはやはりはっきりしています.字がちょっと小さいです.
ここにリンクがあります
アルゴリズムの正確性は以下の定理に基づいています.
二分割図中のすべての満足\(lx)+ly(y)==weight(x,y)\)の辺(x,y)からなるサブ図(等子図という)が完全に一致すると、この完璧なマッチングは二分割図の最大の権利マッチングです.
なぜなら、二分割図のいずれかの一致について、等しいサブ図に含めると、その辺権は、すべての頂点に等しいトップ・スケールとなるからである.それがある辺がイコールのサブマップに含まれていない場合、その辺権とすべての頂点より小さいトップ・スケールと(すなわち最適なマッチングではない).従って、等分子図の完全一致は、必ず二分割図の最大の一致である.
初期時は\(lx(x)+ly(y)==weight(x,y)\)恒を成立させるために、lx(x)を頂点Xiに関連する辺の最大権、ly(y)=0とする.現在の等しいサブダイアグラムが完全に一致していない場合、等しいサブダイアグラムが完全に一致するまで、トップスケールを以下の方法で修正する.
現在の等しいサブ図の完全なマッチングが失敗したのは、あるX頂点に対して、私たちはそれから出発するインターリーブの道が見つからないからです.この時、私達は一本のインタリーブツリーを獲得しました.葉の結点は全部X頂点です.今、私たちはインタリーブツリーの中のX頂点のトップマークを全部ある値dに減らして、Y頂点のトップマークは全部同じ値dを増加します.
1)両端はインタリーブツリーの中の辺(x,y)であり、lx(x)＋ly(y)の値は変化しない.つまり、元はイコールの子図で、今もイコールの子図です.
2)両側はインタリーブツリーの中にない辺(x,y)、lx(x)、ly(y)は変わりません.つまり、元はイコールのサブ図に属していますが、現在はイコールのサブ図に属しています.
3)X端はインターリーブツリーの中ではなく、Y端はインターリーブツリーの中の辺(x,y)であり、そのlx(x)＋ly(y)の値は増加する.もとは同じ子図ではなかったが、今は相等子図ではない.
4)X端はインターリーブツリーの中で、Y端はインターリーブツリーの中の辺(x,y)ではなく、そのlx(x)＋ly(y)の値は減少している.つまり、もともとは等子図ではなかったが、現在は等子図に入る可能性があり、等子図が拡大されている.
今の問題はd値を求めることです.ずっと成立させ、かつ少なくとも一つの辺が等しいサブ図に入るため、dは「\(Minlx(x)+ly(y)-weight(x,y)|xはインターリーブツリーにあり、yはインターリーブツリーにない」と等しいはずである.
以上はKMアルゴリズムの基本思想です.しかし、素朴な実現方法では、時間の複雑さはO(n 4)である.\(O(n)\)を探して拡大していく必要があります.拡大するたびに、最大で変更が必要です.\(O(n)\)のトップは毎回、トップを修正するたびに、列挙しながらd値を求めます.複雑さは\(O(n^2)\)です.実際のKMアルゴリズムの複雑さは\((n^3)\)までできます.私たちはY頂点ごとに「緩和量」関数slackを与え、成長路を探し始めるたびに無限大に初期化します.拡大路を探していますが、検査しながら(x,y)、等子図でなければ、slack[y]を元の値とweight(x,y)-lx(x)-ly(y)の小さい値に変えます.このようにして、トップフラグを変更する際に、インターリーブツリーのY頂点ではないすべてのslack値の中の最小値をd値として取れれば良い.ただ、トップマークを修正したら、インターリーブツリーのY頂点にないすべてのslack値をマイナスします.
コード
以下のコードはHU 2255に基づいて小康に走って大金を儲けます.
#include
#include
#include
#define max_n 305
#define INF 0x3f3f3f3f
using namespace std;
int n;//
int love[max_n][max_n];// ，
int ex_girl[max_n];//
int ex_boy[max_n];//
int vis_girl[max_n];//
int vis_boy[max_n];//
int slack[max_n];// ， d
int match[max_n];//
int dfs(int girl)
{
vis_girl[girl] = 1;
for(int boy = 0;boy-1)
{
ans += love[match[i]][i];
}
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i = 0; i x_y_q_,帯域権二分割図の最適整合(KMアルゴリズム)は、https://blog.csdn.net/x_y_q_/uarticale/details/51927054(偏向原理)
SixDayCoder,二分割図の最適な完璧なマッチング――KMアルゴリズム,https://blog.csdn.net/sixdaycoder/article/details/47720471 (概念に向かって)
wenr,KMアルゴリズム詳細解+テンプレート、https://www.cnblogs.com/wenruo/p/5264235.html (アルゴリズムフローの紹介)
kuangbin、Kuhn-Munnkresアルゴリズム(二分割図の最大権マッチ)、https://www.cnblogs.com/kuangbin/archive/2012/08/19/2646535.html (まとめに向けて)
転載先:https://www.cnblogs.com/zhanhonhao/p/11326466.html