セレブの問題



  • ある n人 からなるグループにおいて、セレブとは、他の人を誰も知らないが他のすべての人からは知られているような人である。ここでの課題は、「あなたはこの人を知っていますか?」という形の質問をすることのみでそのセレブを特定することである。セレブを特定するか、グループにそのような人がいないことを判定するようなアルゴリズムを設計せよ。 そのアルゴリズムを用いて n人 の問題を解くのに必要な質問回数の最大値はいくつか?

    A celebrity among a group of n people is a person who knows nobody but is known by everybody else. The task is to identify a celebrity by only asking questions to people of the form“Do you know him/her?”Design an efficient algorithm to identify a celebrity or determine that the group has no such person. What is the largest number of questions your algorithm needs to solve the problem for n people?

    ※別スレッドの問題、《常勝不敗の強者》とはアルゴリズムが異なるものと思われます。



  • たしかに微妙に違うような・・・相違も含めて面白い問題になりそうです。



  • この解説の意味が《cが登場したあたりから》サッパリわかりません。トホホ(;´д`)

    If n=1, the one person is a celebrity by the definition. If n>1, select two people from the group, say, A and B, and ask A whether A knows B. If A knows B, remove A from the remaining people who can be a celebrity; if A does not know B, remove B from this group. Solve the problem recursively for the remaining group of n−1 people who can still be a celebrity. If the solution returned indicates that there is no celebrity among the group of n−1 people, the larger group of n people cannot contain a celebrity either because the person removed after the first question is known not to be a celebrity. If the identified celebrity is a person other than either A or B, say, C, ask whether C knows the person removed after the first question and, if the answer is“no,” whether the person removed after the first question knows C. If the answer to the second question is“yes,” return C as a celebrity, and“no celebrity” otherwise. If the celebrity found among the group of n−1 people is B, just ask whether B knows A: return B as a celebrity if the answer is “no,” and “no celebrity” otherwise. If the celebrity found among the groupof n−1 people is A, ask whether B knows A: return A as a celebrity if the answeris “yes,” and “no celebrity” otherwise.



  • @Hannibal さん
    たしかにすこしギャップがあるような<基本的にこの線であれこれいじくっていました。>
    考えてみます。



  • @Hannibal さん
    分岐1:最初のペアの内(A,B)の何れかが候補に残った場合
    分岐2:A,B以外の者=Cが候補に残った場合ですね

    お絵かきしてみます 多分今晩遅くにアップ



  • @riffraff 自己レス

    模式図

    0_1587467759866_模式図.png



  • (≧∇≦)お絵描き有り難うございます。

    分岐2でDとEとが出現していて目が ◎◎ くなりました。

    英文による解説と付き合わせて悩んでみます。
    Ψ( ̄∇ ̄)Ψ



  • 非常にマズいことに夜中に何度も目を醒まして都度夢の中で本問題に取り組んでいて一度目が覚めると小一時間は眠れないということになりました。

    朝から家事仕事をしながら頭がぼんやりとしています。

    3*n -4
    はこれでいいのかとか



  • @Hannibalさん
    おはようございます。運動不足解消の散歩前に覘きました。

    謎のアルゴリズム(3XN-4に悩まなかった訳)

    セレブ十字 知ってるN-1、知らないN-1⇒2N-2
    セレブ十字に重ならない千鳥歩きの自由度 N-2
    しめて 3N-4
    0_1587517624437_模式図2.png



  • riffraffさん、考えてみます。有り難うございます。



  • (削除しました)



  • 今考えていますが、うまくいくかどうかわからない思いついたアルゴリズムを使用しつつ

    y=必要回数=f(人数)=f(x)
    としたときに

    x:y のペアを以下のようなリストにすべくポンチ絵を書こうとあれこれ紙を消費しています。

    x:y
    1:0 = 31 -3
    2:2 = 3
    2 -4
    3:5 = 33 -4
    4:7 = 3
    4 -5
    5:10 = 35 -5
    6:13 = 3
    6 -5
    7:16 = 37 -5
    8:18 = 3
    8 -6

    x = 0, 5, 6, 7, 8
    のときに 3*x -4 にならないアルゴリズムです。

    むはあ…

    ※実を申しますと未だに、
    ①書籍「アルゴリズムパズル」の模範回答(英文版)が解読できていません。(3*n -4)

    ②また、折角頂いた riffraff さんから御提示頂いた(3*n -4)の図解の意味も掴みかねています。

    ③ ②は①の解読になっているかどうかに全力を注ぐ日々ですが…

    ④そんななか、(3*n -4)では甘いのではないかと奮闘中であります。

    願わくばどうにかこうにかうまくいきますように。

    乳(ちち)と香(か)と清流の僉(みな)にかけて

    アーメン御陀仏タージマハール
    アーメン御陀仏タージマハール
    アーメン御陀仏タージマハール

    追記:
    y = 3*(x -1) +floor(log_2(x))



  • @Hannibalさん
    うまく行きますように!
    おやすみなさい。



  • 定義:ある人aが《陰性》であることとは、
    ①:aを知らない人がグループ内に1人以上いる
    ②:aが知っている人がグループ内に1人以上いる
    としたときに、①あるいは②のどちらか、あるいは両方を満たすことである。

    定義:ある人aが《偽陽性》であることとは、aが陰性であることが質問により確認されていないことをいう。

    ※初期状態においては、質問を1回も行っていないので、グループ内のn人全員が《偽陽性》である。

    定義:ある人aが《陽性》であることとは、aが他の人を誰も知らないことが質問によって明らかになっていてかつ、aが他のすべての人からは知られていることが質問によって明らかになっていることである。

    ※定義により陽性となりうる人物は2人以上にはならない。
    陽性者がいればこの人をセレブと呼べる。

    陽性者の特定、あるいはグループ内に陽性者が不在であることの証明には、以下の2ステップからなる手段を使う。

    【1】陰性の者を(n−1)人見つけ出す。すなわち偽陽性の者が1人だけとなる。

    【2】最後の偽陽性の者が陽性であるかどうか検査し、検査に合格すれば陽性:セレブの特定になり、検査に不合格ならば陽性:セレブはグループ内にはいないことが判明する。

    以上の【1】【2】のステップでは数々の質問がなされることになるが、【1】で使われた質問のうちのいくつかが、そのまま【2】での陽性の確認において役に立つことがある。
    【1】【2】で共通に使われる質問の数が多いほど、全体の質問回数は少なくなる。【2】を睨んで【1】での質問の組み合わせを工夫しておくことが望まれる。
    (【2】では工夫のしようがない、全数検査なので。)

    (つづく)



  • n=2 の際に、【1】と【2】との具体例をまず検討することとする。

    初期状態では偽陽性である2人をAとBとする。

    まず「AはBを知っているか否か」という質問を行うとどのような情報が得られるか整理しておきたい。

    (1)この質問に対する答えがイエスのとき。

    AはBを知っているので、「他の誰も知らない」ところの陽性者ではないことが確定する。すなわちAは陰性であるとわかる。この質問に対するイエスの回答からは、Bについて確定的なことは何も得られない。

    (2)この質問に対する答えがノーのとき。

    AがBを知らないるので、Bは「他の誰からも知られている」ところの陽性者ではないことが確定する。すなわちBは陰性であるとわかる。この質問に対するノーの回答からは、Aについて確定的なことは何も得られない。

    (1)(2)のいずれのケースでも、2人の偽陽性者のうち、1人が陰性であることがわかる。

    ここまでで2人がともに偽陽性であるものとしていることに注意されたい。

    2人のうち少なくとも1人が陰性であるときには、質問に対する回答次第では、陰性者の人数が1名増加することにはならないのである。

    【1】のステップではまっしぐらに陰性者の人数を増やし偽陽性者の人数を減らすべきなので、質問「○は□を知っているか」における○も□もともに偽陽性者であることが1回の質問で得られる情報が増えることになり、このことが肝要である。
    なお、【2】のステップではこの限りではない。

    以上で「AはBを知っているか否か」という質問を行うとどのような情報が得られるか整理し終わった。

    ここからは、n=2 の際に、【1】のステップの具体例を記述する。

    2人の偽陽性者X、Yについて、「XはYを知っているか」と質問をする。どちらかが陰性であることが確実なのど、一般性を失うことなく、Yが陰性、Xが偽陽性のままとできる。

    偽陽性者の人数が1となったので、以上で【1】のステップが終わる。

    次に【2】のステップに移る。
    最後に残った1名の偽陽性者が陽性者であることの確認をすることとなる。

    (続く)


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.