如何求两线性函数的最小差值？

muscle1

是否考虑一下把求最小|Z|看成求最小Z*Z

gtxawp

if (Z < (a*X - b*Y))
{
        Z = a*X - b*Y;
}

改为
if (Z > (a*X - b*Y))
吧~~~~~~~~~~

muscle1

suny00059 的X和Y都穷举可能会导致数量级的计算时间，我想了一个只穷举X或Y的方法，时间复杂度降低了一个数量级，看看行不行。初步测试结果好象没什么问题。

#include <math.h>

#define min(a,b) (((a) < (b)) ? (a) : (b))

double Zaxby(int Xmin, int Xmax, int Ymin, int Ymax, double a, double b)
{
    int i;
    double c, Zmin, dt;
       
    if(b == 0) return min(fabs(a * Xmin), fabs(a * Xmax));
    if(a == 0) return min(fabs(b * Ymin), fabs(b * Ymax));
       
    c = a / b;
    Zmin = fabs(c * Xmax - Ymax);
    for(i = Xmin; i <= Xmax; i++){
        dt = c * i;
        if(dt > Ymin && dt < Ymax){
            dt = fabs(dt - (int)(dt));
            if(dt > 0.5) dt = 1.0 - dt;
        }
        else if(dt <= Ymin) dt = Ymin - dt;
        else dt = dt - Ymax;
       
        if(dt < Zmin) Zmin = dt;
    }

    return fabs(Zmin * b);
}

main()
{
    double a = -1.3, b = 2.2;
    int Xmin = 1, Xmax = 5, Ymin = 2, Ymax = 8;
    double data;

    data = Zaxby(Xmin, Xmax, Ymin, Ymax, a, b);
}

maloneliu

我觉得lhempire 的想法挺有道理的，下面是我的分析：
1. Z = A*X - B*Y ==> Y = (A/B)*X - (Z/B),其中B != 0；
2. 对于A,B已知的情况下，另C = (A/B), D = (Z/B)，这样方程可以写成：
  Y = C*X-D；
3. 对于这个方程我们再熟悉不过了，就是简单的一次线性方程，如果画图的话，这个方程表示的就是一个斜率固定，沿着Y轴方向平移的一系列直线；
4. 既然我们知道了X,Y的范围，画在图中就是一个矩形区域；
5. 这样Z的极限值一定发生在直线经过矩形区域的四个顶点的时候，由于我们知道X,Y的范围，矩形的四个顶点是已知的，带到方程中就可以求出Z.

muscle1

解释一下我的方法，对z=|a*X-b*Y|，对a和b有一个等于0的情况没什么说的，直接就得到Z的最小值了，对a和b都不为0时，原题可以看成求z/b=|a/b*X-Y|的最小值，令c=a/b，则问题就变成了求|cX-Y|的最小值了，又因为我们知道X和Y都时整数，从Xmin到Xmax遍历X，求出cXi,判断cXi与Ymin,Ymax的关系：如果cXi在（Ymin,Ymax）中，则|cXi-Y|最小值不会超过0.5，如果fabs(cXi - (int)(cXi))<0.5,就取fabs(cXi - (int)(cXi))，否则取1-fabs(cXi - (int)(cX))；如果cXi<=Ymin,则|cXi-Y|最小值为Ymin-cXi;如果cXi>=Ymax,则|cXi-Y|最小值为cXi-Ymax.这样Xi从Xmin到Xmax遍历X后就可以求出|cX-Y|的最小值了,最后再乘以fabs(b),就是要求的Z的最小值了。

lhempire

其实加不加绝对值情况类似
我们还是看这个空间图, 它变成了两个半平面
在z=0的平面上截取
限定x和y的范围后, 截取的结果如果是两个半平面都涉及到,那z最小一定是0了
否则,就和不加绝对值的情况类似了

怎么判定在x和y的范围内,是一个半平面还是两个半平面呢
这个也很简单, 用ax-by=0这个直线和 x,y限定的矩形的相交关系就知道了