| 查看: 159 | 回复: 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 ] |
回复此楼» 猜你喜欢
40+中年人失业后，还能找到好工作吗？
已经有13人回复
-
用NBS溴化时溶剂除了CCl4外还有什么
已经有6人回复
-
申请科研项目纯靠实力能成功吗？
已经有11人回复
-
极限拉扯，如何抉择
已经有15人回复
-
二审4个多月了还是Awaiting Reviewer Scores
已经有4人回复
-
OpenAI又攻克数学难题了，离AI做有机合成还有多远？
已经有13人回复
-
课题组会帮你通过考核么？
已经有7人回复
-
售一区SCI文章T0P，我:8O.551.O54,科目全,可十急
已经有9人回复
-
售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急
已经有8人回复
-
售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急
已经有10人回复
200