| 查看: 153 | 回复: 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.54,科目全,可伽急
已经有8人回复
-
售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急
已经有8人回复
-
国社科又开始会评了，不知道这次命运如何
已经有13人回复
-
麻烦专家们看看评委们的意见（F口面上）
已经有13人回复
-
售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急
已经有4人回复
-
售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急
已经有6人回复
-
科研人应该花精力去思考如何解决问题，而不是去凝练问题
已经有14人回复
-
要骂人了，新模版改版就是要淡化问题凝练这种虚的东西，结果有个评委还在说凝练得不够
已经有17人回复
-
基金系统什么内容也没有
已经有10人回复
-
学科评审组评审是指会评吗？
已经有5人回复
30