How to find the minimum difference between two linear functions?

muscle1

Whether to think about seeking the minimum | Z | as the minimum Z * Z

gtxawp

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

To
if (Z> (a*X-b*Y))
Right~~~~~~~~~~~

muscle1

suny00059X and Y exhaustion may result in orders of magnitude of calculation time, I thought of a method of exhaustive X or Y only, the time complexity is reduced by an order of magnitude, see if it works. The preliminary test results seem to be fine.

#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;
The
    if(b == 0) return min(fabs(a * Xmin), fabs(a * Xmax));
    if(a == 0) return min(fabs(b * Ymin), fabs(b * Ymax));
The
    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;
The
        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

I think the idea of ​​lhempiremakes sense. The following is my analysis:
1. Z = A*X-B*Y ==> Y = (A/B)*X-(Z/B), where B != 0;
2. For the case where A and B are known, another C = (A/B), D = (Z/B), so that the equation can be written as:
  Y = C*X-D;
3. We are not too familiar with this equation. It is a simple linear equation. If drawing a graph, this equation represents a series of straight lines with a fixed slope and a translation along the Y axis;
4. Now that we know the range of X and Y, it is a rectangular area drawn in the picture;
5. In this way, the limit value of Z must occur when the straight line passes through the four vertices of the rectangular area. Since we know the range of X and Y, the four vertices of the rectangle are known. Z can be obtained by bringing it into the equation.

muscle1

Explain my method. For z=|a*Xb*Y|, there is nothing to say about the case where a and b are equal to 0, and the minimum value of Z is directly obtained. When both a and b are not 0, The original question can be seen as seeking the minimum value of z/b=|a/b*XY|, let c=a/b, then the problem becomes to find the minimum value of |cX-Y|, because we know X And Y are integers, traverse X from Xmin to Xmax, find cXi, determine the relationship between cXi and Ymin, Ymax: If cXi is in (Ymin, Ymax), the minimum value of |cXi-Y| will not exceed 0.5, if fabs(cXi-(int)(cXi))<0.5, take fabs(cXi-(int)(cXi)), otherwise take 1-fabs(cXi-(int)(cX)); if cXi<=Ymin, Then the minimum value of |cXi-Y| is Ymin-cXi; if cXi>=Ymax, then the minimum value of |cXi-Y| is cXi-Ymax. In this way, Xi can find |cX-Y| after traversing X from Xmin to Xmax The minimum value of, and finally multiplied by fabs (b), is the minimum value of Z required.

lhempire

In fact, the situation with or without absolute value is similar
We still look at this space map, it becomes two half planes
Intercept on the plane z=0
After limiting the range of x and y, if the result of the interception is that both half planes are involved, then the minimum z must be 0
Otherwise, it is similar to the situation without absolute value

How to determine whether it is one half plane or two half planes in the range of x and y?
This is also very simple. Use the intersection relationship between the line ax-by=0 and the rectangle defined by x and y.