我一直在尝试用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道歉,但我没有更简洁的方式将重要信息提供给读者.
感谢您的时间和阅读本文,我很感激.