最小回数で応答を得るには

質問

次のような問題を考えます。
　送信側：1人，受信側：4人（A，B，C，D）いる。
　送信側は、受信側4人それぞれの情報を獲得したい。
　受信側は、応答として、0、1で返答し、1がYES、0がNoを表すものとする。
　送信側が得られる受信の情報は、関数ask(・)から返される値である。
　関数ask(・)
　　入力：4人のだれに聞くか N1,N2,N3,N4（例：N1=1,N2=0,N3=1,N4=0）1で聞く，0で聞かない
　　出力：入力で指定した受信側の応答のOR情報（一人でもYESだったら、1が返される）
　但し、1回目：A，2回目：B，3回目：C，4回目：Dという聞き方はなしとし、初回は4人全員に聞く
　ものとする。
　いま、A=1，B=1，C=1，D=1であるとして、送信側は最小何回で受信側A～Dのそれぞれの
　情報を知ることができるか？

いま、自分が考えている方法は、
　1回目：入力　N1=1、N2=1、N3=1、N4=1（対象全員）
　　　　　出力　1
　　　　　送信側は、4人のだれかがYESと言っていることを確認。

　2回目：入力　N1=1、N2=1、N3=0、N4=0（対象A,B）
　　　　　出力　1
　　　　　送信側は、4人のうち、A,BがYESと言っていることを確認。　
　　　　　しかし、そうなると、C,DもYESの可能性がある。

　3回目：入力　N1=0、N2=0、N3=1、N4=1（対象C,D）
　　　　　出力　1
　　　　　送信側は、4人のうち、C,DがYESと言っていることを確認。　

　4回目：入力　N1=0、N2=1、N3=1、N4=0（対象B,C）
　　　　　出力　1
　　　　　送信側は、4人のうち、B,CがYESと言っていることを確認。　

　5回目：入力　N1=1、N2=0、N3=0、N4=1（対象A,D）
　　　　　出力　1
　　　　　送信側は、4人のうち、A,DがYESと言っていることを確認。　

ですが，あまり効率的であると思えません。ORをとっているので、上記でもし、1回目に1、
2回目に0が返されれば、3回目以降は、C,Dのみに聞けばよいと思い、この方法にしましたが、
A～D全員が1である状況なので、この方法では効果がないと感じています。

実際には、A～Dは4人より多い場合も想定できるようにしたいですが、今回は
擬似的な問題として、上記のような問題を考えています。

何か他によい方法はないでしょうか？
ご教授頂きたくお願い申し上げます。

回答No.3

skydaddy · ベストアンサー

関数ASK(*)がORで値を返すかぎり、複数に問い合わせるなら人数分以上の回数聞く必要があると思いますし、不定（決まらない）ことが起こります。

例示されているシーケンスだと１回目（全員に聞く）は、2回目以降に影響を与えないため不要と思われますが、例示の問い合わせだけではＡ～Ｄの送信を確認できていません。

例えば、２回目はＡＢ両者がＹＥＳではなくＡ，ＢまたはＡＢがＹＥＳです。例えばＡがＮＯ（Ａ＝０、Ｂ＝１、Ｃ＝１、Ｄ＝１）でも例示の方法では全てＹＥＳが帰ってきます。（ＡorＢ＝１、ＣorＤ＝１、ＢorＣ＝１，ＡorＤ＝１）
このケースでは、Ａ以外が１のためＯＲで複数に聞くとＡの送信内容が判りません。

同様にＡ＝Ｃ＝０、Ｂ＝Ｄ＝１でもＡＣ以外の組み合わせではORは全て１が帰ってきます。

したがって、効率的な検索方法以前に関数ASK_AND(*)のようなANDで値を返すものを合わせて用意する必要があると思います。（複数同時に聞くという条件を満たすため）

以下、ＡＮＤ/ＯＲが実装されたとした場合・・・・

もし、一人ずつ聞くより同じか少ない回数でＡ～Ｄの状態をOR等の関数を使うことで知ることができるか？ということならできないと思います。（ＡＮＤとＯＲの回答がまとめて１回で聞けても個別情報を分離するのに人数より多い回数を必要としそうです）

ＡＢＣＤが１０１０のケースだと
１）ＡＢ：ＡＮＤ＝０，ＯＲ＝１
２）ＢＣ：ＡＮＤ＝０、ＯＲ＝１
３）ＣＤ：ＡＮＤ＝０、ＯＲ＝１
４）ＡＤ：ＡＮＤ＝０、ＯＲ＝１
５）ＡＣ：ＡＮＤ＝１、ＯＲ＝１　　Ａ＝Ｃ＝１が確定
６）ＢＤ：ＡＮＤ＝０、ＯＲ＝０　　Ｂ＝Ｄ＝０が確定

ＢＤという問い合わせとＡＣという問い合わせの組み合わせがあるまで確定できない

３つ以上合わせて聞いても全てが同じという幸運を期待するもので無い限り、回数を減らすためとしては聞く意味がないと思われます。
例えば上記の例で、どの３つの組み合わせの問い合わせを入れても任意の２つ以上の問い合わせと交換することができない（等価ではない）です。（例えば、ＡＢＣという問い合わせと＃５，＃６と入れ替えられない。ＡＢＣＤ＝０１０１でもＡＢＣＤ＝１０１０と同じ返り値）

