2017年2月16日星期四

700万小时搞定最小数独问题(ZT)

        三位爱尔兰数学家在2012年初发表了一篇论文,证明了数独至少需要 17 个初始数字才有唯一解。这个问题很难吗?其实一点也不,计算机才花了 700 万小时的 CPU 时间(CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度)就搞定了这道数独题。这 700 万个小时它了做了什么?是三位数学家的方法很笨才导致算了这么久吗?实际上,这个时间已经不算长了。看看死理性派的详细介绍你就知道了。

数独游戏和长久以来的世界难题

        18 世纪末,瑞士数学家欧拉发明了一种叫做“拉丁方阵(Latin Square)”的游戏。虽然最初这个游戏并没有风靡起来,但随着时间的推移,在 20 世纪 70 年代的美国,这个游戏以“数字拼图(Number Place)”的名字迅速流行起来,之后逐渐流传到日本、英国,到现在已经成为了红遍全球的智力游戏。
数独游戏基本规则是这样的:在一个九宫格中给出一些初始数字。玩家需要在九宫格内填入缺失的数字(1 - 9),保证:
每一行的 9 个数字各不相同
每一列的 9 个数字各不相同
每一个用粗线标识出的 3 × 3 的小正方形内 9 个数字也各不相同
        虽然规则非常简单,但其中包含的信息却毫不简单。数学家 Bertram Felgenhauer 在 2005 年证明,数独的解共有 9! × 722 × 27 × 27,704,267,971 种不同的可能组合,上面这个乘式的最后一个数还是一个质数。
一个经典的数独。图像来源:wikipedia
一个经典的数独。
        而如此多变的变化,无疑也给数学家们出了不少难题。其中一个被讨论了很久的问题是, 至少给定多少个初始数字,数独才会有唯一解? 此前已经有人给出了一些包含 17 个初始数字的数独,并利用计算机证明了其解是唯一的(对于某个给定了 17 个初始数字的数独,计算机枚举了所有可能的排列情况,只找到一个解),从而证明了 17 个初始数字的数独是可以存在唯一解的。但是长久以来都没有人知道, 16 个初始数字的数独是否存在唯一解。终于,在 2012 的元旦,都柏林大学(University College Dublin)的数学家们给出了 答案:16 个初始数字的数独不存在唯一解。

有没有解试出来

        消息一出,媒体争相报道,报道中不乏复杂的算法、超级计算机等“虽然不知道在说什么,但看起来很厉害”的词汇。事实上,研究人员用来证明这个问题的方法用一个字就可以总结,那就是——试。
        解决这个问题几位数学家最初的想法非常可爱: 只要把每一种有 16 个初始数字的数独都尝试着填一遍,自然就知道答案了。 但很可惜,因为数独的组合实在是太多了,所以即使是现在最快的计算机,也不可能在我们的有生之年穷尽所有的组合。因此,必须用一些数学的方法来减少尝试的次数,这个想法才能够实现。
他们发现,数独虽然有很多种可能的组合,但是其中一些其实是等价的。如下图,可以看到交换第一列和第二列对整个数独并没有影响。实际上任意一个合法数独的解交换两列后,都可以构成一个新的合法数独,而这个新数独和原数独就可以看做是等价的。
两种等价的数独组合
两种等价的数独组合
三位数学家总结了数独的 4 种等价变换:
⒈ 列与列的重新排列(例如上图)
⒉ 行与行的重新排列
⒊ 数字 1 到 9 的重新排列。如把原先是 1 的位置都填上 2,然后把原先是 2 的位置都填上……直到把原先是 9 的位置都填上 1 等
⒋ 网格的变换。如整个数独顺时针旋转90度,整个数独做镜像对称等
在 2006 年已经有数学家证明,排除以上几种重复后,数独总共有 5,475,730,538 个等价类。因为每个等价类里的任意一种情况都可以通过这个等价类中的其它情况经由以上 4 种变换得到,所以对每个等价类来说,我们只要考虑一种情况即可。如此一来,有非常多的组合都被我们直接排除了,计算量大大减小。

让枚举量少一点,再少一点

        虽然等价类的数量已经降低到了可以接受的范围,但问题还远没有结束。因为在选择了某个等价类中的一种情形之后,我们还需要验证这个情形的 81 个数字中是否可以选出 16 个,使得以这 16 个数为初始数字的数独有唯一解。
如果检查所有的可能情况,对于每一个等价类,我们要检查的次数就是:
/gkimage/ld/cs/bh/ldcsbh.png这显然很不幸:好不容易通过排除等价变换的方法把计算量减下去,怎么能在这里再加回来呢!所以这又需要数学家再做一些工作,把 3.4 × 10 16 这个数减小,让枚举量少一点,再少一点。
        因此,几位数学家利用了 “不可避免集”的概念:如下图所示,如果表示颜色的 4 个数字中任何一个都没有在初始数字中给出,那么这个数独一定没有唯一解——因为在没有给出的情况下这 4 个数字都是由玩家填进去的,玩家既可以以左图的方式填入这 4 个数字,也可以以右图的方式填入,而得到的两个解都是合法的。具有这种属性的数个方格就叫做不可避免集,一旦出现了不可避免集,我们就必须要在其中至少选出一个格子用来填写初始数字。
