剪枝搜索策略

  通常由几次迭代组成。

  在每次迭代中,它剪裁输入数据的一部分,然后递归的调用同样的算法解决剩余的问题

  几次迭代之后,输入数据的大小会变得很小,以至于可以在常量时间内解决。

每次迭代 n、 (1-f)*n、(1-f)^2 *n、…


二叉树搜索算法,在每一次比较后,都会剪掉一半的数,可以被看成是一种特殊的分而治之方法,只不过不需要解决另一半的问题,也不需要合并。


After each comparison, a half of the data set arepruned away.

Binary search can be viewed as a special divide-and-conquer method,

since there exists no solution in another half and then no merging is done.

选择问题,找到n个数中的第 k 小元素

Input: A set S of n elements

Output: The kth smallest element of S

The median problem: to find the -th smallest element.

The straightforward algorithm:

step 1: Sort the n elements

step 2: Locate the kth element in the sorted list.

Time complexity O(nlogn)

最直接的算法就是用排序算法,但是排序算法的最好复杂度是O(nlogn)

使用剪枝搜索算法解决此问题,复杂度为O(n),将数字串 S 分为三部分s1,s2,s3,然后剪枝:


|S|表示 S 中的元素个数

关键点:如何确定P,使得每一次迭代时都能够丢弃S 的一部分,不管这部分是S1,S2还是S3,可以按如下方法选择P:

首先,将n个元素分成每5个元素形成一个集合的个子集。如果需要,可以在最后的子集中加入虚拟元素

然后,对每5个元素子集排序,从每个子集中选出中位数形成新序列M = { m1,m2,m3…m(n/5) },并令P为M的中位数,

S中至少有1/4 的元素小于或等于p,至少1/4 的元素大于或等于p。

如果按照这种方法选择p,那么在每次迭代时总能减去S中至少 n/4 的元素。


算法描述如下:


时间复杂度:

令T(n)为找出第 K小元素算法的时间复杂度。由于每个子集都是常数个元素,

所以,

步骤2,O(n)

步骤3,O(n) 即 常量*n

步骤4,时间复杂度是T(n/5),使用本算法找到中位数

步骤5,时间复杂度是O(n),

步骤6,T(3/4 *n),    At least n/4 elements are pruned away during each iteration.

时间复杂度:

T(n) = T(3n/4) + T(n/5) + O(n)


那么,


则:



即T(n) = O(n)

基于剪枝搜索策略得到在最坏情况下为线性时间的解决选择问题的方法。

两变量线性规划(Linear programming with two variables)

特殊的两变量线性规划问题定义如下;

最小化 ax+by

约束为

1圆心问题(The one center problem)

定义如下:给定n个平面点的集合,要找到一个覆盖所有几个点的最小圆。



。。。

  剪裁搜索算法实例-Apriori算法 




分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注