因为这两个算法比较简单，又有些相似，所以这里放在一起。

K-最近邻：

k-最近邻也是一种用来进行预测的算法。

工作原理：

接受一个用以进行数值预测的新数据项，然后将它与一组已经赋过值的数据项进行比较。算法会从中找出与待预测数据最为接近的k项，并这k项其求均值以得到最终的结果。

总计来说这是一个很简单的算法，只要我们做好距离的定义并选择一个适合的k值，我们就可以很容易的实现它。

由于我们计算2组数据的距离的通常方法是将他们中对应的每一项目的差值的绝对值(或平方)相加，所以就会出现不同数据范围不同导致的误差。比如每组数据有2个分量，一个取值为0—10,另一个是0—-999999，那么第二的值就会几乎完全决定我们最后的结果。所以我们要对每一组数据进行缩放。

对数据的缩放取决于具体的应用，我们可以通过交叉验证尝试多组缩放因子然后比较它们的优劣。交叉验证的做法是先数据的一部分去除，然后用剩余数据去推测这组数据，我们就可以根据预测的结果对缩放因子进行评估。

优点：

能利用复杂函数进行数值预测，又简单易懂，并且我们可以很容易的在算法中实现查看用哪些近邻进行预测。

缺点：

每次进行预测，它都会使用所有样本，这会导致效率的低下。

寻找缩放因子是一项很乏味的工作.

聚类：

聚类算法可以用于任何具有一个或多个数值属性的数据集合，通过这些数值属性，我们将其所有数据映射到一个n维空间中，并定义该空间中的距离，然后我们可以通过各个数据间的距离对其实现聚类。

分级聚类:

分级聚类的算法是不断找出所有数据中距离最小的两个数据A、B，然后将它们合并成一个新的节点，该节点在n维空间中的坐标是原来两数据点的均值，通过不断进行这一操作，我们最终可以得到一个树形的层级结构。

K-均值聚类:

不同于分级聚类，K-均值聚类的目的是将数据拆成K个不同的群组，其具体算法如下：

1. 在n维空间中随机生成K个中心点
2. 将每个数据项分配给与其距离最近的中心点。
3. 将中心点位置移动到所有分配给它的数据项的中心。如果中心点位置没有改变，则结束算法，否则回到第二步。

具体选择哪种聚类算法取决于要处理的问题，当要将数据拆分到不同的群组时，k均值聚类往往是很有价值的，而如果我们更想了解哪些群组间更为接近，分级聚类更好。当然，我们也可以同时使用２种算法得到更加详细的信息。

      今天上了开学的第一节统计学，开了很久的小差，想了不少东西。

      以前虽然自学过概率论与数理统计，但是也只是了解了一些公式与原理，一直对于统计学的一些应用不甚理解(或者说不能接受)，尤其是基于统计的机器学习，一直不能接受它作为一种实现的人工智能的手段。因为我心中的人工智能是绝对理性，严谨，逻辑的。虽然我可以接受统计学的理论，却不能把它作为一种严谨的逻辑。

　 但是，今天突然想到了感性，是的，人是理性的，但是人的思维中也充满了感性的，当然，这是早已熟知的事实。

　 先给感性下一个定义吧。

　 感性：作用于人的感觉器官而产生的感觉，知觉和表象等直观认识，相对与‘理性’”

　 是的，感性一种直观的认识，那么这种认识从哪里来呢？过去的经验。人们的感性是在经验的基础上建立的，是一种仅仅由经验得出而没有任何逻辑背景的判断。