不可避免集
不可避免集

不可避免集大大化简计算量

        在论文中,数学家们采用了 Ed Russell 总结的一套不可避免集的模板,总共记录了 525 种不同的不可避免集。因为一开始所说的 4 种等价变换对不可避免集也适用,所以他们对不可避免集进行了一些标准化的处理,以保证这 525 种不可避免集互相之间不能通过 4 种等价变换得到。
        此时,枚举算法就被改造成这样:数学家给所有的不可避免集都设定一个状态,分为“被击中”或“未被击中”两种。初始时九宫格 81 个方格内都没有填入数字,所有不可避免集的初始状态均为“未被击中”。之后开始每次选择一个最小的未被击中的不可避免集,枚举其中的每个格子。即每次选择不可避免集中的一个格子填充初始数字,直至试完不可避免集中的所有空格。同时将这个不可避免集标记为“被击中”状态,每次枚举都有 4 种可能。
● 如果这个格子也出现在了其它不可避免集中,那么将这些被涉及到的不可避免集也标记为“被击中”状态;
● 如果枚举了 16 个格子后还有不可避免集未被击中,说明以这 16 个格子为初始状态的数独一定没有唯一解;
● 恰好枚举了 16 个格子后所有的不可避免集全部被击中;
● 如果枚举了不到 16 个格子后所有不可避免集已经全部被击中,则从剩下的所有格子中再枚举几个格子使初始填充了数字的格子达到 16 个。
        完成上面这个工作后,就要用解数独的程序来验证所有枚举的情况是否有唯一解。为了进一步加快枚举速度,数学家们还加入了一些可行性剪枝和最优化剪枝,如提前判断“当前情况下已经不可能击中所有不可避免集”并终止枚举等。
        在这一系列优化之后,算法的复杂度终于降低到了可以接受的范围内。但即使这样,整个计算过程还是耗费了 700 万小时的 CPU 时间。幸而这个算法最终给出了一个确定的结果:所有仅包含 16 个初始数字的数独,都不存在唯一解!

暴力与美学的结合

        当然,上述结果的正确性还有待其他科学家进一步验证,因为算法耗时极高,所以验证过程也需要花费比较长的时间。但无论这次 3 位数学家给出的结论正确与否,随着验算结果的公布,这个问题终将得到一个解答。
        粗略看来,这个算法的实现是非常暴力和机械化的:尝试每一种可能的情况。但是在实现的过程中,数学家们又在借助于数学的力量,不断地试图减少枚举的数量,最终将不可能的事情化为了现实。怪不得西澳大利亚大学的数学家 Gordon Royle 这样评价道:“这个挑战性的问题让人们把计算的能力和数学的技巧发挥到了极限,这就像是在攀登最高耸的山峰。”

2017年2月2日星期四

如何集成 Tomcat 插件到 Eclipse?

  1. 下载 Tomcat
        作者选择的是 Tomcat7,下载地址:http://tomcat.apache.org/download-70.cgi
        2. 安装 Tomcat
        解压缩第 1 步的 apache-tomcat-7.0.75.zip,作者把它解压缩在 E 盘 setup目录下。右键点击我的电脑,选择属性->高级->环境变量->新建系统变量,变量名TOMCAT_HOME,变量值输入 E:\setup\apache-tomcat-7.0.75->确定。
        3. 下载 Tomcat Eclipse 插件
        下载地址 http://www.eclipsetotale.com/tomcatPlugin.html。最新的 releaseNotesV331 可以支持到 Tomcat 7(tomcatPluginV33.zip 可以支持 Eclipse 3.1, 3.2, 3.3, 3.4, 3.5, 3.6 和 Tomcat 4.x, 5.x, 6.x, 7.x。
        4. 安装 Tomcat 插件
        将上一步得到的 tomcatPluginV331.zip 解压缩,将解压缩后得到的 com.sysdeo.eclipse.tomcat_3.3.1 文件拷贝到 eclipse 根目录下的 plugins 目录中。重启 eclipse,工具栏里出现图标Eclipse工具栏Tomcat的图标证明已经安装成功。
        5. Eclipse Tomcat 配置
        eclipse->Window->Preferences->Tomcat,勾选Version 7.x,Tomcat home 选择第二步的安装目录。点击确定按钮。
        6. 部署 JEE 项目到 Tomcat
        右键点击项目名,Properties->Tomcat->确认 Is a Tomcat Project 被勾选后点击 OK 按钮,%Tomcat%/conf/Catalina/localhost 下会有 *.xml 文件生成。

2017年2月1日星期三

Apache与Tomcat之间的区别和联系

Apache 和 Tomcat 都是web网络服务器,两者既有联系又有区别,在进行HTML、PHP、JSP、Perl等开发过程中,需要准确掌握其各自特点,选择最佳的服务器配置。

