1. 引言
众所周知,对于求根类的问题,二分法是最快的算法。如解决以下问题:
甲和乙在进行一项游戏,甲随机记下某个在1至1000内的自然数让乙来猜,乙依据某种固定的选取整数的方式来猜数,乙每猜一个数,甲就会告诉乙这个数是否为甲记下的数,若不是,则会告诉乙他的猜测是偏大还是偏小,那么乙如何选取整数可以最快地猜到甲记下的数字?
2. 问题描述
将上述问题的一般形式转化为一个数学问题:
从小到大连续取n (n不为0或无穷)个整数
,组成集合
,等概率地随机抽取一个数
。
取
将集合A分为两个集合:
与
判断
是否成立,若不成立,则判断
是否成立。
若
成立,则取
将集合
分为两个集合:
与
。
若
不成立,则取
将集合
分为两个集合:
与
。
依此类推,重复以上取
以及判断的步骤。最终一定可以在有限步后取得
。
问:运用什么算法选取
,算法的平均收敛速度最快?
3. 初步分析
根据题目,实际上是对于有序序列的一个搜索问题,可以初步分析得到以下结论:
1) 根据算法的性质 [1],当选取
的方式与集合A元素个数n确定时,对于任意取定的
,最终取得
时所迭代的平均次数i唯一确定。
2) 最终取得
时对应的迭代数i不大于集合A元素个数n。
3) 每当在A的子集中选取
后,该子集必可以依据
分为两个真子集(包含空集)。
下证解决本问题的所有算法中,二分法算法可以达到平均最快的收敛速度;首先给出针对本题二分法的定义与证明所需引理。
定义1 二分法算法步骤 [2]:
Step1:取
,
。若
,则算法结束。
Step2:若
,则置集合
为更新的集合A;若
,则置集合
为更新的集合A。
Step3:更新n为集合A的元素个数,返回Step1。
比较针对本问题的各种算法的收敛速度时,由于取定任意
的概率相同,从而可以比较取得任意取定的
的迭代数的均值,均值越小的算法收敛速度越快。该均值直接从正面求解与证明较为困难,而取定任意
的概率相同,且根据集合与算法的确定性,对于某些算法当集合A的基数n与选取元素的算法确定时,每一个元素所对应的取得该元素时算法的迭代数唯一确定,因此可将解决问题思路转化为:先根据算法确定好每个元素的各项参数,再随机选取一个元素作为
的方式计算迭代数的均值。转化后的问题与原问题等价。
设元素
对应的迭代数为
,则计算均值的公式 [3]:
根据公式,在问题规模相同的情况下只需比较每个元素对应的迭代数和
,该和数越小则对应算法收敛速度越快。因此,可将元素与根据某算法取得该元素的迭代数列成表格,再计算表中所有迭代数的均值以比较各算法的收敛速度。
4. 两个命题
命题1 对于有序序列搜索问题,任何算法下全体元素所对应的迭代数中
至多出现
次。
证明:使用数学归纳法证明。
令
时,显然成立。
设
时成立,且根据结论(3),算法在选取对应的元素后,剩余可行的元素集合被算法迭代选取的元素至多分成两部分,则当
时,根据算法可以在初始集合
的至多
个互不相交的真子集中的一个选取下一个元素,因此至多有
个元素对应迭代数为
,根据数学归纳法,原命题成立。
命题2 解决有序序列搜索问题的所有算法中,二分法算法可以达到最快的平均收敛速度。
证明:根据二分法,每次取得可行区间中点的近似的元素。设
,则第
次存在
个可取元素,第i次存在
个可取元素。
根据上文列出二分法算法的元素与迭代数的对应表,再根据命题1,二分法算法使得小于i的迭代数对应的元素数达到了最大值,其余元素均为第i次迭代时所取得,不存在大于i的迭代数对应的元素,因此迭代数之和
达到了最小值,命题2成立。
注:二分法算法可以达到最快的平均收敛速度,但可以达到最快的平均收敛速度的算法并不唯一,对于不同的具体问题,只要可以满足命题1中的最多条件,即可达到最快的收敛速度。