最新 | 最热门 | 最高评价

+0  0-1背包问题与子集合加总问题的近似算法

Tag: 数学规划 | 算法艺术 | 0-1 Knapsack Problem | 0-1背包问题 | FPTAS | Interval Subset Sum Problem | PTAS | Subset Sum Problem | 动态规划 | 子集合加总问题 | 近似算法
diaorui 发于 2013年07月14日 20:28 | 点击: 3120 | 展开摘要
最近没有怎么更新博客,因为一直比较忙。最近发现所里在做的一个项目中,可以抽出一部分内容和0-1背包问题、子集合加总问题非常相似(虽然表面上不容易看出相似点),所以看了一些这方面的资料和论文,这里主要对问题特点和算法思想做一些整理。

这类问题其实很有意思,做数学和做计算机的人都会研究,而且我这里将要提到的论文都是做计算机的人所写的。

问题简述

0-1 Knapsack Problem (0-1背包问题,下面简称KP)和Subset Sum Problem (子集合加总问题

查看全文: http://www.udpwork.com/item/10644.html

+0  从函数近似角度看softmax

Tag: 算法艺术 | softmax | 凸函数 | 分类器 | 近似函数
diaorui 发于 2013年04月01日 19:39 | 点击: 1446 | 展开摘要
我不懂softmax,但是最近好友licstar在做这方面的实验,我就了解了一点点。

我用自己的理解复述一遍。

问题大概是针对分类的,有多个$m$维观测向量且我们知道他们的类别。样本个数记为$C$,类别数量记为$n$。

现在我们构造一个线性分类器,它包括了一个$n$行$m$列的矩阵$A$,将矩阵左乘观测向量$x$,就得到某个向量$b$,这个向量各个数中最大的一个设为$b_i$,则观测向量就是第$i$类的。

从维基百科就能看到这个问题的目标函数,貌似是和概率有关,我概率

查看全文: http://www.udpwork.com/item/10646.html

+0  用pLSA实现博文分类

Tag: 数据挖掘 | 算法艺术 | pLSA | 分类
diaorui 发于 2013年01月30日 00:33 | 点击: 2333 | 展开摘要
pLSA应该是做文本聚类的,不是文本分类的。

不过我是杂牌军,非专业人士,自己看的pLSA,所以会yy还能用到哪里去。

出发点是这样一个问题:有若干博文,需要将他们自动分类为ACM竞赛相关博文,非ACM竞赛的技术相关博文,非技术博文三种类型。这个问题的来源是因为 blog.acmicpc.info 这个网站的需要,在完成后会实际上线使用。目前也有一个正在进行中的比赛针对这个问题: http://acmicpc.info/archives/1194

因为需要实际上线用,难

查看全文: http://www.udpwork.com/item/10649.html

+0  广度优先搜索和双向广度优先搜索求解Matrix67的迷宫问题的C语言实现

Tag: 算法艺术 | c语言 | matrix67 | 双向广度优先搜索 | 广度优先搜索 | 迷宫
diaorui 发于 2012年11月09日 17:24 | 点击: 1360 | 展开摘要
问题描述见 http://weibo.com/1915548291/z4eTPtAnv

简单来说,就是一个小迷宫。可以重复走,但是不能倒退。经过每条边都意味着执行一次运算,现在要2011从迷宫口进去,2012从迷宫口出来。

一个思想就是广度优先搜索,能够找到最短的路径。如果对每个状态标记祖先,就能回溯找到完整路径。自己实现了一个简单的Hash,因为最终步数并不多,所以对Hash的要求也不高。

之后又在广度优先搜索的基础上进行修改,实现了双向广度优先搜索。一个点从入口开始

查看全文: http://www.udpwork.com/item/10651.html
|<<<1>>>| 一共1页, 4条记录