c - 在给定一些限制的情况下最小化距离

Question

假设我的起点是 x-y 平面上的原点。

我只能以某种方式移动。 比如，有人告诉我，我的下一步行动只能是 2 个坐标点的线性组合。

我的目标是，在尽可能多的移动中找出最接近我能到达的起点的点(当然除了原点)。

例如，假设我被告知这 2 个点是 a=(13,4) 和 b=(17,5)。

因此，我能到达的距离原点最近的位置是 (1,1)。这是从 4a-3b 得到的。

我已经为它编写了一个程序。但在我看来，这个逻辑是完全有缺陷的。

但是它为我尝试过的几个测试用例输出了正确的答案。

这是我的代码

#include<math.h>
int sq(int a)
{
    return a*a;
}

int main(void)
{   
    int a,b,c,d,min=200000,i,j,n=100;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for(i=-100;i<n;i++)
    {
        for(j=-100;j<n;j++)
        {
            if(sq((i*a)-(j*c))+sq((i*b)-(j*d))<min)
            {
                min=sqrt(sq((i*a)-(j*c)))+sqrt(sq((i*b)-(j*d)));
            }   
        }
    }
    printf("%d\n",min);
    return(0);
}

请随时提供您的意见以及是否有更好的方法来解决问题。

程序中输出的答案是|x|+|y|。

Answer 1

如果您进行数学计算，您会发现有一种更简单的方法来进行详尽的搜索。

令l,m为线性组合的系数(在您的示例中l = 4和m = -3)。另外，让a = (x1,y1)和b = (x2,y2)。

那么很容易证明您需要找到 a,b 来最小化函数 f(l,m) = slm，其中 s = 符号(x1*x2 + y1*y2)。

此外，如果您可以使用非线性求解器(或者您可以编写自己的算法，因为这是一个简单的函数)，您可以迭代地找到解决方案。