Category: 算法艺术

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

最近没有怎么更新博客,因为一直比较忙。最近发现所里在做的一个项目中,可以抽出一部分内容和0-1背包问题、子集合加总问题非常相似(虽然表面上不容易看出相似点),所以看了一些这方面的资料和论文,这里主要对问题特点和算法思想做一些整理。
这类问题其实很有意思,做数学和做计算机的人都会研究,而且我这里将要提到的论文都是做计算机的人所写的。

问题简述
0-1 Knapsack Problem (0-1背包问题,下面简称KP)和Subset Sum Problem (子集合加总问题,下面简称SSP)是经典的NP完全问题。
两个问题简要描述如下:

KP:有$n$个物品要放入背包,第$i$个物品的价值为$c_i$,占据体积为$v_i$,背包的总容积为$V$,要选择一部分物品放入背包,使得他们的总价值最大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum v_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选取第$i$个物品进背包,等于$1$就代表放入背包,等于$0$代表不放入背包。

SSP: 给一个集合$\{c_1, c_2, \ldots, c_n \}$,还有一个目标值$V$,问能否选出一个子集,使得子集中元素求和刚好等于$V$。我们一般考虑的是他的另一种表述方式:选出一个子集,使得子集中元素求和不超过$V$,且尽量大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum c_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选入子集,等于$1$就是选入子集,等于$0$就是不选入子集。

SSP是KP的特殊情况,也即当$c_i = v_i$的时候,KP退化为SSP,从问题式子上看,也完全一样了。
尽管如此,研究了KP不代表就不用研究SSP了,后面会说明这一点。

精确算法与近似算法
这两个问题都有很简单的动态规划算法可以精确求解,但可惜算法的时间复杂度是伪多项式的,也即和$V$相关,但$V$不是问题输入数据的规模,$n$才是。在ACM竞赛等算法比赛中,经常会遇到一些问题属于KP的变种,而伪多项式算法也就足够了。由于网上资料很多,而且难度不大,这里就不详细介绍了。如果你不知道,请你搜索“动态规划求解0-1背包问题”。
这里我们更关心多项式近似算法,也即PTAS(Polynomial Time Approximation Scheme),也即对任意给定的$\epsilon$,算法可以在关于$n$的多项式时间内求得一个解,且该解和真实最优解的最多相差$\epsilon$倍。
实际上这两个问题都有FPTAS(Fully PTAS)算法,也即时间复杂度不仅要是$n$的多项式,而且还要是$\frac{1}{\epsilon}$的多项式。

KP的近似算法
KP有非常简单的近似算法。
对任意$\epsilon$,令$P = \max_i c_i$,$K = \frac{\epsilon * P } { n}$,记$c_i’ = \lfloor \frac{c_i}{K} \rfloor$ (这里$\lfloor \cdot \rfloor$表示向下取整)
则使用$c_i’$代替$c_i$求0-1背包问题,求得的$x$即为$\epsilon$近似解。这是因为每一个物品由于取整而产生的误差都很小。
而这时候,由于$c_i’$都是整数,可以使用动态规划算法求解,容易算得动态规划的状态数至多$n \lfloor \frac{ P}{K} \rfloor$个,因此整个算法的时间复杂度为$\mbox{O}(n^2\lfloor \frac{ P}{K} \rfloor) = O(n^2 \lfloor \frac{n}{\epsilon} \rfloor ) $,
算法复杂度之所以能够达到多项式,是由于取整减小了动态规划的状态数,而$K$的出现是为了控制因取整而产生的误差,$K$足够小的时候就能保证解的相对误差不会超过$\epsilon$
此算法参考 Vijay V. Vazirani写的书 Approximation Algorithms(点击下载) , 第8.1,8.2章节(第69页-70页)
虽然这不一定是最快的多项式近似算法,但暂时没看到别的算法在任何情况下复杂度都能更低。
我自己也没有想到更好的。而有趣的是我最近在思考另一个等价的问题,但在发现等价性之前,我也想出了一个思路几乎相同,复杂度完全一致的算法。现在看来,其实本质是同一个算法。

