ab剪枝算法

龙源期刊网

ID3分类及其剪枝算法研究

作者：刘冲 杨磊 李娜

来源：《软件导刊》2016年第12期

摘 要：分类是数据挖掘的一个重要课题。分类的目的是建立一个分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个利用该模型形成分类规则并预测未来数据趋势[1]。决策树归纳是经典的分类算法，构建决策树模型算法中最有影响力的方法是ID3算法。针对ID3算法缺点，使用预剪枝和后剪枝相结合的办法处理决策树中的过学习情况，可生成一个更简单、更精确的决策树。

关键词：ID3分类算法； 决策树； 剪枝算法

DOIDOI：10.11907/rjdk.162536

中图分类号：TP312

文献标识码：A文章编号：1672-7800（2016）012-0033-02

1 ID3分类算法

1.1 ID3算法原理

决策树归纳是经典的分类算法[1]。ID3算法是Quinlan提出的一个著名的决策树生成方法。决策树是指具有以下性质的树：每个内部节点都被标记一个属性，每个弧都被标记一个值，这个值对应于相应父节点属性；每个叶节点都被标记一个类[2]。ID3算法是一种基于信息熵的决策树算法，算法的核心是在生成决策树时使用信息增益作为训练样本集合的分裂度量标准，选择信息增益最大值的属性对训练样本划分，该属性使得划分样本分类所需的信息量最小。该方法可以减少训练样本的划分次数，并尽可能得到一棵简单的决策树来描述相关信息。

1.2 ID3算法缺点

（1）对噪声较为敏感，训练数据的轻微错误会导致不同结果，鲁棒性较差；算法结果随训练集记录个数的改变而不同，不便于渐行渐进学习。

（2）ID3算法只能处理离散属性的数据，对于连续属性数据，必须先进行离散化处理才能使用。如产品名称是一个离散性属性，适合用ID3算法处理，而产品价格是连续性属性，必须对产品价格进行离散化处理后才能使用。

极小极大搜索过程

2011-03-30 09:59

转载自 shengtingjiaju

最终编辑 shengtingjiaju

极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的α-β剪枝搜索方法，就是从这一方法发展而来的。

首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。

想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应......这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。

极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。

在图3.5所示的例子中，假定搜索深度为2，D～J是7个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C是三个极小节点，它们分别取各自子节点最小值为自己的值，得到三个节点的值分别为-6、-2和-4。s是极大节点，从A、B、C三个节点的值中取最大值，得到-2。由于-2来自于节点B，所以搜索的结果是应选择B作为我方的走步。对于我方来说，-2并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择A为我方的走步，如果对方回应D的话，我方可以得到评价值9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择E，而不是D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。

第２８卷第２期　２０１１年２月　计算机应用与软件　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖｏ１．２８　Ｎｏ．２　Ｆｅｂ．２０ｌｌ　

