最近看的一些东西

称球问题:

给定一架天平，有n个球，其中一个是次品。
结论1 次品的重量比其他的重，称ceil(log3(n))次就能找出那个次品。
结论2 轻重不详。有一个标准球。称ceil(log3(2*n)) 次就可以找到次品，并且知道轻重。
结论3 轻重不详。称ceil(log3(2*n+2)) 次就可以找到次品，并且次品的轻重。
结论4 轻重不详。有一个标准球，称ceil(log3(2*n-1)) 次就可以找出次品。

树形动态规划,对于普通的树形(兄弟节点之间没有相互限制),直接用;对于比较特殊的(兄弟之间有相互限制的),可以先转换成二叉树,然后再dp.

搜索剪枝:一般情况下,搜索的时候必不可少的要用到剪枝,一个好的剪枝函数会很大幅度的减少运行所需要的时间,因此,剪枝相当的重要,个人认为,剪枝是搜索的核心,但是剪枝不是那么好剪的,我感觉需要多做题目,多长见识,多多积累才能在做题的时候比较好的想出剪枝的方法,毕竟对于不同的题目,似乎没有什么统一的剪枝方法,但是有三个重点:正确性,准确性和高效性/
    正确性:剪枝不能剪掉正确的支,否则结果错了,啥优化都是空的;
    准确性:剪枝的时候要力求剪准了,这样提高效率;
    高效性:有的时候通过某些剪枝确实可以进一步提高剪枝,但是,剪枝判断本身需要耗费比较大的代价,这样,可能就会影响总的效率,所以需要权衡一下,力求高效.
   然后,剪枝的同时可以使用逐步细化,分段,以及结合dp等多种方法来达到比较好的效果^_^

posted on 2007-10-09 22:47  xmx  阅读(300)  评论()    收藏  举报