apache是web服务器(静态解析,如HTML),tomcatjava应用服务器(动态解析,如JSP、PHP)
tomcat只是一个servlet(jsp也翻译成servlet)的容器,可以认为是apache的扩展,但是可以独立于apache运行。
两者从以下几点可以比较的: 
1、两者都是apache组织开发的 
2、两者都有HTTP服务的功能 
3、两者都是开源免费的 

联系
1)Apache是普通服务器,本身只支持html即普通网页,可以通过插件支持php,还可以与Tomcat连通(Apache单向连接Tomcat,就是说通过Apache可以访问Tomcat资源,反之不然)。
2)Apache只支持静态网页,但像asp、jsp、php、cgi等动态网页就需要Tomcat来处理。
3)Apache和Tomcat整合使用:
如果客户端请求的是静态页面,则只需要Apache服务器响应请求;
如果客户端请求动态页面,则是Tomcat服务器响应请求,将解析的JSP等网页代码解析后回传给Apache服务器,再经Apache返回给浏览器端
这是因为jsp是服务器端解释代码的,Tomcat只做动态代码解析,Apache回传解析好的静态代码,Apache+Tomcat这样整合就可以减少Tomcat的服务开销 。 
4)Apache和Tomcat是独立的,在同一台服务器上可以集成。

区别
Apache是有C语言实现的,支持各种特性和模块从而来扩展核心功能;Tomcat是Java编写的,更好的支持Servlet和JSP。
1、Apache是Web服务器,Web服务器传送(serves)页面使浏览器可以浏览,Web服务器专门处理HTTP请求(request),但是应用程序服务器是通过很多协议来为应用程序提供 (serves)商业逻辑(business logic)。

Tomcat是运行在Apache上的应用服务器,应用程序服务器提供的是客户端应用程序可以调用(call)的方法 (methods)。它只是一个servlet(jsp也翻译成servlet)容器,可以认为是Apache的扩展,但是可以独立于apache运行。

2、Apache是普通服务器,本身只支持html静态普通网页。不过可以通过插件支持PHP,还可以与Tomcat连通(单向Apache连接Tomcat,就是说通过Apache可以访问Tomcat资源,反之不然),Tomcat是jsp/servlet容器,同时也支持HTML、JSP、ASP、PHP、CGI等,其中CGI需要一些手动调试,不过很容易的。

3、Apache侧重于http server,Tomcat侧重于servlet引擎,如果以standalone方式运行,功能上
Tomcat与apache等效支持JSP,但对静态网页不太理想。

4、Apache可以运行一年不重启,稳定性非常好,而Tomcat则不见得。

5、 首选web服务器是Apache,但Apache解析不了的jsp、servlet才用tomcat。

6、Apache是很最开始的页面解析服务,tomcat是后研发出来的,从本质上来说tomcat的功能完全可以替代Apache,但Apache毕竟是tomcat的前辈级人物,并且市场上也有不少人还在用Apache,所以Apache还会继续存在,不会被取代,apache不能解析java的东西,但解析html速度快。


两者例子:
apache是一辆车,上面可以装一些东西如html等,但是不能装水,要装水必须要有容器(桶),而这个桶也可以不放在卡车上,那这个桶就是TOMCAT。


两者整合:
Apache是一个web服务器环境程序,启用他可以作为web服务器使用不过只支持静态网页,不支持动态网页,
如asp、jsp、php、cgi。
如果要在Apache环境下运行jsp就需要一个解释器来执行jsp网页,而这个jsp解释器就是Tomcat。
那为什么还要JDK呢?因为jsp需要连接数据库的话就要jdk来提供连接数据库的驱程,所以要运行jsp的web服务器平台就需要APACHE+TOMCAT+JDK

整合的好处:
如果客户端请求的是静态页面,则只需要Apache服务器响应请求。
如果客户端请求动态页面,则是Tomcat服务器响应请求。
因为jsp是服务器端解释代码的,这样整合就可以减少Tomcat的服务开销。

致李显龙总理的一封公开信。

敬爱的李显龙总理,

    本公司(PIABIA)在Blk 824,Jurong west street 81租下了一间HDB超市(mini-mart),本来卖酒名正言顺,结果莫名其妙地受到HDB杯葛,导致一直申请不到酒的牌照。而隔壁Blk 825同样类似的HDB超市则能拥有酒的牌照(License)。
    新加坡被评为经济自由度第2高的国家和地区,酒牌照申请的不平等待遇明显与新加坡的经济自由度不符,也容易滋生政府腐败和权钱交易。
    本来酒牌照的申请是通过police(警察局)处理的,现在还得经过HDB批准。多了一道莫须有的关卡,就难以避免权力的滥用和政府效率的降低。
    不管在中国、美国、日本、德国还是世界各地,超市卖酒都是天经地义的事,既便民又亲民,这也是符合市场经济规律的。总不能在组屋超市里卖奢侈品吧。
    希望李显龙总理能够关注我们小老百姓们的民生,遏制懒政,建立一个“民有、民治和民享”的优秀政府。