24小时热门版块排行榜

返回列表

当前主题已经存档。

longrning

金虫 (小有名气)

应助: 1 (幼儿园)
金币: 1381.6
散金: 47
红花: 1
帖子: 202
在线: 71.3小时
虫号: 504348
注册: 2008-02-16
专业: 地理信息系统

[交流] 【求助】一个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 ]

回复此楼

» 猜你喜欢

1楼 2008-12-19 14:12:15

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 longrning 的主题更新

返回列表