基于剪枝的最小生成树算法在供水管网的应用　毛　华　谢利伟　张智星　（河北大学数学与计算机学院河北保定０７１００２）　（河北省数学研究中心河北石家庄０５００１６）　（河北省机器学习与计算智能重点实验室河北保定０７１００２）　摘要　在进行供水管网网络设计时，如何使铺设的供水管网线路最短，构建的供水管网造价最低是设计者需要重点考虑的问题　之一。文章就此问题提出了一种基于剪枝的最小生成树算法。算法首先将交叉点（街道的交汇处）和节点（用户）都视为图的顶点，　然后求出最小生成树，最后再将最小生成树中以交叉点为末梢的“枝叶”剪掉。该算法简洁、快速、易于实现。对铺设公路，架设网　线等一类网络问题也有实际的参考意义。　关键词　供水管网　交叉点　节点　度　ＡＰＰＬＹＩＮＧ　ＰＲＵＮＩＮＧ．ＢＡＳＥＤ　ＭＩＮＩＭＵＭ　ＳＰＡＮＮＩＮＧ　ＴＲＥＥ　ＡＬＧｏＲＩＴＨＭ　ＩＮ　ＷＡＴＥＲ　ＳＵＰＰＬＹ　ＮＥＴＷｏＲＫＳ　Ｍａｏ　Ｈｕａ　Ｘｉｅ　Ｌｉｗｅｉ　Ｚｈａｎｇ　Ｚｈｉｘｉｎｇ　（Ｃｏｌｌｅｇｅ　ｏｆＭａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｈｅｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ　０７１００２，Ｈｅｂｅｉ，Ｃｈｉｎａ）　（Ｍａｔｈｅｍａｔｉｃｓ　Ｒｅｓｅａｒｃｈ　Ｃｅｎｔｅｒ　ｏｆ　Ｈｅｂｅｉ　Ｐｒｏｖｉｎｃｅ，Ｓｈｉｊｉａｚｈｕａｎｇ　０５００１６，Ｈｅｂｅｉ，Ｃｈｉｎａ）　（Ｋｅｙ　Ｌａｂ　ｉｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　ａｎｄ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　ｏｆＨｅｂｅｉ　Ｐｒｏｖｉｎｃｅ，Ｂａｏｄｉｎｇ　０７１００２，Ｈｅｂｅｉ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｗｈｅｎ　ｄｅｓｉｇｎｉｎｇ　ｗａｔｅｒ　ｓｕｐｐｌｙ　ｎｅｔｗｏｒｋｓ，ｉｔ　ｉｓ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｔｏ　ｂｅ　ｅｍｐｈａｔｉｃａｌｌｙ　ｃｏｎｓｉｄｅｒｅｄ　ｂｙ　ｔｈｅ　ｄｅｓｉｇｎｅｒ　ｔｈａｔ　ｈｏｗ　ｔｏ　ｐａｖｅ　ｓｈｏｒｔｅｓｔ　ｌｉｎｅｓ　ｏｆ　ｗａｔｅｒ　ｓｕｐｐｌｙ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ｌｏｗｅｓｔ　ｃｏｓｔ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｐｒｕｎｉｎｇ—ｂａｓｅｄ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｉｓ　ｐｒｏｂｌｅｍ．Ｉｎ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｃｒｏｓｓ—ｐｏｉｎｔｓ（ｒｏａｄ　ｉｎｔｅｒｓｅｃｔｉｏｎｓ）ａｎｄ　ｎｏｄｅｓ（ｕｓｅｒｓ）ａｒｅ　ｐｏｉｎｔｅｄ　ｏｕｔ　ａｓ　ｖｅｒｔｉｃｅｓ　ｏｆ　ａ　ｇｒａｐｈ，ａｎｄ　ｔｈｅｎ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｏｆ　ｔｈｉｓ　ｇｒａｐｈ　ｉｓ　ｔｏ　ｂｅ　ｓｏｌｖｅｄ．Ｔｈｅ　ｆｉｎａｌ　ｓｔｅｐ　ｉｓ　ｔｏ　ｐｒｕｎｅ　ｔｈｅ　ｔｏｐ　ｖｅｒｔｉｃｅｓ　ｗｈｉｃｈ　ａｒｅ　ａｌｓｏ　ｔｈｅ　ＣＲＯＳＳ－ｐｏｉｎｔｓ　ｉｎ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ．Ｔｈｉｓ　ａｌｇｏ－　ｒｉｔｈｍ　ｉｓ　ｓｉｍｐｌｅ　ａｎｄ　ｆａｓｔ，ｅａｓｙ　ｔｏ　ｂｅ　ｒｅａｌｉｚｅｄ．　Ｉｔ　ａｌｓｏ　ｈａｓ　ｐｒａｃｔｉｃａｌ　ｓｉｇｎｉｆｉｃａｎｃｅ　ｔｏ　ｏｔｈｅｒ　ｓｉｍｉｌａｒ　ｎｅｔｗｏｒｋｓ　ｓｕｃｈ　ａｓ　ｐａｖｉｎｇ　ｒｏａｄｓ　ａｎｄ　ｓｅｔｔｉｎｇ　ｕｐ　ｃａ－　ｂｌｅｓ　Ｋｅｙｗｏｒｄｓ　Ｗａｔｅｒ　ｓｕｐｐｌｙ　ｎｅｔｗｏｒｋ　Ｃｒｏｓｓ—ｐｏｉｎｔ　Ｎｏｄｅ　Ｄｅｇｒｅｅ　０引　言　供水管网是城市的基础设施之一，建立健全一套完整有效　的供水管网系统，是保证城市供水的必要措施和基本条件…。　对供水管网系统进行科学的规划、设计和运行管理，不仅可以　为国家节约大量的资金投入，还可以提高水资源的利用率，提　高整个供水系统的运行可靠性，减少维修量　。供水管网优化　系统是一个复杂的系统，系统中任何一部分的改进与完善都有　利于整体优化效果的提高　。供水管网系统完整的优化过程　包括规划、设计、运行管理三个阶段　Ｊ。其中，供水管网优化设　计是优化过程的主要内容，优化设计的效果将直接影响供水管　网的运行及管理方式。国内外许多学者在管网优化设计方面开　展了研究，主要方法有非线性规划法　、线性规划法　以及人　工神经网络法　等。但是，以上方法主要研究的是如何确定　管网流量分配和选择各级管道尺寸、水塔高度和水泵扬程等优　化设计问题，且以理论研究为主，而对实际的一些具体问题如管　网如何铺设研究较少。因为管网的铺设涉及到资金的投入，故　是一个不能忽略的问题。本文着重从管网在城市内如何铺设考　虑，为管网优化方法的进一步发展提供参考。　在城市管网铺设时，由于管道只能沿着街道铺设，所以街道　的交汇处就必须加以考虑。如何处理和选择这些交汇处使得供　水管网连接所有的用户并保证其造价最低是管网铺设中重要而　又较难解决的问题。本文就此问题提出了一种基于剪枝的最小　生成树算法，在最后举例加以说明。　１供水管网优化设计模型　由图论知识　知，每个管网可视为一个图。本文首先将管　网的内容转化为图论语言，以达到实现用数学的方法解决管网　设计的目的。由管网到图的语言描述如下：　ａ）将规划区域内的供水中心和用户称作节点，街道的交汇　处称作交叉点，将节点和交叉点都视为图的顶点。　ｂ）将各个节点和交叉点间可能铺设的路径视为图的边。　ｅ）将各条线路的建设费用和运行费用之和视为边的权。　收稿日期：２００９—１０—１１。河北省自然科学基金数学专项基金（０８　ＭＯＯ５）。毛华，副教授，主研领域：代数组合数学及其应用研究。

