| 查看: 156 | 回复: 0 | |||
| 当前主题已经存档。 | |||
longrning金虫 (小有名气)
|
[交流]
【求助】一个DP问题的实现
|
||
|
请大家伙帮忙分析解答一下我的困惑，事情源于一个DP算法的VB代码实现： 问题描述：有一组时间序列T={t1，t2,...,tN}，每个时刻对应一个速度值F={f1,f2,...fN},现在想将这个时间序列进行可变时段划分，即将原来N个时刻划分到M(M<=N)个时段内,即{(s1,e1),(s2,e2),...,(sM,eM)},然后将每个时段内的速度进行平均得到平均速度AVG([si,ei]),为了使平均之后的信息损失最小，就需要使每个时段内平均之后的误差最小，即Sum Squre Error的值最小，对于整个时间序列来说就是M个时段的SSE的和最小。即找到满足minSSE=ΣΣ(fj-AVG([si,ei]))^2, j=si->ei, i=1->M 的最优时段分割，其约束条件为： N=Σ(ei-si+1)，i=1->M si=1,eM=N si+1=ei+1 其迭代方程为： SSE*(I,k)=min{SSE*(j,k-1)+SSE([j+1,i])}, 1≤i≤N,1≤k≤M,1≤j≤i 说明： SSE*(i,k)为子区间F[1,i]内最多划分k个时段的SSE最小值。 SSE([j+1,i])= Σ(F[m]-AVG([j+1,i]))^2 其中(m=j+1->i)就是子区间F[j+1,i]划分为一个时段的SSE的值。 要得到该时间序列划分为k个时段的情况先要求k-1个时段的情况，其中第k个时段左边的边界在[2，i]之间变化。其中SSE*(1,1) 是迭代初始值，可以知道。由此可得到满足SSE*(N,M) 时各时段的起始端点以及该时段的平均速度。 不晓得问题有没有说清楚，我现在想用VB来实现这个算法，因为其他模块都是用VB写的。那位好心人能给俺指点下，伪代码也行，我现在写的感觉不对。 [ Last edited by longrning on 2008-12-19 at 14:40 ] |
回复此楼» 猜你喜欢
售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急
已经有4人回复
-
上海工程技术大学 激光智能制造课题组 2027级博士研究生招生
已经有6人回复
-
课题组招2027级博士 上海工程技术大学 激光智能制造方向
已经有6人回复
-
现代”学阀”该如何界定
已经有14人回复
-
求合成方法
已经有8人回复
-
师弟论文见刊大半年才想起来申请专利，还能抢救一下吗？
已经有4人回复
-
有机合成以后会不会被AI改变？做科研的虫友怎么看
已经有8人回复
-
我的奶奶
已经有3人回复