　 统计学不也是这样么？将大量的样本作为过去的经验，仅仅由这些经验而不带任何逻辑推断的去快速做出一种“感性”的判断。只是这种感性比人的感性更加严谨，不会受到类似“小概率事件经常发生”这种错觉的影响，但也可以算是一种理性的感性了。

      对应的，我又想起了逻辑学，如果统计是根据经验快速简单的做出判断的话，那么逻辑学就是通过严谨的逻辑推理去寻找正确的答案，这个过程会很繁琐，但是它使绝对严谨理性的，比我们的大脑更加严谨，理性——那何不把它看成一种是理性的理性呢？

     但是仅仅有统计与逻辑，我们无法建立一个系统，因此也许还需要一个驱动吧？在完成一个任务、解决一个问题时，这个驱动不断的让感性提供可能解，然后让理性验证它——突然我发现，这不就是“启发式搜索”所作的事情么？

     以前翻过一些人工智能的书，总是觉的虽然那些方法可以达到目的，但是却没有触及到智能的本质，因此总是有些失望的，可是现在，我释然了。什么是智能的本质？好像是在《与众不同的心理学》这本书上，我看到过类似问题(也许问得是别的什么，不过差不多)。书里说，这是不可验证的，如果我们甚至不能解释，验证它，我们为什么可以凭借自己的主观推断去确定一个机器是否拥有智能？我们凭什么可以认为，这些机器，当他们把现在这些技术发挥到一定程度后就不可以拥有智能？也许我们自己的自我认知也只是一种数学的算法对自身产生的作用呢？（是不是有谁说过，这个宇宙，连同我们的存在，都只是一种错觉？记不清了…..不过看来这句话还是很有意思的。）

　 想到了这些之后，我对“人工智能最难的是处理常识”第一次有了很深的认同，以前总是不能充分认识常识的作用，但是如果直觉，经验在智能中占了如此重要的一部分，那么我们就必须去处理常识――其中的困难自然不用多说了。

     最后，把我上课时写在书上的话记录下来吧：

     统计学—以理性研究感性，我们的直觉从过去的经验去推导未来，这种推断不能解释结果的原因。（因为它在历史上倾向于如此，所以它很可能如此。）统计学将这种感性理性化，并出除了一些直觉上的错误（如：小概率事件经常发生），但其根本上还是一种感性的判断，因此解释这种感性推断背后的原因，事物呈现这种状态的原因，就是人的工作了。所以统计学也可以用来在没有线索时，作为一种“事后诸葛亮”式的推断的第一步（即先找出最可能答案，在设法解释它，不过这种方法具有不可证伪性，所以不是科学严谨的――毕竟是直觉么）。同时，统计的机器学习可以就可用来模拟人的直觉学习了（而且是一种没有错误的直觉）。

生物神经网络：

     在生物的神经网络中的基本单位是神经元，神经元与神经元之间是由突触的相互联系来传递信息的，在静止息状态时，神经元的膜的内外电压保持一种稳定状态（膜内电压低于膜外电压），当神经元受到刺激后，在被刺激的部分周围，这种平衡状态会被打破，电压改变，与没有受到刺激的部分形成电流传递信息，电流的强弱取决于受刺激部位电压的改变量。

     前一个神经元的轴突末梢作用于下一个神经元的胞体、树突或轴突等处组成突触。不同的轴突末梢可以释放不同的化学物质对下一个神经元产生不同的影响。也就是说会使下一个神经元的受刺激部分产生不同的电压，也就导致了不同程度的电流，最终也就传递了完全不同的信息。

     一个神经元可以通过轴突作用于成千上万的神经元，也可以通过树突从成千上万的神经元接受信息。当多个神经元同时对一个神经元产生作用时，结果这些神经元的作用强度共同决定。

     神经系统按功能可大致分为传入神经（感觉神经）、中间神经（脑：延脑、脑桥、小脑、中脑、间脑、大脑脊髓）与传出神经（运动神经）三类。

     感受神经的作用是接受外界信息（输入），中间神经则起到了信息传递与计算分析的作用，最用，传出神经会负责对外界信息作出相应的反应（输出）。

     模仿这一过程，我们就可以建立人工神经网络。

人工神经网络：

     人工神经网络的基本单位是人工神经元（以下简称神经元）。一个神经元可以有多个输入，每个输入有一个相应权值。

图示如下：

