Celebrity problem and algorithm to solve it – Algorithms and Me
There are two things to note about any candidate celebrity in party. If there are two person u and v in party and you ask u if he knows v. There are two outcomes : either u know v in that case u is definitely not celebrity as celebrity does not know anybody. Second, if u does not know v, then v is not celebrity as everybody in party knows celebrity. Any which way, you are eliminating one person of two, other goes back to list of candidates for celebrity. To start with all present at party are candidates.
At the end you will be left with one candidate. Will that be surely a celebrity? Answer is no. Because, we still need to check if he does not anybody else. Consider a case, that we never asked our last candidate the question and he survive till end, however, he knows somebody at the party. To avoid this case, let ask this last candidate the same question for each person. If he does know somebody, he is not celebrity or else he is.
Read full article from Celebrity problem and algorithm to solve it – Algorithms and Me
No comments:
Post a Comment