多数派問題
配列v[1…n]の各要素v[i](1<=i<=n)がm個の要素の1つに対応すると仮定し、ここでm個の要素は整数1〜mで表され、配列vにある要素が出現した回数が半数を超えたか否かを判断する必要がある.もし,v[1...n]がn票に対応し,1〜mがm候補に対応するならば,この問題は実際には候補の得票数が厳格に過半数(n/2より大きい)であるかどうかを判断することである.
実際の応用シーンでは,この問題を以下の方法で解決し,各候補の得票数をm要素の配列でそれぞれ記録するとともに,現在最も得票が多い候補の得票総数を記録し,v[1...n]というn枚の票を順次読み込み,各票に対応する候補の得票数に1を加えることができる.すべての票の処理が完了した後、得票数が最も多い候補者の得票数がn/2より大きいかどうかを判断する.このアルゴリズムの時間的複雑度はO(n),空間的複雑度はO(m)であった.一般に,候補者数mは定数であるため,このアルゴリズムは効率的に解くことができる.しかし,mの場合が不明であれば,この方法には大きな問題がある.初期段階では,mの規模を特定できないため,プログラム実行中に候補者の数が予め割り当てられた配列よりも大きくなる可能性があり,このときm配列の再割り当てとメモリのコピーに関与し,極端な場合,m=nであれば候補配列の複数回の再割り当てに関与することができ,アルゴリズムの効率に大きく影響する.
Robert S.BoyerとJ Strother Mooreの2人の牛人(BMアルゴリズムの提案者)は、『MJRTY-A Fast Majority Vote Algorithm』で、mの具体的な状況を知らなくてもO(n)時間の複雑さ、O(1)空間の複雑さの中で、候補者の得票数が半分を超えているかどうかを判断する巧みなアルゴリズムを提案した.このアルゴリズムは、実行中に2つの一時変数cとtを必要とし、cは現在得票数が半分を超える可能性のある候補番号を記録し、tは候補者の純超過回数を記録する.cについては,1〜mの任意の値に等しくてもよいほか,未知の状態と呼ぶ.現在の任意の候補者を表す得票数が半分以上(プログラムでは0、または-1で表すことができる)、tの最小値が0、プログラム開始時cが未知状態(c=0)、t=0であり、投票配列vを以下のように処理する.はv[i](1<=i<=n)について、cが未知の状態である場合、c=v[i]、t=1、iをインクリメントする. c=v[i],++tの場合、iはインクリメントされる. c!=v[i],--t,t=0の場合,cを未知の状態にしてiをインクリメントする. すべての投票処理が完了した後、cが未知の状態であれば、候補者の得票数が半分を超えていないことを示し、そうでなければ配列vを再遍歴し、候補者cの実際の得票総数を統計し、cの得票数が確かに半分を超えていれば、cは最終結果である.
例えば、v[1…8]={1,2,1,1,3,1,4,4}を仮定すると、投票の数は8であり、候補者の数は4である.この場合、上記のアルゴリズムで投票データを処理する過程は以下の表のように示され、ここでは未知の状態は'?'表示
i
1
2
3
4
5
6
7
8
v[i]
1
2
1
1
3
1
4
4
c
1
?
1
1
1
1
1
?
t
1
0
1
2
1
2
1
0
プログラム実行の最終結果,cは未知の状態にあり,投票配列vに対して候補者の得票数の過半数が存在しないことを示す.
v[1…9]={1,2,1,1,3,1,4,4,1}の場合,cの最後の状態が1である場合,配列vを再遍歴し,候補1の得票数が確かに過半数であるかどうかを調べ,統計結果1は5回出現し,9/2より大きいため,候補1の得票数は過半数である.
v[1…9]={1,2,1,1,3,1,4,4,4}の場合,cの最後の状態は4であり,配列vを統計すると4が3回出現し,9/2未満であることが分かったので,投票集合vについては候補者の過半数は存在しなかった.
このアルゴリズムは、配列vを初めて遍歴することによって、可能な候補cを見つけた.このとき、配列vに対して、票の過半数の候補はcであるか、誰も票の過半数が存在しない.この結論はそれほど明らかではないので,説明する必要がある.まず、投票の順番は投票の結果に影響しないので、v[1...9]={1,1,1,1,2,3,4,4}にしてもv[1...9]={1,2,1,3,1,4,4,1}にしても、最終的に過半数を得票したのは候補1なので、私たちは自分の必要に応じて、投票の順番を調整することができます.第1回配列vを遍歴した結果c=c′であると仮定すると、このようにして投票配列における投票の順序、1枚のc′、1枚の他の候補者の投票、1枚のc′、1枚の他の候補者の投票を構築することができ、このようにしてv[1...n]={c′、x,c′,x,...}が構築され、xはc′を除く他の任意の候補者の投票を表し、これにより、c'とxを対応させることができ、c'の出現回数がn/2より大きいため、c'の総数は必然的に他のすべての候補者の票数の和より大きいので、この方法で投票を並べ、最後に必然的にc',c',c',......連続的に現れる場合、本アルゴリズムによれば、以前のすべてのペアのc'、x処理が完了した結果はc=?後続はすべてc'であるため、実行の最終結果は必ずc=c'であり、vのある候補者c'の得票数が半数を超えると、実行結果は必ずc=c'であることを示している.
cが最終的に不確定状態であれば、この時点で最も得票の多い候補c'の票数はn/2にすぎず、この時点でどの候補も得票の過半数は存在しない.
もちろん、得票数が過半数でcが未知でない場合もある.したがって、アルゴリズムは、候補cの真の得票数を再統計し、本当に得票数が半分を超えたかどうかを決定する必要がある.
以下はアルゴリズムコードで、候補者の番号は0から始まり、未知の状態は-1で表されます.
このアルゴリズムは得票が過半数の候補者を計算する際に投票配列を2回スキャンする必要があるため,候補者数が固定されている場合,効率は従来のアルゴリズムに及ばない.しかし、候補者の状況が不確定な場合、このアルゴリズムは影響を受けなくてもよい.特に,このアルゴリズムの多数派問題を解決する際の考え方は,確かに我々が学ぶ価値がある.
実際の応用シーンでは,この問題を以下の方法で解決し,各候補の得票数をm要素の配列でそれぞれ記録するとともに,現在最も得票が多い候補の得票総数を記録し,v[1...n]というn枚の票を順次読み込み,各票に対応する候補の得票数に1を加えることができる.すべての票の処理が完了した後、得票数が最も多い候補者の得票数がn/2より大きいかどうかを判断する.このアルゴリズムの時間的複雑度はO(n),空間的複雑度はO(m)であった.一般に,候補者数mは定数であるため,このアルゴリズムは効率的に解くことができる.しかし,mの場合が不明であれば,この方法には大きな問題がある.初期段階では,mの規模を特定できないため,プログラム実行中に候補者の数が予め割り当てられた配列よりも大きくなる可能性があり,このときm配列の再割り当てとメモリのコピーに関与し,極端な場合,m=nであれば候補配列の複数回の再割り当てに関与することができ,アルゴリズムの効率に大きく影響する.
Robert S.BoyerとJ Strother Mooreの2人の牛人(BMアルゴリズムの提案者)は、『MJRTY-A Fast Majority Vote Algorithm』で、mの具体的な状況を知らなくてもO(n)時間の複雑さ、O(1)空間の複雑さの中で、候補者の得票数が半分を超えているかどうかを判断する巧みなアルゴリズムを提案した.このアルゴリズムは、実行中に2つの一時変数cとtを必要とし、cは現在得票数が半分を超える可能性のある候補番号を記録し、tは候補者の純超過回数を記録する.cについては,1〜mの任意の値に等しくてもよいほか,未知の状態と呼ぶ.現在の任意の候補者を表す得票数が半分以上(プログラムでは0、または-1で表すことができる)、tの最小値が0、プログラム開始時cが未知状態(c=0)、t=0であり、投票配列vを以下のように処理する.
例えば、v[1…8]={1,2,1,1,3,1,4,4}を仮定すると、投票の数は8であり、候補者の数は4である.この場合、上記のアルゴリズムで投票データを処理する過程は以下の表のように示され、ここでは未知の状態は'?'表示
i
1
2
3
4
5
6
7
8
v[i]
1
2
1
1
3
1
4
4
c
1
?
1
1
1
1
1
?
t
1
0
1
2
1
2
1
0
プログラム実行の最終結果,cは未知の状態にあり,投票配列vに対して候補者の得票数の過半数が存在しないことを示す.
v[1…9]={1,2,1,1,3,1,4,4,1}の場合,cの最後の状態が1である場合,配列vを再遍歴し,候補1の得票数が確かに過半数であるかどうかを調べ,統計結果1は5回出現し,9/2より大きいため,候補1の得票数は過半数である.
v[1…9]={1,2,1,1,3,1,4,4,4}の場合,cの最後の状態は4であり,配列vを統計すると4が3回出現し,9/2未満であることが分かったので,投票集合vについては候補者の過半数は存在しなかった.
このアルゴリズムは、配列vを初めて遍歴することによって、可能な候補cを見つけた.このとき、配列vに対して、票の過半数の候補はcであるか、誰も票の過半数が存在しない.この結論はそれほど明らかではないので,説明する必要がある.まず、投票の順番は投票の結果に影響しないので、v[1...9]={1,1,1,1,2,3,4,4}にしてもv[1...9]={1,2,1,3,1,4,4,1}にしても、最終的に過半数を得票したのは候補1なので、私たちは自分の必要に応じて、投票の順番を調整することができます.第1回配列vを遍歴した結果c=c′であると仮定すると、このようにして投票配列における投票の順序、1枚のc′、1枚の他の候補者の投票、1枚のc′、1枚の他の候補者の投票を構築することができ、このようにしてv[1...n]={c′、x,c′,x,...}が構築され、xはc′を除く他の任意の候補者の投票を表し、これにより、c'とxを対応させることができ、c'の出現回数がn/2より大きいため、c'の総数は必然的に他のすべての候補者の票数の和より大きいので、この方法で投票を並べ、最後に必然的にc',c',c',......連続的に現れる場合、本アルゴリズムによれば、以前のすべてのペアのc'、x処理が完了した結果はc=?後続はすべてc'であるため、実行の最終結果は必ずc=c'であり、vのある候補者c'の得票数が半数を超えると、実行結果は必ずc=c'であることを示している.
cが最終的に不確定状態であれば、この時点で最も得票の多い候補c'の票数はn/2にすぎず、この時点でどの候補も得票の過半数は存在しない.
もちろん、得票数が過半数でcが未知でない場合もある.したがって、アルゴリズムは、候補cの真の得票数を再統計し、本当に得票数が半分を超えたかどうかを決定する必要がある.
以下はアルゴリズムコードで、候補者の番号は0から始まり、未知の状態は-1で表されます.
int Majority(const int array[], size_t array_size)
{
unsigned int i;
int candidate = -1;
unsigned int times = 0;
for(i = 0; i < array_size; ++i)
{
if(candidate == -1)
{
candidate = array[i];
times = 1;
continue;
}
if(candidate == array[i])
{
++times;
continue;
}
if(--times == 0)
{
candidate = -1;
}
}
if(candidate == -1)
{
return -1;
}
for(i = 0, times = 0; i < array_size; ++i)
{
if(array[i] == candidate)
{
++times;
}
}
if(times > array_size / 2)
{
return candidate;
}
return -1;
}
このアルゴリズムは得票が過半数の候補者を計算する際に投票配列を2回スキャンする必要があるため,候補者数が固定されている場合,効率は従来のアルゴリズムに及ばない.しかし、候補者の状況が不確定な場合、このアルゴリズムは影響を受けなくてもよい.特に,このアルゴリズムの多数派問題を解決する際の考え方は,確かに我々が学ぶ価値がある.