[读书笔记]基于归纳的算法设计——算法引论

        没有什么能比见到创造的源泉更为重要，我认为，它比创造本身更有意义。

                                                                                    ———G.w.布莱尼兹（1646-1716）

  基于归纳的算法思想类似于数学归纳法，方法要保证两点：第一、解决问题的一个小规模事例是可能的（基础事例），第二、每个问题的解答都可由更小规模问题的解答构造出来（归纳步骤）。
        1、如果原始问题的规模为n，假设问题规模为n-1时的求解释已知的，那么只要求出从n->n-1的过程即可。
        2、如果所求的问题，有如下的性质：[P and Q]( P(n)比直接求容易，那么我们就更强的归纳[P and Q]( [P and Q](n)。
        需要注意：问题规模缩小时，必须保证子问题和原问题满足的条件必须一致；如果用更强的归纳，所使用的条件Q要证明。

1、多项式求值

问题 给定一串实数a_n,a_n-1,...,a₁,a₀,以及一个实数x，计算多项式P_n(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x ＋a_0的值

两种归纳假设的思路：a、P_n-1(x) = a_n-1x^n-1 + a_n-2x^n-2 + ... + a₁x ＋a0（假如n-1规模已知）
                                             P_n(x) =  a_nxⁿ ₊   P_n-1(x) （问题规模n->n-1）
                                   b、P'_n-1(x) = a_nx^n-1 + a_n-1x^n-2 + ... + a₁ （假如n-1规模已知）
                                             P_n(x) =  x.P'_n-1(x) + a_{0（问题规模n->n-1）
明显思路b的算法好于a。}

        _{2、最大到处子图}

问题 给定一个无向图G=(V,E)和一个整数k，试找出G的最大导出子图H=(U,F)，其中H中所有顶点的度大于或等于k，或者说明不存在这样的子图。

_{归纳思路：
       [全局观] 首先，考虑顶点数小于n的情况，如果n<=k，那么即使是完全图，也无法满足要求，如果n=k+1，只有完全图才能满足要求。（问题的终止条件）
       [归纳假设] 然后，考虑n>k+1的情况，首先假设顶点数为n-1的情况是已知最大导出子图的。（假如n-1规模已知）
                        如果顶点的度顶点去掉，并且这条边所指向节点的度要减一。（问题规模n->n-1）
说明：1、处理顶点的
            2、如果问题改成每个顶点的度小于或等于k，那么问题将变成NP，不能用同样的方法求解。}

    _{3、寻找一对一映射}

问题  给定一个集合A和一个从A到自身的映射f，寻找元素个数最多的一个子集S属于A，S满足：（1）f把S中的每一个元素映射到S中的另一个元素（即f把S映射到它自身），（2）S中没有两个元素映射到相同的元素（即f在S上是一对一函数）。

归纳思路：
       a、对于包括n-1个元素的集合，如何求解是已知的（假如n-1规模已知）   
       b、没有被任何元素映射的元素i 不可能属于集合S（换句话被映射次数为0的元素不可能属于集合S），要把元素i 删除，同时要删除f(i)元素被映射的次数。（规模n->n-1）

4、社会名流问题

问题 给定一个n x n 连接矩阵，确定是否存在一个i，其满足在第i列的所有项（除了第i_i项）都为1，并且第i行所有项（除了第i_i项）都为0

归纳思路：
        a、对于包括n-1个元素的集合，如何求解是已知的（假如n-1规模已知）   
        b、Know[i,j]=1，i不是名人去掉i，如果Know[i,j]=0，j不是名人去掉j（规模n->n-1）

最后的检验：当问题规模为1时，检验这个这个结果是否满足要求，Know[i,ca] = 1(i>=1 && i<=n && i !=ca) 以及 Know[ca,j] = 0(j>=1 && j<=n && j !=ca) 

_{5、在二叉树中计算平衡因子}

问题 给定一颗n个节点的二叉树T，计算所有节点的平衡因子。

归纳思路：
        我们已知如何计算节点数小于n的二叉树的全部节点的平衡因子。
更强的归纳假设：
        已知如何计算节点小于n的二叉树的全部节点的平衡因子和高度。（假如n-1规模已知）
        根节点的平衡因子只与子节点的高度有关，所以提出更强的假设，虽然多求了高度，但简化了计算。（规模n->n-1）

        书中其他的方法也是类似的方法，如轮廓问题，背包问题，最大子序列等，在这里就不赘述了。