a1~an为神经元的输入值
w1~wn为神经元各个的输入所拥有的权值
b为偏移量
sum对各个输入与其权值的积求和(含偏移量)。
f为传递函数，接受sum的输出，通过一个函数变换，输出t
t为神经元输出
数学表示 t=f(WA'+b)
W为权向量
A为输入向量，A'为A向量的转置
b为偏移量
f为传递函数

在人工神经网络中，神经元之间相互连接，在连接点将前者的输出作为后者的输出，形成错综复杂的网状结构，进行信息的传递与计算。

我们这里要介绍的是其中比较简单的一种模型，称为“多层感知机（MLP）”网络。

为了简化模型，我们假设偏移量b=0.

多层感知机网络由3部分组成：

输入层：功能类似感受神经，每个节点接受外界的直接输入。这里的模型中，每个节点接受单一输入，权值为1。

输出层：功能类似运动神经，该层输出就是神经网络的输出。

隐藏层：是输入层和输出层之间的多层神经网络，可以有1或多层。

因此，MLP网络中至少有3个层次。

这些层次中，每层的每个神经元的输出都会作为下一层的每个神经元的输入，因此当我们对输入层进行输入后，该信息会一层层传递下去，最终从输出层输出。

神经网络建立后，我们需要设法确定每个神经元的各个输入的权重w，并选择合适的函数f对输入进行变换，只有完成以上工作后，我们才能使用神经网络完成相应的工作。

我们一般会选择过关于源点对称的S形函数作为函数f，该种函数特点是:输入接近0时，函数对输入的变化有敏感的反应，这一敏感度将随输入绝对值的增大而下降，最终趋于0。

权重的获取：

选择合适的函数后，我们就要去确定各权重w了，权重的选择取决于我们想要神经网络完成的任务，我们首先会给每个输入一个初始化的默认值，该值可任意选取。

完成初始化后，我们就要开始训练神经网络了，即给神经网络大量的已知的正确的输入及其对应的输出，神经网络会将自己得到到的输出与正确输出向比较，然后根据某一算法调整自身的权重，使自身输出更接近正确答案。

我们这里要介绍的调整算法称为反向传播法，因为该算法是沿网络反向调整权值的。

这一算法中，我们会分析输出与正确答案，并将将输出向正确答案推进，为了了解如何推进，我们需要一个函数来计算函数f的斜率，设该函数为g。根据该函数，我们可以计算sum因改变的值。

整个算法如下：

从后向前对输出层和所有隐含层：

1）  计算节点当前输出与期望结果的差值d。(期望结果t – 实际输出 y)

对输出层: t在输入训练数据时一同输入。

对隐含层: t = sum ( 前一层的每个节点的差值di * 这两个节点间连线的权值 )

2）  利用函数g确定函数f在节点输出值y处的改变速率v。v=g(y)

3）  改变每个输入链接的权值，其改变量与链接的当前输入强度与学习速率rate（自己定义的属于(0,1)的常量）成正比。

（每个wi的改变量为（vdrate*输入ai））

这样一层层的从后向前反推，最终完成对一个训练样本的学习。

当对所有样本完成训练后，我们就可以使用这个神经网络了。

比如，我们想用神经网络模拟一个数学函数，我们先向网络提供大量的正确的输入输出进行训练，然后就可以用神经网络作模拟这个函数进行计算了。

优点：

数学基础：

树：树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；

每一个子结点只有一个父结点；

没有前驱的结点为根结点；

除了根结点外，每个子结点可以分为m个不相交的子树；

没有子节点的节点称为叶节点。

决策树分类器原理：

决策树是一颗树，要分类的样本从树根进入，在树的每个节点通过对样本的某种属性的判断选择不同的路径逐步下降到底,得出其所属类别。

例图:

为了建立一棵决策树,我们首先应向程序输入大量训练数据(包含所属类别的数据)，程序将根据训练数据按某一算法自动生成决策树。

决策树生成算法:

   为了构造决策树，算法首先创建一个根节点，然后通过分析训练数据，逐步选出适合的变量对数据进行拆分(即逐步构造上图中的非叶子节点。)

   为了选择适合的变量对数据进行拆分，我们需要一个方法来评估一种拆分方案的好坏，其评估方法包括：

2. 基尼不纯度：

定义：基尼不存度是指来自集合的某种结果随机应用于集合中某一数据的预期误差。（如果集合中所有结果属于同一类，则误差为0）

使用：利用这一思想，我们可以将集合中每种类别的数据出现的次数除以数据总数计算相应概率，再将这些概率的乘积相加（所有概率两两相乘后在相加），这样就会得到某一数据被随机分配到错误结果的总概率。

伪代码：

imp=0
for k1 in kinds
    p1=count(k1) / total
    for k2 in counts
        if (k1==k2)continue
        p2=count(k2) / total
        imp+=p1*p2
ans=imp

   (p1*p2是一个p1类别的数据被当作p2的概率)

2. **熵：**在信息论中，熵代表的是集合的无序程度—–基本上就相当于我们在此处所说的集合的混杂程度。

熵的值是遍历所有结果后得到的pi*log2(pi)的和的绝对值

伪代码：

ent=0.0
for k in kinds
    p=count(k) / total
    ent=ent – p*log2(p)     // 因为0<p<=1，所以必有log2(p)<=0
ans=ent

有了上述评估方法后，我们就可以不断尝试各种拆分方法，然后选出最好的拆分方法构造树中的节点了。我们将计算拆分前的熵（基尼不存度）值，与拆分后的熵（基尼不存度）的值的加权平均，将其差值作为信息增益。最终对能得到最大信息增益的属性进行拆分。然后再分别对拆分后得集合选择属性进行拆分，直到最大信息增益为非正时停止拆分，这时决策树就构建完毕了。

优化：

为了防止决策树变的过度拟合（过度针对训练数据），我们可以在信息增益小于某个值后就停止拆分。但是我们可能遇到这样的数据―――某次拆分信息增益很小，但下一次就会很大。为了防止这一状况，我们可以在用先前的方法构造整棵树后，在尝试消除多余的节点。这个过程就是剪枝。

剪枝的过程就是对具有相同父节点的节点进行检查，判断将其合并后，信息增益是否会小于某个指定发值。若是，则合并这些节点。合并后节点包括所有可能的结果值。

在处理数值型数据时，熵和基尼不存度并不是一个好的选择，因为有些数值相差很近，有些相差很远，不能简单用是否为同一类别进行判断。所以我们可以用方差代替它们。

决策树对缺失数据的处理：

当我们要判断类别的样本缺少某些决策树作判断时必须的数据时，我们可以选择同时走两个分支，不过我们不是平均统计各分支的结果值，而是进行加权统计。为了达到这一目标，决策树中每个节点都有一个值为１的权重，即观测数据对于数据向是否属于某个特定分类的概率具有１００％的影响，而如果走多个分支，我们将给每个分支一个权重，其值等于所有位于该分支的其他数据所占的比重。

优点：

决策树最大的优势是它可以轻易对一个受训模型给予解释。（解释分类原理）

决策树可以同时接受分类型和数值型数据。

比起贝叶斯分类器（参考**[<集体智慧编程>算法总结1—贝叶斯分类器][2]**）决策树可以更好的处理变量间的相互影响。

 这几天以很快的速度翻完了<集体智慧编程>,因为只是对里面的算法感兴趣,对那些web2.0的应用没什么感觉,所以很多地方都是一扫而过,现在按最后一章的顺序来对所有相关的算法作一个详细的复习….

这个是第一篇……贝叶斯分类器

数学基础：

条件概率

定义：设A, B是两个事件，且P(A)>0 称P(B∣A)=P(AB)/P(A)为在条件 A下发生的条件事件B发生的条件概率。

乘法公式

设P(A)>0，则有P(AB)=P(B∣A)P(A)

全概率公式和贝叶斯公式

定义: 设S为试验E的样本空间，B1, B2, …Bn为E的一组事件，若BiBj=Ф, i≠j, i, j=1, 2, …,n; B1∪B2∪…∪Bn=S则称B1, B2, …, Bn为样本空间的一个划分。

定理

设试验E的样本空间为，A为E的事件，B1, B2, …,Bn为的一个划分，且P(Bi)>0(i=1, 2, …n)，则P(A)=P(A∣B1)P(B1)+P(A∣B2)+ …+P(A∣Bn)P(Bn)称为全概率公式。

定理

设试验E的样本空间为S，A为E的事件，B1, B2, …,Bn为的一个划分，则P(Bi∣A)=P(A∣Bi)P(Bi)/∑P(B｜Aj)P(Aj)=P(B｜Ai)P(Ai)/P(B)称为贝叶斯公式。

说明：i，j均为下标，求和均是1到n

贝叶斯分类器原理：

通过某些特征对不同的内容进行分类。

特征的定义

任何可以用来判断内容中具备或缺失的东西。如要对文档进行分类时，所谓的内容就是文档，特征就是文档中的单词(当然你也可以选择其他合理的东西)

当向贝叶斯分类器输入一个要进行分类的样本后，分类器会先对该样本进行分析，确定其特征，然后将根据这些特征时，计算样本属于各分类的概率。

朴素贝叶斯分类器的具体工作步骤：

1. 学习：向分类器输入一系列的训练数据，注意这些数据是包括其所属类别的，分类器将对训练数据进行分析，计算出

1.各个特征在各个分类中出现的概率(=某分类中具有该特征的数据数目/该分类数目)如先计算出各个单词在各种分类的文档出现的概率。

将该概率作为某分类下某特征出现的条件概率P(feature|category)

2.任选一个样本属于某分类的概率(=某分类文章数 / 文章总数)

记该概率为p(category)

在朴素的贝叶斯分类器中，我们假设将要组合的各个概率相互独立(当然，很多时候并非如此。我们有时会发现，当样本拥有某一特征时，则它就更可能拥有另一项特征。)

2)分类计算：在向分类器提供大量学习数据后，我们就可以用它对新的样本进行分类了。

