分段最小二乘法，不了解这种动态规划的概念

Question

我尝试用Python实现这个算法已经有几天了。我不断地回到它，只是放弃和沮丧。我不知道怎么回事。我没有人可以请求帮助，也没有任何地方可以去寻求帮助，所以我来到这里。在

PDF警告：http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

我不认为这是一个清楚的解释，我肯定不明白。在

我的理解是：

我们有一组点（x1，y1），（x2，y2）。。我们想找到一些最适合这些数据的行。我们可以有多条直线，这些直线来自于给定的a和b论坛（y=ax+b）。在

现在算法从末尾开始（？）并假设点p（x_i，y_i）是线段的一部分。然后注释说最优解是{p1。π−1}正（最佳）线通过{pi。请注意。对我来说，就是到点p（x_i，y逖i），然后后退，找到另一条穿过其余点的线段。现在最佳解决方案是这两条线段。在

然后它进行了一个我无法理解的逻辑跳转，并说“假设最后一个点pn是从p_I开始的段的一部分，如果Opt（j）表示第一个j点的成本，e（j，k）表示 通过点j到k的最佳直线的误差，然后Opt（n）=e（i，n）+C+Opt（i−1）“

还有算法的伪代码，我不明白。我知道我们想迭代点列表，找到最小化OPT（n）公式的点，但是我没有遵循它。这让我觉得很蠢。在

我知道这个问题是个棘手的问题，不容易回答，但我只是在寻找一些关于理解这个算法的指导。我为PDF文件道歉，但我没有一种更简洁的方式来向读者传达关键信息。在

感谢您抽出时间阅读本文，我很感激。在

Answer 1

最小二乘问题要求找到一条与给定点最匹配的直线，并且有一个很好的闭合形式解。将此解作为求解分段最小二乘问题的基元。在

在分段最小二乘问题中，我们可以有任意数量的线段来拟合给定的点，并且我们必须为每一个使用的新线段支付费用。如果使用新线段的成本为0，我们可以通过将一条单独的线穿过每个点来完美地拟合所有点。在

现在假设我们正在寻找与n个给定点最匹配的线段集。如果我们知道n-1子问题的最佳解：第一个点的最佳拟合，前2个点的最佳拟合，…，前n-1个点的最佳拟合，那么我们可以计算出含有n个点的原问题的最佳解，如下所示：

第n个点位于一个线段上，该线段从某个较早的点i开始，对于某些i=1，2，…，n。我们已经解决了所有较小的子问题，即少于n个点，因此我们可以找到n个点的最佳拟合，从而使：

第一个i-1点的最佳拟合成本（已计算）+ 最适合点i到n的单线成本（使用最小二乘问题）+ 使用新段的成本

使上述数量最小化的i值给出了一个解决方案：对子问题i-1和通过点i到n的线段使用最佳拟合

如果你需要更多帮助，我已经写了一个算法的解释，并在这里提供了C++实现：^ a1}