VerySource

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
12
返回列表 发新帖
楼主: fjn6869930

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

[复制链接]

0

主题

5

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2020-5-25 22:15:01 | 显示全部楼层
是否考虑一下把求最小|Z|看成求最小Z*Z
回复

使用道具 举报

0

主题

1

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2020-6-12 19:30:01 | 显示全部楼层
if (Z < (a*X - b*Y))
{
        Z = a*X - b*Y;
}

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

使用道具 举报

0

主题

5

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2020-6-13 00:15:01 | 显示全部楼层
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);
}
回复

使用道具 举报

0

主题

7

帖子

8

积分

新手上路

Rank: 1

积分
8
发表于 2020-6-16 16:00:01 | 显示全部楼层
我觉得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.
回复

使用道具 举报

0

主题

5

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2020-6-19 10:15:02 | 显示全部楼层
解释一下我的方法,对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的最小值了。
回复

使用道具 举报

0

主题

3

帖子

4

积分

新手上路

Rank: 1

积分
4
发表于 2020-8-12 19:30:01 | 显示全部楼层
其实加不加绝对值情况类似
我们还是看这个空间图, 它变成了两个半平面
在z=0的平面上截取
限定x和y的范围后, 截取的结果如果是两个半平面都涉及到,那z最小一定是0了
否则,就和不加绝对值的情况类似了

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

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|CopyRight © 2008-2020|verysource.com ( 京ICP备17048824号-1 )

快速回复 返回顶部 返回列表