N-Queens problem is defined as: place n queens on an \(n × n\) chess board so that the queens do not attack each other. Now, we rotate the board clockwisely by 45 degrees as shown in following picture, and use a variable to denote the queen partition (if any) for each …
read moreThere are comments.
Sudoku is a puzzle that requires players to complete a partially filled 9 × 9 grid with digits 1 to 9 such that each row, each column and each of the nine 3 × 3 boxes (shown in Figure 1 in thick border lines) contain different digits.
The Gecode implementation has hardcoded …
read moreThere are comments.
Hadoop是Apache开源基金会下的一个项目，针对处理大数据的特性设计的分布式编程模型工具。Hadoop的核心思想来源于Google的MapReduce和Google File System（GFS）。通俗来讲，就是将处理的问题分为两个子问题，一个负责将问题分割成一个一个小的部分，另一个负责将前一个步骤的每一部分都合并在一起。
最常见的例子就是单词统计。假设我们需要统计一个文档里的单词，最简单的方式就是用一个dictionary或者map来存储一个key-value对。一旦发现一个新的单词，我们就在这个dictionary里面添加一个条目，value设为1。如果这个单词已经存在，那么取出这个key对应的value，将其加1。这种方式对于一个小的文档来说固然合适，但如果我们处理的是一个TB，PB级别的数据呢？如果我们想在1秒钟之内就处理完这些数据？这就需要用到分布式处理了，也就是多台机器同时运算。对于数单词这样一个简单的工作，要解决的就是如何分配任务，每一台机器需要处理文档的哪个部分，以及如何将这些结果整合在一起。有了这样的思想，我们可以给这两个部分的工作分配给两个模块，一个是mapper，一个是reducer。mapper负责把问题分割成很小的一部分，每一部分都会产生一个问题的输出；reducer负责把所有若干个mapper产生的输出汇总，再计算出所需的输出。由于这种模型涉及到的数据量都比较大，而建立在大数据上的数据处理一般来说都相对比较简单，因此将这种模型一般化，使用户只需要关注mapper和reducer的具体实现，而不用考虑异常处理，问题分割等等细节问题，这就是Hadoop需要解决的问题。
但是，并不是所有问题都适合用MapReduce模型解决，比如说PageRank。当问题涉及到图结构的时候，一个很普遍的现象就是活跃节点和不活跃节点差异非常明显 …
read moreThere are comments.
作为对学了一个学期的内容的总结，在这里稍微介绍一下Constraint Satisfaction Problem（CSP）吧。这个题目我也不知道中文叫做什么，也许叫做有约束问题解决模型比较合适。虽然我没有学过数学建模，但或许他们之间是比较类似的，CSP的中心思想就是针对一个特定的问题建立模型，然后解决它。解决问题的具体实现就叫做Constraint Solver（约束处理机）。我认为这个方法还是很实际的，它可以帮助我们快速建立起对一个问题的数学角度的认识，同时在编程方面也有很多的函数库，比如说IBM的CPLEX。这里只介绍Gecode的使用，当然官方文档对于Gecode已经解释的很详细了，我在这里只想梳理一下整个建立模型的步骤和稍微介绍一下Gecode。
Gecode是一个用于解决约束问题的基于C++的函数库，覆盖了Windows，Linux，Mac三个平台。在2012年以前长期霸占着MiniZinc比赛的头名，就现在来说当然性能也不差，而且也一直有更新。关键的是，相比起CPLEX，它是免费开源的。官方主页：Gecode。
在CSP概念里，问题被表示成几个部分：变量（Variable），值域（Domain），约束（Constraint）。变量是问题模型中所有可以改变的量，可以是一组数，也可以是未知的属性，比如说香港的某一所高校 …
read moreThere are comments.