USING INDUCTION TO DESIGN 使用归纳法设计算法 [7/14]

接上文：http://blog.csdn.net/jj12345jj198999/article/details/6613532

名人问题【Q5】【标题3】（不知道业界如何翻译）

在算法设计中有一个很流行的练习。这是一个非常好的例子，该例子的解答不需要扫描全部数据（甚至是数据的重要的组成部分）。在n个人中，一个名人被定义为其他人都认识但是自己却不认识其他人的人。该问题就是存在名人的情况下确定名人，只能通过以一种“您好，请问您认识站在那里的人么？”的方式提问。（假定所有的回答都是正确的，甚至是名人自己也会给出答案）我们的目标是让最小化提问的次数。由于存在n(n-1)/2对人，在最坏的情况下，如果问题被武断地提出，有可能需要询问n(n-1)次问题才行。我们不清楚我们能比最坏的情况做的更好。

在技术上，如果我们建立一个用顶点表示人的有向图，当A认识B就有一条从A到B的边，那么一个名人就对应一个汇点。（非有意的双关语）也就一个入度为n-1出度为0的顶点。该图可以用一个n×n邻接矩阵来表示，如果第i个人认识第j个人那么在该矩阵中位于第i行第j列的位置被标记为1，否则就为0。该问题也就是通过查找矩阵中尽可能少的条目确定汇点。

像往常一样，我们考虑有n-1个人和有n个人时问题的不同之处。既然由定义可知最多存在一个名人，那这里就有三种可能。其一，名人在前n-1个人中；其二，名人是第n个人；其三，这里没有名人。第一种情况最容易处理，我们只需要核对第n个人认识名人，但是名人并不认识第n个人的局面是否存在。其他两种情况就比较困难了，因为为了确定第n个人是否是名人，我们可能需要提2*(n-1)个问题。在最坏的情况下，这可能会导致n*(n-1)个问题（这是我们试图避免发生的）。我们需要另一种解法。

这里的技巧在于从逆向考虑这个问题。确定一个名人可能很难，但是确定某个人不是名人可能要简单很多。毕竟，很明显在这里非名人要比名人多。把某人排除出考虑对把问题规模从n缩减到n-1来说已经足够了。此外，我们不需要排除出特定的人，任何人都可以。假设我们问Alice她是否认识Bob，如果她认识她就不会是一个名人，如果她不认识
那Bob就不会是一个名人。我们可以通过一个问题排除出他们中间的一个。

现在考虑上面列出的三种情况。我们不只是任意挑选一个人作为第n个人。我们使用上面的思想去排除出Alice和Bob中的一个，然后对其余包含n-1个人的问题进行求解。我们保证情况2不会发生，因为排除出去的人不可能是名人。此外，如果情况3发生，也就是说在n-1个人中没有名人，那在n个人中也不会有名人。只有情况1存在，但是正如上面提到的，这种情况很简单。如果在n-1个人中存在一个名人，只需要提出两个问题就可以确定整个集合中是否存在名人了。否则就不会有名人存在。

所得到的算法如下。我们问A是否认识B，根据A的回答排除掉他们其中的一个。假设排除的是A，然后我们在剩下的n-1个人中寻找（通过归纳法）一个名人。如果没有名人，那么算法就终止。否则我们核实A认识名人但是名人不认识A这种局面。下面给出一个非递归的算法实现。

名人算法（已知n×n的布尔矩阵）
begin
   i:=1;
   j:=2;
   next:=2;
   {在第一步中我们排除了除了一个候选人以外的所有人}
   while next≤n do
      next:=next+1;
   if Know[i,j] then i:=next;
      else j:=next;
   {我们排除i和j中的一个} 
   if i=n+1 then candidate:=j else candidate:=i;
   {现在我们核实该候选人是否确实是名人}
   wrong:=false;k:=1;
   Know[candidate,candidate]:=false;
     {只是一个用来测试的虚拟变量}
   while not wrong and k≤n do
      if Know[candidate,k] then wrong:=true;
   if not Know[k,candidate] then
      if candidate ≠ k then wrong:=true;
   k:=k+1；
   if not wrong then print"candidate is a celebrity!"
end;

复杂度：这里最多只需要提3*(n-1)个问题。在第一步中提n-1个问题从而从候选人中排除掉n-1个人。为了确定那个候选人是否是名人最多只需要提2*(n-1)个问题。上面给出的解答表明可以在邻接矩阵中仅查找O(n)条记录就能确定一个名人，尽管从推理上认为问题的解法与n(n-1)项输入都密切相关。（这里也可能节省掉额外的log2(n)【取下限】次提问，只需要在验证过程中以及提问排除过程中注意避免重复即可）

总结：这个极佳的解法的核心思想在于用一种明智的方式把问题规模从n缩减到n-1。这个例子表明了有时候在更有效的进行问题规模的缩减上花一些努力（在该例子中提出一个疑问）是值得的。此外，逆向思维在本问题中显得很有用。与其去寻找一个名人我们不如尝试去排除非名人。这在数学证明时经常用到。一个人不需要直接去尝试解决问题。有时解决能够给原先问题带来解答的相关问题要简单一些。为了找到这些相关的问题，在开始时使用成品（数学证明中的得到的定理），然后逆向进行我们的工作看看实现这个成品需要什么东西，这往往是很有用的做法。

最后

以上就是玩命八宝粥为你收集整理的USING INDUCTION TO DESIGN 使用归纳法设计算法 [7/14]的全部内容，希望文章能够帮你解决USING INDUCTION TO DESIGN 使用归纳法设计算法 [7/14]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。