SSP的近似算法
根据前面所述,SSP是KP的特殊情况。所以KP的近似算法就可以认为是SSP的近似算法了。但是,之所以单独考虑SSP,是因为他可以求得更快。
SSP也有思路非常类似的算法,可以在一些国外的教学资料上看到。如这一篇(点击下载)。但是时间复杂度都比较高,事实上,SSP有$\mbox{O}(\min \{ \frac{n}{\epsilon} , n + \frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}) \} )$的算法。我认为这个结论是比较漂亮的,复杂度严格比上面提到的KP的算法要低,而且低很多。
为了说明算法思想,我们先再深入理解一下前面的算法。
前面的算法是用取整来控制复杂度,取整的本质事实上是将状态空间划分成若干段,每一段只取一个端点作为“代表”,这样状态数就会是多项式的,总的算法复杂度也就是多项式的。在SSP中,我们可以不事先取整,但仍然将状态空间分段,让每个段记录两个数值(也即选两个“代表”),一个是落在该段上的最小子集和(最小代表),一个是落在该段上的最大子集和(最大代表)。这样我们的状态数相当于比前面KP的算法多了一倍,而且是需要动态维护的,但是由于误差控制的更好(极端的例子是如果集合只有一个数,这么做就没有误差),没有取整那么大的误差,所以不需要分那么多段就能保证解的相对误差不超过$\epsilon$,因此最终算法复杂度会低。
此算法参考 Hans Kellerer等人的论文 An efficient fully polynomial approximation scheme for the Subset-Sum Problem (点击查看) Journal of Computer and System Sciences 66 (2003) 349–370
可以发现,这个算法是不能简单推广到0-1背包问题上的。

SSP的拓展问题——ISSP
Anshul Kothari等人在2005年研究Uniform-Price Auction Clearing(其实我也不知道这是啥问题)的论文中提出了Interval Subset Sum Problem (下面简称ISSP),他是SSP的一个推广。这个问题没有前面的问题这么有名(事实上我没看到第二篇论文讨论这个问题),但刚好我也发现了另外一个实际问题可以抽象成这个模型,所以我觉得还是很有意义的。问题简要描述如下:
给定$n$个区间$[a_i,b_i]$,对每个区间可以选择上面的一个数,也可以什么都不选,使这些数的和不超过目标值$V$,且尽量接近。对应的优化问题是
$\max_{x_i,y_i} \sum y_i * x_i $
$\mbox{s.t.} \sum y_i * x_i \le V, x_i \in \{ 0, 1 \}, y_i \in [a_i, b_i] $
至少从形式上看,他不再是线性的了,而且当$a_i=b_i$时退化为SSP。所以似乎更难了。
实际上这个问题也能改写为线性模型。
$\max_{x_i,y_i} \sum y_i $
$\mbox{s.t.} \sum y_i \le V, x_i \in \{ 0, 1 \}, y_i \in [x_i * a_i, x_i * b_i] $
从直观上看,如果$a_i$很小,$b_i – a_i$很大,这个问题似乎很容易解。我已经可以给出看上去不是太强的条件,在该条件下,ISSP是多项式可解的,具体这里就不给出了。但无论如何,In general,ISSP也是NP难问题。
Anshul Kothari等人的论文中也给出了一个FPTAS算法,比较有趣的是,这个算法和上面的SSP的算法思想是一致的,时间复杂度也是一致的。因此这一算法应当是受到上面所述的SSP的算法启发而设计的,而且是一个比较简单的推广。
此ISSP算法参考论文为 Interval Subset Sum and Uniform-Price Auction Clearing (点击查看) Computing and Combinatorics, Lecture Notes in Computer Science Volume 3595, 2005, pp 608-620

一些启示
1,SSP是KP的一个特殊情况,但是他们的近似算法复杂度却可以完全不同,这说明特殊问题可以有特殊算法。使用General的算法是可以的,但需要仔细想想问题是否有特殊的地方没发现,是否有更具针对性的算法没找到。
2,ISSP是SSP的一个推广,也即SSP是ISSP的特殊情况。但事实上ISSP并没有更难,甚至某些时候很可能有多项式算法,这说明推广了,也有可能变简单,特殊情况也有可能更难。但是特殊情况的算法思想可以借鉴用来解决推广了的问题。

从函数近似角度看softmax

我不懂softmax,但是最近好友licstar在做这方面的实验,我就了解了一点点。
我用自己的理解复述一遍。
问题大概是针对分类的,有多个$m$维观测向量且我们知道他们的类别。样本个数记为$C$,类别数量记为$n$。
现在我们构造一个线性分类器,它包括了一个$n$行$m$列的矩阵$A$,将矩阵左乘观测向量$x$,就得到某个向量$b$,这个向量各个数中最大的一个设为$b_i$,则观测向量就是第$i$类的。

