gur*_*urk 9 python algorithm implementation
我一直在尝试用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道歉,但我没有更简洁的方式将重要信息提供给读者.
感谢您的时间和阅读本文,我很感激.
动态编程的基本前提是递归地优化问题（降低“成本”或在本例中为错误），同时存储子问题的成本，这样它们就不会被重新计算（这称为记忆化）。
有点晚了，所以我不会说得太详细，但似乎你遇到最多问题的部分是核心 DP 本身。由于“分段”质量，这里需要 DP。正如您的 PDF 所示，通过最小二乘法找到最佳拟合线很简单，并且不需要 DP。
Opt(n) - e(i, n) + C + Opt(i-1) --- 我们的成本函数，其中
C 是新线段的恒定成本（没有它，问题就微不足道了，我们只需创建新线段）每两个点的线段）
e(i, n) 是具有一条线段的点 i 到 n 的误差（非递归）
Opt(i-1) 是从第一个点到 (i-1) 的递归成本最小)th
现在的算法
确保点列表按 x 值排序
M[0] = 0 --- 不言自明
对于所有 i < j 的对 (i, j)：找到 e(i,j) ---- （这将需要嵌套for/foreach 循环，或理解式结构。将这些值存储在二维数组中！）
For (j=1..n): M[j] = min([Opt(j) for i in range(1,j) )]
所以基本上，找到任意两个可能点之间的单线成本，存储在 e 中，
找到 j 之前的最小成本，其中 j 介于 1 和 n 之间。沿途的值将有助于以后的计算，因此请存储它们！请注意，i 也是 Opt 的参数。M[n] 是总优化成本。
问您的问题 - 如何确定分段发生的位置？一切结束后，如何使用它和 M 来确定线段集？
希望这可以帮助！