Tag Archive: DP

[RL Note] 时序差分学习的优势

1. 时序差分学习的优势   时序差分(TD)学习结合了动态规划(DP)和蒙特卡洛(MC)方法的关键思想,主要有一下优势: TD 像 MC 一样不需要环境模型,可以直接从经验中学习;而 DP 需要环境模型。 TD 像 DP 一样可以自举,而 MC 无法自举。 TD 可以在线增量地更新,DP 和 MC 都无法做到这一点。 TD 可以渐进地收敛到正确的预测值,而且通常收敛得比 MC 快。

URAL 1238. Folding

1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1238 1238. Folding Time limit: 1.0 second Memory limit: 64 MB Bill is trying to compactly represent sequences of capital alphabetic characters fr…
Read more

最大图样问题

  在最大正方形问题一篇中介绍了寻找最大正方形的方法,同样的方法稍加变化,即可用于寻找最大图样。 0. 问题描述   有M*N个正方形格子,其中一些格子涂成了蓝色,如图1中左图所示。求蓝色格子所能构成的最大十字的高度。图1中左图蓝色格子所能构成的最大十字高度为5,标记为深蓝色,如图1中右图。 1. 思路   十字不同于正方形,难以将寻找大十字的问题分解为寻找小十字的问题,那么考虑将十字拆分成为更加…
Read more

最大正方形问题

0. 问题描述   有M*N个正方形格子,其中一些格子涂成了蓝色,如图1所示。求蓝色格子所能构成的最大正方形边长。图1中蓝色格子所能构成的最大正方形边长为3。 1. 预处理   使用g[i][j]表示以第i行第j列的格子为右下角,所能构成的最大正方形的边长。对g[i][j]进行初始化: 如果格子为白色,令g[i][j] = 0; 如果格子为蓝色,令g[i][j] = 1。   得到结果如图2。注意…
Read more