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

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

一个O(nlogn)的算法【标题4】

这里的关键思想是加强归纳假设。由于要排序我们在合并步骤需要花费O(nlogn)的时间。尽管我们知道如何直接解决这个问题，但是它耗时太长。我们能够做到在解决排序问题的同时解决最近对问题么？换句话说，我们想加强归纳假设把排序作为最近对问题的一部分包含进来从而得到一个更好的解法。

归纳假设：给定平面上一个少于n个点的集合，我们知道如何去寻找它们之间的最近距离也知道如何按照y坐标排序后输出该集合。

我们已经知道如果知道如何排序那该怎样去寻找最小距离。因此，唯一需要做的事情是如果我们知道两个含有n/2的子集排序顺序那该如何对整个集合进行排序。换句话说，我们需要把两个有序的子集合并成一个有序的集合。合并可以在线性的时间内完成（见例【1】）。因此，递归关系变成如下：

T(n)=2T(n/2)+O(n), T(2)=1,

这也意味着T(n)=O(nlogn)。该算法和上一个算法唯一的区别是按照y坐标排序时不必每次都从头开始进行。当我们执行时使用加强的归纳假设来进行排序。下面给出的是改进后的算法。该算法是由Shamo和Hoey(见[15])提出来的。

最近对算法 {一个改进的版本}
 {p1,p2...pn:平面上的点}
 begin
   按照x坐标对点进行排序
   {该排序只有在开始时执行一次}
   把该集合划分为两个相等的部分；
   递归的执行下面的步骤
      计算每个部分中最小的距离；
   按照y坐标对每个部分的点进行排序；
   把两个有序的列表合并成一个有序列表；
     {请注意我们必须在排除点之前合并，我们需要为下一阶段的递归提供有序的全集}
   把d赋值为两个最小距离中的最小者;
   排除出分割线d距离范围外的点
   按照y坐标对剩下的点进行排序
   按照y顺序扫描这些点并计算每个点和它的五个邻居之间的距离{事实上，4个就够了}
   if 这些距离中有小于d的 then
     更新d值
end;

更强的归纳法【标题2】

更强的归纳法(有时也被称为结构化归纳法)的思想在于不仅仅使用定理对于n-1(或者其他小于n的值)成立的假设，也使用定理对所有k(1≤k<n)成立的更强假设。把这种技巧转换到算法设计中需要维持一个含有所有小问题解法的数据结构。因此，该技巧通常引起更多的空间占用。我们给出一个使用这种技巧的例子。

背包问题【Q8】【标题3】

背包问题是一个很重要的优化问题。它也有很多不同的变种，但这里我们只讨论其中的一种变种。

问题：这里有n个不同大小的物品。第i个物品有一个整型的大小ki。问题是找到一个物品的子集使得该集合的大小总和正好为K，或者我们确定不存在这样的子集。换句话说，给我们一个大小为K的背包我们想把它装满物品。我们把这个问题表示为P(n,K)，第一个参数表示物品的数目，第二个参数表示背包的大小。我们假设大小是固定的。我们用P(j,k)(j≤n且k≤K)表示有j个物品和大小为k的背包问题。为了简化，我们仅关心问题的结论，也就是决定是否存在这样的一个解答。在后面我们给出如何去寻找到一个解答。

我们首先从最直接的归纳法开始。

归纳假设：我们知道如何去解决P(n-1,K)的问题。

最后

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

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