首先对样本进行分析，找出其具有的各种特征，利用这些特征，我们来计算各个分类中出现该样本的概率p(sample | category)。为了完成这一计算，我们只要简单将该分类下在该文档中出现过的特征出现的条件概率相乘即可。即∏P(feature | category) 这里的feature是该样本拥有的所有特征。

但是，我们实际要计算的是P (category | sample),即给定样本属于某分类的条件概率。

这里，就用到了贝叶斯定理：P(A | B)=P(B | A)P(A) / P(B)

这里就是：P(category | sample)= P(sample | category)P(category) / P(sample)

军训期间闲着无聊时,决定读一些“杂书”，其中有一本叫《你的灯亮着么?》的小册子，刚读完不久，趁着今晚休息的时间作以记录。

1)动手解决问题前，好好想想问题的来源。2)如何从各个角度看待问题，找到其真正所在。3)为什么不要把人们的解决方法误以为是问题的定义，更不要把某个问题的解决方法误认为是问题的定义，特别是整个解决方法是你自己所使用的。4)永远不要肯定你已经有了一个正确的定义，即使是在问题好像已经解决之后。5)每一种解决方法都会带来新的问题。6)问题最难处理的部分恰恰是去意识到它们的存在。7)在理解问题前，至少要做好准别接受三种可能的出错情况。8)或许还可以改变问题的表述来获得不同的解决方法。9)当你沉迷于寻找问题的定义和解决方法时，不要忘记随时都回头看看，看看自己是不是已经迷路了…。10)当别人能很好的解决自己的问题时，千万不要越俎代庖。11)如果某人能够解决这个问题，但是他们并不会遇到这一问题时，那么你首先要做的就是让他们也感受一下问题。12)不管看上去如何，人们很少知道他们要什么，直到你给了他们所需要东西。13)甚至，事实上，并没有多少人真的希望他们的问题被解决。