从维基百科就能看到这个问题的目标函数,貌似是和概率有关,我概率学得一般,但是发现可以从函数近似的角度去看。也许很多人已经这么做了,毕竟我不了解这个模型。
我们实际上有个很直观的目标是: minimize $ sgn(\max_j b_j – b_i) $
其中$sgn(\cdot)$是符号函数,也即当$t$为正时$sgn(t)=1$,当$t$为负时$sgn(t)=-1$,当$t=0$时$sgn(t)=0$。也即$b_i=\max_j b_j$的时候,目标函数取$0$,否则取$1$,含义就是有多少个被分类错误了。然后我们求这个函数的极小值。
但是这个目标明显非常难算,不连续更不可导。
首先我们替换掉$\max $,它的一个常用光滑近似函数是 $\max_j b_j \approx \mu \ln \sum_j exp(b_j / \mu )$ ,在参数$\mu$很小的时候,他们近似相等,但是参数太小函数会性质不好。这是一个凸近似。
然后需要再来近似符号函数$sgn$,近似他的办法有很多种,为了得到凸近似,考虑到复合函数为凸的一个必要条件(不是充分条件):若$f$和$g$都是凸函数,且$f$递增,则有$f(g(x))$是凸函数。所以我们需要找一个凸的,递增的函数来近似$sgn$,并且最主要是在零点处接近$sgn$,这还真不是太好找,这个函数需要在零点从负突然上升到正,而且要凸。如果不要求是凸的话倒是很好找。
一个简单的近似就是线性函数$f(u)=u / \mu $ 当$\mu$很小的时候,他在零点附近和符号函数接近,而且线性函数也是特殊的凸函数。

综上,目标就变成了 minimize $ \ln \sum_j exp(b_j / \mu ) – b_i / \mu $
化简一下,上式中目标函数
$ = \ln \sum_j exp(b_j / \mu ) – \ln exp(b_i / \mu) $
$ = \ln (\sum_j exp(b_j / \mu ) / exp(b_i / \mu)) $
也即等价于 maximize $ \ln (exp(b_i / \mu) / (\sum_j exp(b_j / \mu ))) $
这看上去就和维基百科上给出的目标函数一致了。

用pLSA实现博文分类

pLSA应该是做文本聚类的,不是文本分类的。
不过我是杂牌军,非专业人士,自己看的pLSA,所以会yy还能用到哪里去。
出发点是这样一个问题:有若干博文,需要将他们自动分类为ACM竞赛相关博文,非ACM竞赛的技术相关博文,非技术博文三种类型。这个问题的来源是因为 blog.acmicpc.info 这个网站的需要,在完成后会实际上线使用。目前也有一个正在进行中的比赛针对这个问题: http://acmicpc.info/archives/1194
因为需要实际上线用,难点在于占用资源不能太多,运行时间不能太长,不能用第三方工具。但是可以用第三方工具做训练,预测的时候不用就行了。

题中给出了5000个文章。可以先对这5000个文章用pLSA聚类,提出主题。
首先,我们要对文章做预处理,预处理主要包括几个方面:
1)去除网页标签:正则表达式替换即可,<[^>]*>替换成一个空格。
2)html实体替换:主要包括&nbsp;替换成空格,&lt;替换成<之类的,如果用PHP语言,可以使用htmlspecialchars_decode函数。
3)分离文字和代码:有几个策略,高级一点的是检测代码位置,一般在<pre>标签中间或者<textarea>标签中间,当然也有可能两边没标签,只能根据内容检测。如果要用这个方法,则前面去除标签步骤应该后做。山寨一点的办法就是把ASCII码全当成代码分离出来,效果也还行。
4)统计每个文章的词,这里可以使用ICTCLAS做分词,建议添加一些人工词,比如一些算法相关词汇。ICTCLAS支持UTF8等多种编码格式。输出中也提供了词性,我们只需要统计名词和用户自定义词即可,其他的词都丢掉。词太多和词太少的文章丢掉,不拿来训练。

然后要用pLSA算法,可以学习这个博文:概率语言模型及其变形系列(1)-PLSA及EM算法,在看这篇之前先看文本语言模型的参数估计-最大似然估计、MAP及贝叶斯估计可能效果更好。

实际写程序,就是个迭代,说夸张点,只有加减乘除等基本运算,核心代码很短。他文章中给出了式子。
设定一个合理的主题数量,然后就可以聚类,算出$p(w_j|z_k)$,就是每个主题下选中每个单词的概率。

下面就是讨论怎么用到博客的分类中去。
根据$p(w_j|z_k)$,列出各个主题下概率最高的单词,然后人工判断他们有多大概率属于目标的三类文章。分别设定一个权值,我们可以记为$p(t_l|z_k)$,也即主题$z_k$属于文章类型$t_l$的概率。
实际预测的时候只需要关键词列表$w_j$,主题下选中各单词的概率$p(w_j|z_k)$,还有人工设定的分类概率$p(t_l|z_k)$
然后拿到一篇新文章,不必做分词和之前训练时的繁杂的预处理,只要用关键词列表扫一遍即可,直接寻找子串,每匹配上一次关键词就粗略的认为关键词出现了一次。这样简单,也不需要第三方库了。
可以跑一次只包含一个文章的pLSA,并且$p(w_j|z_k)$固定为之前算出来的数值不动,只迭代更新$p(z_k|d)$。算出$p(z_k|d)$之后,利用$\sum_k p(t_l|z_k)p(z_k|d)$算出文章属于每一类的概率。选取最高的一个概率做分类即可。