Minimax极⼤极⼩算法、Alpha-BetaPruning剪枝算法

这篇博客分为两部分。⾸先我会先讲极⼤极⼩算法，然后在此基础上进⾏改进给出进

阶版的Alpha-Beta剪枝算法以及代码实现。⽂中配备b站讲解的视频，感兴趣的可以看

⼀下视频讲解，然后复习的时候拿着⽂章当作参考。

Minimax算法（极⼤极⼩算法）概念

是⼀种找出最⼩失败的可能的算法。意思就是两个⼈下棋，A和B下棋，A想要⾃⼰的利益最⼤化（失败的可能性最⼩），B想要A的利

益最⼩化（B想要A输）。这个算法以及接下来的Alpha-Beta剪枝都是⼀种对抗性搜索算法（两个⼈互相对抗着下棋，俩⼈都想赢），

是⼀种⼈⼯智能搜索的算法。掌握此算法后可以⽤来写井字棋、五⼦棋等⼈⼯智能⼈机对抗下棋程序。

具体步骤

给你⼀颗⼆叉树。告诉你⼩紫和⼩⿊玩游戏。紫⾊和⿊⾊圆圈代表他们两个。我们是站在⼩紫的⾓度来描述的。⼩紫想要他⾃⼰的得分最⼤

所以⼩紫玩的时候，⼆叉树的那⼀层叫MAX层。⼩⿊想要⼩紫的得分最⼩化，⼩⿊的叫做MIN层。我们总是让⼩紫第⼀个开始，假设下⾯这个⼆叉树，我们只知道叶⼦节点的值（别管为啥，先学好算法原理，后续如何应⽤这个算法我还打算继续写博客和录视频讲解。）：

在这⾥给出定义，MAX层的节点的值是什么？？是它的⼦节点⾥⾯的最⼤值，MIN层的值是它的⼦节点⾥⾯的最⼩值。直接上图。MIN层是选择其孩⼦节点中最⼩值。

MAX层选择其孩⼦节点中的最⼤值。

算法概念就是这个样⼦。

算法的输⼊是构造的这⼀棵满⼆叉树，输出是最上层MAX节点的值。

代码实现

class Node{ //结点类

public:

const int value;

Node *left;

Node *right;

Node(int v,Node* l,Node* r):value(v),left(l),right(r) {};

};

为了遍历这棵树，⾸先我们得创建出来这棵树对吧？但是你的代码⾥没有创建⼆叉树这⼀部分啊。别急，⼀会给出完整代码，现在先专注于