以上摘自书中序言。

解决问题前，我们自然要先明确问题，比如问题的对象，问题的内容等等，虽然问题本身并不会有一个通俗简单的定义。但是书中的一种说法确实让人耳目一新—-“问题就是你所期望的东西和你体验的东西之间的差别”。对问题的定义是非常重要的―――同样是具有风险的，很多人在问题的定义中徘徊，因为他们不愿承担定义失误的风险。

作为一个问题的解决者，为了定义一个问题（当然，它并不唯一），我们可以利用经典的分治算法把一个问题变为一系列的问题。为了实现这一转变，我们需要去回答另外一些问题—比如“谁有问题”“问题的本质是什么”“问题是谁引起的”等等。

当我们做出了一个比较适合的定义后，我们就可以着手去解决它。由于“问题就是你所期望的东西和你体验的东西之间的差别”，我们可以从两个方面入手—-要么改变期望，要么改变体验。

要改变体验，有很多种方法，书中举例说“很多人觉得等待电梯的时间太久”―――“那么我们的期望的就是更加快速有效的乘坐电梯，体验则是漫长的等待”，而解决方法是―――“在等待电梯的拐角放上一面镜子”――――“对着镜子整理衣着减少了人们体验到的时间”。

你从例子中体验到了什么?我悟到的是“体验!=(不等于)现实”，我们可以在不对现实做出任何改变的同时，用某种手段改变人们的体验。

但是在解决这一问题后是什么呢?—-新的问题—有人在镜子上乱涂乱画！我们的问题解决者不得不继续想办法去解决它。

如果你想找到一个问题的解决方法，试试“让情况变得更糟”。基于这个原则，问题解决者把在镜子上涂画变成了一种娱乐的活动—效果是一样的，人们不会觉得电梯来得太慢了—他们甚至觉得来得太快了，不是么？