这里面人工的工作量只有设定$p(t_l|z_k)$,因为主题数很少,所以人工的工作量非常小。
当然,说归说,做起来还有很多小问题。我粗略的写了一个版本,也没仔细设定很准确的$p(t_l|z_k)$,已经就可以达到80%以上分类正确率,数据文件大小,运行时间等都满足问题要求,占用资源很少。只要再做一些细微的修正,我觉得由此再改进到90%以上应该问题不大。期待比赛中有更好的思路和程序。

这个思路应该同样可以用于更广泛的博文分类,或者新闻分类等。

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

问题描述见 http://weibo.com/1915548291/z4eTPtAnv
简单来说,就是一个小迷宫。可以重复走,但是不能倒退。经过每条边都意味着执行一次运算,现在要2011从迷宫口进去,2012从迷宫口出来。
一个思想就是广度优先搜索,能够找到最短的路径。如果对每个状态标记祖先,就能回溯找到完整路径。自己实现了一个简单的Hash,因为最终步数并不多,所以对Hash的要求也不高。
之后又在广度优先搜索的基础上进行修改,实现了双向广度优先搜索。一个点从入口开始搜,一个点从出口开始搜。需要注意的是从出口开始搜的话,所有运算都是相反的。搜的时候会有两个队列,直到两边“碰头”为止。
测试结果中可以看到,双向广度优先搜索明显更快一些。
马上光棍节了,几个常量都定义的全是1,哈哈。

Continue reading »

TopCoder Asia-Pacific 2012 解题思路

上月偶然看到网上有提到TopCoder Asia-Pacific 2012 (TopCoder亚太2012),比赛形式为马拉松,题目和传感器定位问题有些类似。因为我今年比较忙,没报名KDD CUP,也没报名TCO,GCJ,这次感觉应该有时间把这个题目做完,就尝试了一下。
题目在此 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15137&pm=11942
题目大致是说有$n (100 \le n \le 2000)$ 个10维空间上的点,每一维坐标从[0, 1000]的整数中随机选取。对于每一个点,你知道到它最近和最远的点的距离,也知道其他点到这个点距离的远近排序。每个点的每个维度都有一定概率已知,需要算出不知道的维度。

Continue reading »

晒代码——为ACMer定制的代码分享平台

本文转自 http://acmicpc.info

你有没有遇到过这样的情况:
花费一番功夫AC了一个题,觉得很过瘾,有冲动和别人分享自己的成果;
费了很大力气还是过不了某个题目的时候,真心想学习一下别人的代码;
自己的代码效率太低,想了解别人用的是什么方法。

来晒代码看看吧!
晒代码为志愿开放源代码的网友提供展示和分享的平台;
晒代码为收集到的代码进行归类,便于初学者选择某一类的代码和相应题目学习;
晒代码收集网友们自愿公开的代码,并且确保这些代码可以在各大OJ上提交正确;
晒代码专注于为ACMer的定制简单、实用的功能,目前已经支持分享PKU, HDU, SGU, ZJU四个OJ的代码,满足了大多数国内ACMer的基本需求;
晒代码也在进一步完善功能,开发插件,增加OJ支持的计划当中。

这就是晒代码——送给全国ACMer的元宵节礼物,欢迎访问 http://shaidaima.com

2011 ACM ICPC 成都赛区网络赛 (HDU 4035) 解题报告补充

本人是退役ACMer,本Blog原则上不发ACM解题报告,因昨天网络赛汇总到的第5题Maze解题报告没有提供相应代码,我按照该解题报告写了一份代码,已经AC,代码供其他人参考。
解题报告的链接为:http://blog.163.com/scaulyd@126/blog/static/155226395201181183149326/,看代码请参照该解题报告。

Continue reading »

Masyu Puzzle

Masyu Puzzle也叫Pearl Puzzle,是一个和数独有一定相似处的逻辑游戏,但远远没有数独有名,目前在维基百科上连中文解释都还没有。网上搜到中文名称有翻译为“串珠”和“黑白珠链”的,但是无论哪种翻译都不是足够的权威。解Masyu Puzzle很有意思也很有难度,一个20*20大小的就足够让大多数人动一番脑筋了。

Continue reading »

PKU2011ACM校赛总结&简要解题报告

昨日和wrj组队去打PKU校赛,本来觉得队内阵亡一人(有事出差)之后,应该元气大伤,却出乎意料的超常发挥,拿到了很不错的名次。准备按照当时的做题顺序一一记录一下每个题目的思路,希望对同去参加的其他队伍有所帮助。

Continue reading »

三角形计数的一些问题及思路

今年ACM竞赛大陆的几个网络赛中,出现了两个有关三角形计数的问题,一个是天津赛区,一个是福州赛区。
天津赛区在前,但个人认为福州赛区的那个题目更难一些。

Continue reading »