日知一录

桑丸莱Q 2017-08-11

今天没有去图书馆,近来似乎并不是很想去图书馆,也不清楚为什么,无意中看到一些PDF,有遗传算法的,还有TAOCP的几册,读了一下,我读的是基础算法,排序部分,以前我注意到,大师的书往往都很清晰,这本书也不例外,令我很惊喜的是,在stanley的《计数组合学》里出现的一些内容,Knuth也有讲,而我惊喜的地方仅仅在于,Knuth讲的部分更容易看懂,主要讲了排列的组合性质,主要让我明白了几个概念到底是指什么,诸如排列的逆,指数,杨表等。之前读计数组合学,并没有看的太懂,可能是内容太压缩的缘故,组合数学是我较为保持着兴趣关注的部分,也一直想看到一些通俗的能被我看懂的介绍,可惜遇到的不多,图书馆的组合数学书,看起来十分的基础,以及古代化,与我所知的现代的组合学差距太大。当然,我想组合数学未来还可能更为抽象和统一。

同时也看了一下优化方面的内容,诸如一些NPC问题,或者组合优化问题,这里我注意到的是线性规划的确是一种很好的工具,可以解决不少的优化问题。此外多目标规划看起来是一个更好的方法,因为能适应多个优化目标,以后可以了解一下,除此之外,就是这些优化问题的遗传算法处理了。遗传算法我认为和回溯法有一些相似之处,诸如都是求某个解向量。后来找到一个中文的NPC问题列表,十分丰富,这些问题也是很有趣的,我注意到NPC问题的一个有意思的地方在于那些创造性的归约,虽然NP问题本身很难,恐怕很难解决,但这些NPC问题之间的转化也是需要巧思的,有的转化读起来十分有趣。我想,认真的读一读NPC问题的归约是有意义的,因为很多NPC问题都十分有用,那里也包含着很多的创造性。这些问题我已经有了大致的印象,不过这些问题在现实中到底如何解决的,这方面的信息目前所知很少。此外也需要寻找更多的NPC问题的优化形式,而不仅仅是判定形式。

今天还发展了一种理论,那就是关于区间和期望的,就是区间中的点与区间两端的距离远近,可以用来刻画风险,区间中的点靠近高端风险变大,靠近低端风险变小,从而就可以以此估计期望。这种方法是否有效我不得而知,不过思路是正确的,因为它的确是刻画了某种直觉。这个思路主要是我第一次尝试使用概率论,这个问题是在考虑一个背包算法时附带出来的。注意到的是,在很多问题里,主要指现实世界里,概率论分析比回归分析可能更能刻画问题的本质。因为很多信息是不确定的,不完全的,一次性的,无法产生足够的数据供分析。概率论可以搭建出一个分析框架。只能说这里有趣的部分是比较多的。

对于这些方法的分类,有一些分类法是有用的,诸如分为选择,分配,几何分析等。它们的目的都是提供某种参照框架。基本上这部分也算是熟悉了,从理论现状到实践的方案,基本都有一个概貌。接下来就是深入的了解一些方法,试试它们的组合。

查看更多主题的豆瓣日记和相册

桑丸莱Q
作者桑丸莱Q
26日记 0相册

全部回应 0 条

添加回应

桑丸莱Q的热门日记

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端