在结束这一章时，书中继续了那个很有趣的电梯的故事—“在他们讨论解决问题时，曾经用说笑的口气提出过偷取隔壁大楼电梯使用时间的方法，但是被否决了。后来问题解决者发现隔壁大楼是一座百货商场，而且商场最近生意还不怎么样—他们巴不得有人去偷取他们的电梯时间呢！”文中的结论是“对那些没有幽默感的人，帮他们解决问题简直就是自寻烦恼”（因为他对这个说笑口气提出的解决方案给予了严肃的批评），我觉得，这告诉我们，很多方案，我们并不能只从印象和表面去判断他是否可行—-因为那并不可靠。

然后是一个新的故事—-在这里不对那个故事进行复述了，我觉得这个故事中最重要的结论是“不要把他们的解决方法误认为是问题的定义”即是说，我们要自己去了解问题，而不要从别人那里—尤其是他们的解决方案那里得到问题的答案。很多时候我们试图从别人那里去得到问题的定义，但是那永远是局部的，这和我们在做题做不出时，会去重读题目一样—最原始的资料，虽然最难以使用，但却又是最为有效的。

另外一个结论是：如果你太轻易地解决了他们的问题，他们永远都不会相信你真的解决了他们的问题。

人总是过于自信的，这使他们不愿承认自己错误的估计了一个问题的难度。这使得我们有时为了解决一个问题，会浪费比解决问题更多的时间去说服哪些人—–为了避免这一点，我们必须在适当的时候承认自己的愚昧和无知。当然，倒过来想，绝大多数问题可以是简单的，只是我们用错了方法，走错了方向。仅此而已。

在下一个故事中，再次强调了以下的事实：

每一种解决问题的方法都会到来新的问题。我们永远都不能消灭问题。问题、解决问题的方法和新的问题编织成一条无穷无尽的锁链。在解决一个问题的时候，要找出至少三个可能出现的新问题，否则说明我们对于当前问题的理解还不够透彻。

另外：问题最难以处理的部分恰恰是去意识到它们的存在。如果我们能够意识到问题的存在，那么很多问题是很容易解决的。一个典型的例子是交通限速与交通事故的关系。当能源危机使美国限速减低到55英里时，交通事故大量减少。但是在这以前呢？我们常把原因归因与酒后驾车等问题,根本没有人意识到他们习以为常的交通限速根本就不合理！这是因为我们思维中的惯性的存在。因此，换一个身份进行思考，（孩子，外国人等等）也许你会对问题有一个全新的解读。因为很多我们习以为常的东西其实并不合理，或者说并不完美。

这也就代入了“问题的表述”的问题，不同的问题表述可以给我们不同的解决方案，同样会带来不同的新的问题。

 只要我们记得对自己提问：“我们要怎样改变问题的表述才能获得不同的解决方法？”也许我们就能得到不同表述与答案。

一个简单的例子是一个简单的圆。我们可以问“这个物体是什么?”，也可以问“这个常见的物体什么?”“这个不常见的物体是什么?”你的答案一定会大不一样吧。

这里我又想到了一个加鸡蛋的故事：“您要加鸡蛋么？”“您要加一个还是两个鸡蛋？”这样提问的两家商店可以有着完全不同的营业额。

提问的内容与方法确实可以制约到人的思维，进而控制了我们的答案。

这其实是一种文字游戏。

有时我们可以利用它，有时我们却要减少文字引起的不确定性，因此，一旦你用文字来表述一个问题，请仔细推敲这些文字以使这种表述在每个人的头脑中都是一个意思。

    另外，由于问题中存在的种种陷阱**：**当你在寻找问题定义的道路上疲倦地游荡时，不要忘记随时都回头看看，看看你是不是已经迷路了。

又是新的故事。

如果一些人产生了问题，你最好不要随便的插干涉它—“当别人能够很好地解决自己问题的时候，千万不要越俎代庖。”因为外力的入侵或许会使问题产生一些我们事先没有想到的变化—-比如引入新的变量，改变问题的性质等等。

如果这是他们的麻烦，就让它成为他们的麻烦吧。

    但是当你无法解决你所解决的问题而需要寻求帮助时，你也许会发现有人可以轻易的解决它。你要如何寻找帮助呢?威逼和利诱都不是最好的选择—-你只需要让他也感受到这一问题的存在。（当然，这不是永远有效的，因为也许那个人根本就不在乎，或者他会认为你是在给他捣乱！）

