| 查看: 135 | 回复: 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 ] |
回复此楼» 猜你喜欢
面上本子正文33页，违规吗？会被低分嘛？
已经有10人回复
-
国自然上会要求
已经有9人回复
-
博士申请
已经有5人回复
-
评审有感
已经有6人回复
-
今年审到国自然15份，谈谈感受
已经有16人回复
-
上海大学实验技术岗位非升即走
已经有8人回复
-
考博自荐
已经有6人回复
-
青C资助名额大幅增加！
已经有16人回复
-
重磅！青年科学基金项目（C类）资助增幅预计超过50%
已经有10人回复
-
我在等一个没有答案的答案
已经有3人回复
