algorithm - 最小化距离 : distance formula

Question

我正在用C写一个程序，我想通过最小化表达式来找到解决方案

D1+D2+......+Dn

其中 Di 是通过 2 点之间的距离公式计算的距离。上面的表达式在 x & y 变量中

现在我将区分这个表达式并找到解决方案。我的疑问是:

因为在上面的表达式中，所有的 Di 都会以平方根的形式出现，这将很难解决。所以我们可以解决这个表达式:

D1^2 + D2^2 + ......+ Dn^2

上述表达式产生的答案是否与解决原始问题产生的答案相同？

我检查了简单的测试用例，例如 n=2。它产生正确的答案。一般来说是这样吗？

如果不是，这个问题怎么解决？

Answer 1

即使对于 2d 距离，a^2 + b^2 的最小值与 a + b 的最小值通常不在同一位置>。当然，对于一些非常具体的有限问题集，这可能是正确的。如果你想找到一个反例，请注意正方形对长距离的惩罚过度；如果您构造一个最小值至少包含一个长距离的示例，则平方和很可能具有不同的最小值。

您要解决的问题是什么？当然，对于您的问题来说，区别很可能无关紧要；或者平方和的最小值是一个成本较低的问题，并且更容易对最终解决方案进行初步近似。

这可能是显而易见的，但如果各种距离不相关，那么对于每个单独的距离，当距离为最小值时，平方最小，因此不相关距离的总和最小，其中正方形是。

Edit Post update:您正试图找到一个质心，但它位于特定的线上。那么总的来说:你只有一个自由度，你可以做简单的微分。但是，结果将是分母为 sqrt 的分数之和；在一般情况下用代数方式解决这个问题是不可能的(AFAIK)。我不是 100% 肯定，但我认为你很幸运，因为你的距离总和没有局部最小值，只有全局最小值；在这种情况下，牛顿法将可靠且快速地收敛。

因此，如果您可以验证只有一个局部最小值的假设，您就可以自由自在，即使可以，您也可以相当可靠地获得相当不错的结果并检测何时只需将牛顿法计算的最小值与几个现实检查点(例如，每个点在直线上的正交投影)进行比较，它就会出错。