以上は、普遍的に１００％判別するのに必要な最小問い合わせ数（最悪のケース）の話であって、現実の運用では聞く順番を入れ替えるとそれより少ない回数でできることもあります。上記の例だと＃５，＃６と２回聞けば答えがわかります。（ＹＥＳ，ＮＯが３つ有るようなケースだと３回、全てＹＥＳかＮＯなら２回）これらを考慮しても平均は大体４回ちょっとになりそうですね。

回答No.5

stomachman

A,B,C,Dの答がYESなのかNOなのかを(1=YES, 0=NOとして)<Aの答 Bの答 Cの答 Dの答>と表しますと、
<0000> <0001> <0010> ... <1111>
の16通りあります。また質問の仕方を(N1 N2 N3 N4)で表しますと、これは
(0001) (0010) ... (1111)
の15通り。
　16通りの答がどれも同じ確率p=1/16で生じると仮定すると、そのうちの一つが選ばれるという事象の持つ情報量は、どの答が実現した場合でも4 Shannonです(4 = -log p ただしlogの底は2)。また、質問の仕方をどう工夫しても、YESかNOかの1bitしか出力がないのだから、1回の質問で得られる情報量は1 Shannon以下です。(情報量が1 Shannonになるのは、YESとNOがどちらも確率1/2になるように質問を選んだ場合。）質問回数をnとすれば、得られる情報量はn Shannon以下ということです。
　なので、「16通りの答がどれも同じ確率で生じる」という仮定の下では、どんなに上手に質問しても、質問回数の期待値を4未満にすることは不可能です。
　一方、16通りの答が生じる確率に偏りがある場合には、情報量の平均値
-Σp[j] log p[j]　　(logの底は2、Σはj=<0000>～<1111>についての総和）
が4未満になりますから、質問の仕方を工夫することで質問回数の期待値を4未満にできる可能性があります。

　ところで、<1111>, <0111>, <1011>, <1101>, <1110> の5つがどれも発生確率p＞0である場合、質問回数は4以下になりません。なぜなら、<1111>と<0111>を比べてみると、質問(1000)に対しては出力が違いますが、他のどんな質問に対しても出力が同じになります。だから、<1111>と<0111>を区別するためにはどうしても質問(1000)をする必要があります。同様に
<1111>と<1011>を区別するためには質問(0100)
<1111>と<1101>を区別するためには質問(0010)
<1111>と<1110>を区別するためには質問(0001)
が必要です。言い換えれば「<1111>ではない」と断言するだけのために、少なくとも4回の質問(1000)(0100)(0010)(0001)が不可欠です。

回答No.4

nag0720

＃２、＃３で指摘されているとおり、OR情報だけでは４人の情報を確定することはできません。

では、＃３さんの提案したORとANDの両方を受信できるとした場合はどうかというと、

「初回は4人全員に聞くものとする」という条件のもとでは最大５回、その条件がなければ最大４回で十分です。

考え方は、
例えばA=1,B=0,C=1,D=0のケースを単に1010と書くことにすると、
４人の状態は、0000,0001,0010,0011,0100,・・・・,1111の１６通りあります。
一方、質問の仕方は、個別質問を除くと11通りあり、
受信のパターンは、OR=0,AND=0、OR=1,AND=0、OR=1,AND=1の３通りあります（OR=0,AND=1はありえない）。
初回に4人全員に聞くと、
OR=0,AND=0 → 0000
OR=1,AND=0 → 0001,0010,0011,・・・,1110 の14通り
OR=1,AND=1 → 1111
のケースに分かれます。
最悪の回答を想定してOR=1,AND=0となった場合、２回目の質問の対象をABにすると、
OR=0,AND=0 → 0001,0010,0011
OR=1,AND=0 → 0100,0101,0110,0111,1000,1001,1011,1011
OR=1,AND=1 → 1100,1101,1110
同様に最悪の回答を想定してOR=1,AND=0となった場合、３回目の質問の対象をCDにすると、
OR=0,AND=0 → 0100,1000
OR=1,AND=0 → 0101,0110,1001,1011
OR=1,AND=1 → 1100,1011
というように常に最悪の回答になった場合のケース数が少なくなるように質問していけば５回で確定できます。

初回に４人全員に聞くという条件がなければ４回で十分です。
５人以上の場合でも、人数分の回数で確定できるでしょう。

１回の質問でORかANDの片方しか受信できないとした場合は、初回に4人全員に聞くという条件があっても８回で確定できます。

回答No.2

gohtraw

だれか一人がＮＯの場合（例えばＡとします）でも
全員⇒出力は１
ＡとＢ⇒ＢはＹＥＳなので出力は１
ＣとＤ⇒出力は１
ＢとＣ⇒出力は１
ＡとＤ⇒ＤはＹＥＳなので出力は１
となるので全員ＹＥＳの場合と区別できません。

回答No.1

Cupper-2

最小回数ですか。

１回

入力：N1=1,N2=1,N3=1,N4=1
出力：０
返事がない。まるで屍のようだ…以上！

こんなケースも考える必要があります。