分段最小二乘的动态规划算法

问题描述

几天来，我一直在尝试用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，...pi−1}的最优解，加上通过{pi，...Pn}的(最佳)线’。对我来说，这只是意味着我们去到点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道歉，但我没有更好的方法将关键信息传递给读者。

感谢您抽出时间阅读这篇文章，我很感激。

---

解决方案

最小二乘问题要求找到一条最适合给定点的直线，并且有一个很好的闭合形式的解。此解决方案用作解决分段最小二乘问题的基元。

在分段最小二乘问题中，我们可以有任意数量的分段来适应给定点，并且我们必须为使用的每个新分段支付成本。如果使用新线段的成本为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++实现：http://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/