12月15, 2016

基础算法解惑之二分法

二分不论写得多好,总得 WA 一发。——翔哥

时隔一年,又见二分,仇人相见分外眼红。二分法作为最广为人知,最基础的算法之一,在大多数计算机科学出身的人眼中并没有什么说头,毕竟它的原理太简单,使用方法太暴力。 但其实,即便我们不去谈论日前爆出的许多科班出身的大学生面试时无法手写正确的二分法这种“大新闻”,从其本身来看,二分法无论是在原理还是在实现的细节上都是有些“莫名其妙”的。在这里,我试图探究一下其中的妙处。作为我一时兴起《基础算法解惑》的第一篇,只希望能名副其实吧。 《庄子·杂篇·天下》中有言“一尺之棰,日取其半,万世不竭”,这为我们展示了一个原始的二分画面。乍一想会让人觉得理论上就是这样,但是站在今天的我们已经知道当物质细分到一定小的数量级时,就不能再细分了。然而数学上二分法的应用也同样基于这样的事实,当范围细分到一定程度时,这个范围内的数就可以满足我们的要求。 二分法被广泛用于求方程的根,我们通过构造函数将其转换为求函数零点,用伪代码来描述:

輸入 f(x) 的定義

輸入 a 和 b 為初始區間

输入 e 为目标误差

重複如下: m := (a + b) / 2

如果 f(m) * f(a) < 0 則 b := m

否則 a := m

直至 (b-a) / 2 < e

quoted from wikipedia

适用情况

这里就存在一个关键问题,就是怎样的 f\left ( x \right ) 可以让我们执行以上操作并得出正确答案?观察伪代码,我们可以发现代码的核心在于“如果 f\left ( m \right )*f\left ( a \right ) <0 ”这句判断。而这句判断就依赖于 f\left ( x \right ) 的单调性—— f\left ( x \right ) 在其区间上必须是单调递增或者单调递减的。

精度问题

确定了得出结果的正确性以后,我们还需要注意结果的准确性,这便又回到了上述的“砍棰问题”,到底细分到多少时,范围的误差才不影响结果的准确性。

我们举一道基础的解方程题为例(HDU2199

这道题中,题目要求最终得到的方程的根要精确到小数点后第4位。那这是不是意味着当范围缩小到1e-4时,答案即为准确的呢?我们知道每一次二分都会使最初的范围减半,假设在此题中将最初的范围1e2缩小到最终的1e-4我们需要的二分次数是 n,那么有以下等式关系 100*\frac{1}{2^{n}}=0.0001 ,以此求得 n=\frac{6}{lg2}\approx 19.9 。我们尝试以次作为循环次数,编写程序验证一下我们的猜测。

#include <bits/stdc++.h>
const double eps = 5 * 1e-5;
using namespace std;
double f(double x)
{
    return 8 * pow(x, 4) + 7 * pow(x, 3) + 2 * pow(x, 2) + 3 * x + 6;
}
int main()
{
    int t;
    double y, left, right, mid;
    cin >> t;
    while(t--) {
        cin >> y;
        int cnt = 20;
        left = 0, right = 100;
        while(cnt--) {
            mid = (right + left) / 2;            
            if (f(mid) < y) left = mid;
            else right = mid;
        }
        cerr << fixed << setprecision(10) << mid << endl;
        if (fabs(f(mid) - y) < 1e-3)
            cout << fixed << setprecision(4) << mid << endl;
        else
            cout << "No solution!" << endl;
    }
}

在程序的最后,我们用一个宽松的要求——最终函数值误差不多于1e-3,来判断结果的正确性。以题目的第一组样例100为例,得到结果 1.6152381897 ,这一结果连我们预设的宽松要求都无法通过。这时候我们需要一个标准答案来对比一下误差是多少,于是我们把二分次数调节至200,程序得出的结果是 1.6151500386 ,将其视为标准答案,由此得出 x 的误差 0.0000881511 ,这一误差确实在我们的区间范围限制1e-4内,这组数据如果四舍五入的话也会得到一样的数值,但是若标准答案为 1.6151400386 ,得出答案则为 1.6152281897 ,前者四舍五入会得到 1.6151 于后者四舍五入得到的 1.6152 截然不同。 故 1e-4 的要求是不够的。这时我们想, 1e-5 是不是就足够了呢?此时二分次数 n=\frac{7}{lg2}\approx 23.3 ,我们索性使用一个更大的 30 次来检验一下。程序最终得出的结果是 1.6151499934 ,四舍五入后的结果是 1.6151 ,结果还是不对。观察得出的结果,我们很容易发现原因,此时的误差虽然只有 0.0000000452 ,但还是产生了奇妙的影响,形成了 4999 这样的不进位巧合。 从以上的例子,我们可以看出范围大小的选择并不能直接和精度划上等号关系,其实两者根本没有太明显的可以用公式表示的关系,我们只能在时间和准确性中寻找一个平衡点,尽可能的避免 49999... 这样的现象发生。故我们一般直接将循环数量确定在 50\sim 100 之间,以100为例最终的区间会是原来的 \frac{1}{2^{100}}\approx 10^{-30} 倍大,这样就很难出现影响最终答案的误差了。由于每个循环基本等时,所以也易于控制程序运行的时间,不会超时。

整数区间开闭

有时题目要求我们用二分法找出符合区间中最大(小)的那个,这就要求我们在二分的过程中考虑好区间边界的取舍。 我们知道,二分法在计算中间值的时候 mid = \frac{left + right}{2} 需要进行一次取整。边界的取舍就需要通过这次取整和每次左右区间的调整来配合实现。二分法的写法有很多种,取整方式分为向下取整 left + \frac{(right - left)}{2} 、向上取整 right - \frac{(right - left)}{2} 两种;区间开闭分为闭区间、左闭右开区间、左开右闭区间、开区间四种;退出条件分为区间长度为零 left < right 、区间长度为一 left + 1\le right 两种。 建议熟练掌握一种写法后统一使用,以免出错。

本文链接:https://sxing.xyz/post/基础算法解惑之二分法.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。