Robert Anderson's Blog

http://www.cs.nctu.edu.tw/~huanpo/0519.ppt

来看一下ST算法是怎么实现的(以最大值为例）：
　　首先是预处理，用一个DP解决。设a是要求区间最值的数列，f表示从第i个数起连续2^j个数 中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。 f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f其实就等于a。这样，Dp的状态、初值都已经有了，剩下的 就是状态转移方程。我们把f平均分成两段（因为f一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段 (长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F=max（F,F）.

Idea #1: Heuristic Pruning

The easiest and most common use for heuristic functions is to prune the search space. Assume the problem is to find the solution with the minimum total cost. With an admissible heuristic function, if the cost of the current solution thus far is A, and the heuristic function returns B, then the best possible solution which is a child of the current solution is A+B. If the a solution has been found with cost C, where C < A+B, there is no reason to continue searching for a solution from this state.

This is simple to code and debug (assuming one starts with a working, but slow, program, which is how this should be used) and can yield immense returns in terms of run-time. It is especially helpful with depth-first search with iterative deepening.

原本是想貼之前拿到的講義

不過我實在有點看不太懂裡面在寫啥阿(查)

卡車說的沒錯

是很簡單的XD

假設已經知道起點和終點

而每個情況最大拓展的STATE數量是原本的R倍

我想會很有用

就學起來吧

轉貼我自己 2008.6.27的文章

轉貼我自己2008 8/6的文章