如果你用尽方法都行不通的话，为什么不试试指责你自己呢？人们倾向于在别人身上寻找问题，确不会降低自己的期望。还记得我们对问题的定义么“问题其实就是你期望的东西和你体验的东西之间的差别”除了改变体验外，降低期望同样是一种方法—-虽然你并不喜欢。但是事实是，很多问题的根源在你自己身上。

不得不提的是书中最经典的一个例子:在一个隧道的入口处有一个照牌“警告：前有隧道请打开车头灯”，那么隧道的出口呢？“请关灯？”如果是晚上呢？也许我们可以用非常麻烦的语法分析各种情况写出一个完美的招牌，但是谁会去读它？最简单的方法是“如果这是他的问题，把问题留给他好了”—简单的在牌子上写上“你的灯亮这么?”—我们没有必要为所有人解决一个对每个人都很简单，组合起来确又非常复杂的问题，不是么？

最后，书中讨论了一个很奇怪的问题“我们真的想解决问题么？”虽然很奇怪，但是这种情况确实经常出现。也许你只是在享受问题解决过程的乐趣，也许你解决问题是为了否定它,谁知道呢?

最后的最后，是书中的最后说明的一句话：

   ****“首先，对自己要真诚。”

   “This above all， to thine own self be true**。”**

    在解决和定义一个问题前：“道德是最为重要的”

    虽然文章已经结束了，我还是想把书中一个很有趣的问题及解决与大家分享，这来自书的序篇。

序篇

问题：没有人会阅读序言

解决方法：把序言称为第一章

解决方法带来的新问题：第一章是单调沉闷的

再次解决：把第一章扔了，再把第二章称为第一章

ACM的暑假集训结束了，趁着军训还没开始，对整个暑假接触到的东西作了一个总结，因为刚参加ACM不久，所以内容大都比较基础吧，文章中提到了些参考资料，如果需要的话，请留下邮箱。

目录
1)数据结构
 1.并查集
 2.高精度数
 3.线段树
 4.字典树<未完成>
2)常用算法
 1.递推
 2.动态规划
 3.贪心
 4.搜索
3)图论部分  1.2-SAT问题
 2.差分约束系统
 3.二分图
 4.最短路(SPFA,Dijkstra)
 5.欧拉回路<未完成>
 6.最优比率生成树
 7.关键路径
 8.网络流(流的算法/应用)
  最大流算法(3种)
  最小费用最大流算法
  图的连通性（最小点割集）<未完成>
  混合欧拉回路
 9.其他图论相关问题算法:
  K短路
  图的单向连通（包括2次DFS缩点）
4)其他
 1.计算几何
 2.数学(数论,组合数学,数值计算)
5)附录
 1.A*算法
 2.位运算之格雷码：
 3.线性同余方程

一．数据结构：

1.并查集.

用于实现合并与查找两种操作的数据结构.
实现方法:线形数组,有根树.
优化:
把深度小的树合并到深度大的树,深度相等时任选一棵树,既max(h1,h2), if h1<>h2. / h1+1, if h1=h2.
合并操作时的路径压缩.
并查集的偏移向量:
并查集的偏移向量属于并查集的变形，只要适用于集合数目较少，或是固定的并查集类型。
增加一个offset字段,表示元素相对根的偏移量.

在find函数中计算偏移量
int findset ( int x )
{
    int t ;
    if ( father [ x ] == x ) return x ;
    else t = findset( father [ x ] ) ;
    offset [ x ] = ( offset [ x ] + offset [ father [ x ] ] ) % DEPTH ;//DEPTH表示几个状态量
    //如果1182中，DEPTH=3；
    father [ x ] = t ;
    return t ; 
}//使用函数递归调用查找父亲在处理上优于循环。
union函数中计算偏移量
void union(int x,int y,int d){
    int fx , fy ;
    fx = find ( x ) ;
    fy = find ( y ) ;
    if ( fx == fy ) return ;
    father [ fx ] = fy ;
    offset [ fx ] = (offset [ y ] - offset[x]+d+3)% 3 ;
} 

2.高精度数

大数的加减乘除
小数的高精度计算参考pku1001