博弈树启发式搜索的α-β剪枝技术研究
作者：张聪品， 刘春红， 徐久成， ZHANG Cong-pin， LIU Chun-hong， XU Jiu-cheng
作者单位：河南师范大学,计算机与信息技术学院,智能信息处理实验室,河南,新乡,453007
刊名：
计算机工程与应用
英文刊名：COMPUTER ENGINEERING AND APPLICATIONS
年，卷(期)：2008,44(16)
被引用次数：1次
参考文献(5条)
1.王文杰;叶世伟人工智能原理与应用 2004
2.Luger G F Artifical intelligence structures and strategies for complex problem solving 2006
3.王永庆人工智能原理与方法 2003
4.Claney W J Heuristie classification 1985
5.Cohen P B;Feigenbaum E A The handbook of artifical intelligence 1982
本文读者也读过(8条)
1.危春波.王海瑞.文乔农.Wei Chunbo.Wang Hairui.Wen Qiaonong博弈树搜索算法的分析与实现[期刊论文]-科技广场2007(5)
2.岳金朋.冯速博弈树搜索算法概述[期刊论文]-计算机系统应用2009,18(9)
3.蒋加伏.陈蔼祥.唐贤英基于知识推理的博弈树搜索算法[期刊论文]-计算机工程与应用2004,40(1)
4.李红.吴粉侠.刘小豫.LI Hong.WU Fen-xia.LIU Xiao-yu博弈树搜索算法研究[期刊论文]-长春工程学院学报（自然科学版）2007,8(2)
5.王镌博弈树搜索的算法改进[期刊论文]-福建电脑2004(2)
6.吕伟忠.Lu Weizhong一种改进决策树剪枝算法的研究[期刊论文]-微型电脑应用2011,27(5)
7.焦尚彬.刘丁.JIAO Shang-bin.LIU Ding博弈树置换表启发式算法研究[期刊论文]-计算机工程与应用2010,46(6)
8.纪洪生.JI Hong-sheng基于概率的剪枝算法[期刊论文]-电脑知识与技术（学术交流）2006(11)
引证文献(1条)
1.蔡增玉.方娜.甘勇.贺蕾智能五子棋博弈关键技术研究[期刊论文]-郑州轻工业学院学报（自然科学版）
2010(6)
本文链接：https://www.doczj.com/doc/a218403450.html,/Periodical_jsjgcyyy200816016.aspx
实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解8数码问题 （1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n） 其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。 （2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。 实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路 八数码问题的求解算法 （1）盲目搜索 宽度优先搜索算法、深度优先搜索算法 （2）启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)
1、程序源代码 #include
博弈树的启发式搜索问题 A方、B方必须是完备博弈，它有三个条件： 1、A，B双方轮流博弈。博弈的结果只有三种情况：A胜，B败；A败，B胜；A，B平手。 2、任一方都了解当前的棋局和历史的棋局。 3、任一方都分析当前的棋局，并能作出有利于自己，而不利于对方的策略。 我们描述博弈过程采用与/或树 1、博弈的初始棋局作为初始节点 2、‘或’节点与‘与’节点逐层交替出现。自己一方扩展节点之间是‘或’，对方扩展节 点之间是‘与’。双方轮流扩展。 3、所有能使自己获胜的终局都是本原问题，相应的节点是可解节点。 本问题其实是一个构造博弈树的问题。对给定的棋局，该棋局中A，B方的棋子数相等，并且轮到A方下。这样构成一个初始棋局，称一个状态。当A或B下一个棋子后，又形成一个新的状态。 任何一方都希望自己取得胜利，因此当某一方有多个方案可供选择时，他总是跳最有利于自己而最不利对方的方案。此时我们站在A的立场上看，可供A选择的方案之间是‘或’的关系，可供B的方案之间是‘与’的关系。因为主动权在A上，A必须考虑任何一个可能被B选中的方案。 极大极小分析方法的特点： 1、它是为其中一方寻找一个最优的行动方案的方法 2、为了当前最优的方案，需要对各个方案能产生的后果进行比较，具体地说就是考虑每个方案实施后，对方可能采取的行动，并计算可能的得分 4、为了计算得分，需要根据问题的特性定义一个估价函数，用来计算当前博弈树端节点的 得分，该得分也称静态估值 5、当端节点估值后，再推算父节点的得分，推算方法是对于‘或’节点，选择子节点中最 大的得分作为自己的得分，对于‘与’节点，选择子节点中最小的得分作为自己的得分，父节点得得分也称倒退值 6、若某一个行动方案能获得最大得倒退值，则它就是当前最好得方案 在本问题中，假设棋盘为4*4的矩阵，A方的棋子为1，B方的棋子为－1，空格为0。 我们定义估价函数为：在某一棋局状态，A方棋子可能占满的整行，整列，整斜线总和与B 方棋子可能占满的整行，整列，整斜线总和的差。这儿的可能是指棋局上留出的空格让A 方或B方全摆放它的棋子。显然如果A方的大。它的下棋选择的策略范围就大。 对某个棋局用极大极小分析后，得出A下一步的最佳策略，同时也给出B的最不利A 的策略，这样一直循环，直到棋局上无空格，如果棋局上A已经胜出了。那么就意味着B 如何采取对A最不利的策略，A也能胜出，表明A处于必胜状态。 程序说明： 编写语言：Matlab6.5 主函数：Chess.m
博弈树 实现计算机与人对弈，诸如象棋、围棋等双方对垒的游戏，是一件饶有趣味的事情。在这里，我们将讨论实现这种人机完备信息博弈时常用的树型结构及其基本算法。所谓人机完备信息博弈，是指人机对垒，依次轮流走步，而且双方的走步信息完全公开。 为了引起对弈者的兴趣，计算机一方必须尽可能多地知道对方己经走过的棋步和将可能走的棋步。对于编程者来说，要使得计算机能懂得比赛规则并记住当前格局，就得建立恰当的数据结构；要使得计算机能在对弈中选择最可能致胜的走步，就得为之设计一个“聪明”的算法。 博弈树适应了这两个需要，它将对垒的初始格局作为根结点，把所有由初始格局经过合法一步得到的新格局作为其子结点，然后以新格局为根，由此新格局产生的格局为其子结点，依次类推，得到一棵包罗对垒中各种可能格局变化的树，并通过对这棵树的遍历，分析确定计算机的走步。这棵树就是这里所说的博弈树。 [例1]井字棋游戏 问题描述： 从一个空的3*3的棋盘开始，甲乙二人轮流放置棋子到棋盘上未被占据的方格中。如果甲第一个放，他把棋子放在中央方格里；然后轮到乙放，他把棋子放在第一行中间的方格里；于是又轮到甲放，……，如此进行下去，判定胜负的方法是：若某一游戏者若有3枚棋子占据了一横线或一竖线，或一对角线，则该游戏者获胜；若至整个棋盘被占满还没有一方获胜，则为平局。 算法分析： 我们让计算机模拟甲方，称为max选手，与计算机对手的乙方称min选手，上述博弈由这两位选手对垒，双方依次轮流走步。 博弈树以棋盘状态作为结点。开始时空棋盘作为树根，max先放。max选择某个空格放置棋子后的棋盘所有可能状态，都作为根的子结点出现在树的第一层。第二层的结点是min 方走完后的可能棋盘状态，min方从第一层的某个结点出发，选择某个空格放置棋子后的所有可能棋盘状态都作为该结点的子结点出现在第二层。下图的树称作博弈树，树根并不是空棋盘，这棵树的第二层并不是游戏终止时的棋盘状态，我们还可以画出第三层、第四层、……的结点，但在一般情况下，由于计算机存储器大小和运算速度的限制，不能把博弈树构造到游戏终止时的棋盘状态，而只能构造到某一特定的深度。
编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月
南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）：
启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法
The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent https://www.doczj.com/doc/a218403450.html,pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency. This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data. Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm
实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰
一、实验内容： 使用启发式搜索算法求解8数码问题。 1、编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个
南京信息工程大学 研究生实验报告 课程名称人工智能与专家系统 实验名称利用α-β搜索过程的博弈树搜索算法编写一字棋游戏学生姓名王灿田 学号 20111221332 院系信息与控制学院 专业系统分析与集成 任课教师梅平 2012年6月10日
利用α-β搜索过程的博弈树搜索算法编写一字棋游戏 1.α-β搜索过程 在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？ 设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点，所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息，不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程正是这样一种搜索方法。 图1 MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图1中，其中一个MIN节点要全部生成A、B、C、D四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才赋给这个MIN节点的倒推值－∞。其实，如果生成节点A后，马上进行静态估值，得知f（A）＝－∞之后，就可以断定再生成其余节点及进行静态计算是多余的，可以马上对MIN节点赋倒推值－∞，而丝毫不会影响MAX的最好优先走步的选择。这是一种极端的情况，实际上把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得类似的效果，这就是α-β过程的基本思想。
深度学习模型剪枝的评述 摘要 近年来，深度神经网络在机器视觉和自然语言处理领域都取得了巨大的成功。然而，要将这些模型部署到诸如机器人芯片、智能手机等微型嵌入式设备上仍是一个巨大的挑战。因此，对于这样的平台，模型压缩是一种降低内存消耗和计算复杂度的合理解决方案，目前处理这一问题的技术手段仍然是模型剪枝，而通道级别的模型剪枝又是最有效的手段之一。因此如何有效的实现通道级别的模型剪枝是至关重要的，并且一直是一个具有大量研究成果的主题。 本文阐述了近年来出现的通道级别模型剪枝的主要技术手段，我们主要讨论各个论文的研究成果和遇到的问题，以及根据共同的特点按类别组织的解决方案列表，并且还列出了各个实验结果之间的比较。 关键词：深度学习，模型压缩，通道剪枝 一．引言 在最近这几年中，深度学习赢得了越来越多的关注，并且促进了非常多领域的突破，这依赖于深度神经网络百万甚至千万级别的参数量，和图形处理器的高速计算能力都起着至关重要的作用。 然而，深度学习模型不管在训练还是在部署到设备上时都存在需要问题。比如，[1]在2012年的ImageNet Challenge中取得了突破性的成果，使用了包含6000万个参数的5个卷积层和3个全连接层的网络。通常需要两到三天的时间在NVIDIA K40机器来训练整个模型的ImagetNet数据集。有时在仅依赖于全连接层的架构中，参数的数量可以增长到数十亿[2]。另一方面，卷积运算消耗了大量的计算资源，而这在移动设备上是非常稀缺的，数十亿的网络参数对于嵌入式设备来说也是高存储开销。以VGG-16模型为例，它拥有超过1.38亿个参数，占用超过500MB的内存空间。同时，224×224图像的分类需要300亿次浮点运算(FLOPs)。显然，将如此大的模型直接部署到嵌入式设备中是不切实际的。 因此，在精度没有明显下降的情况下压缩深度模型是一个关键问题。在这种情况下，许多模型压缩方法也相继被提出。最近的一些压缩和加速方法，包括权值剪枝[3-5]、网络量化[6-8]、低秩近似[9,10]、高效模型设计[11-12]。神经元剪枝方法[3]通过去除一些不那么重要的连接，使权值变得稀疏。网络量化针对存储空间压缩问题，提出了一种降低参数表示精度的网络量化[7]算法。低秩近似[9]利用低秩矩阵技术将权值矩阵分解成几个存储空间较小的小矩阵。但是以上方法或多或少存在一些问题，权值剪枝与网络量化需要特殊的软硬件结合使用才能达到好的效果，低秩近似对于1*1的卷积并无效果。而高效模型设计更多关注设计一些不同的网络模型而不是优化已有的卷积运算或者网络架构来压缩加速。 通道剪枝[4,5]是另一种权值剪枝方法，不同于神经元剪枝。与去除单个神经元连接相比，修剪整个通道有两个优点。首先，它不引入原始网络结构的稀疏性，因此不需要对生成的模型进行特殊的软硬件实现。其次，推理阶段不需要庞大的磁盘存储和运行时内存。 本文综述了近年来通道剪枝在深神经网络的压缩和加速研究进展，这些研究引起了深度
6一个猎人要带着一只狼、一只羊、一捆草过河，但是人不在的时候，狼会吃羊、羊会吃草，猎人每次只能带一样东西过河。试用状态空间图求出他们能顺利过河的方案。 解：用四元组（f ，w ，s ，g ）表示状态，其中f 表示猎人，w 表示狼，s 表示羊，g 表示草，其中每个元素都可以为0或1，表示在左案，1表示在 右岸。四元组可表示的状态共有16种，其中合法状态为10种： （0，0，0，0）（0，0，0，1）（0，0，1，0）（0，1，0，0）（0，1，0，1） （1，0，1，0）（1，0，1，1）（1，1，0，1）（1，1，1，0）（1，1，1，1） 初始状态为（0，0，0，0）目标状态为（1，1，1，1） 共有七种操作：从左岸到右岸三种，从右岸到左岸四种 操作符 条件 动作 p 1 f=0，w=0，s 和g 相异 f=1，w=1 p 2 f=0，s=0， f=1，s=1 p 3 f=0，g=0，w 和s 相异 f=1，g=1 q 0 f=1，s 和g 相异，w 和s 相异 f=0 q 1 f=1，w ＝1，s 和g 相异 f=0，w ＝0 q 2 f=1，s ＝1， f=0，s ＝0 q 3 f=1，g ＝1，w 和s 相异 f=0，g ＝0 (0,0,0,0)(1,0,1,0) p 2 q 2 (0,0,1,0)(1,1,1,0)p 1 q 1 (1,0,1,1) (0,0,0,1)q 0 p 3 q 3(0,1,0,0) q 2p 2 (1,1,0,1)p 3 q 3 q 2 p 2 p 2 q 2 (0,1,0,1) (1,1,1,1) p 2 q 2 q 0 方案有两种：p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2 8.琴键翻动 （供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为0，关状态为1，全部可能的状态为 ： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。 翻动琴键的操作抽象为改变上述状态的算子，即F ＝{a, b, c} a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}> 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。
AlphaBeta剪枝算法 关于AlphaBeta剪枝的文章太多，这个方法是所有其它搜索方法的基础，得多花些时间认真地理解。 先把基本概念再回顾一遍： 节点：在中国象棋中就是一个棋盘的当前局面Board，当然该轮到谁走棋也是确定的。这里的圆形节点表示终止节点，在中国象棋里就是一方被将死的情况（或者到达了搜索的最大深度），后续不会再有着法产生，游戏如果走到这里就会结束。在引擎里通常给红方一个很大的评估值，如+30000，给黑方一个很小的评估值，如-30000，来方便地判断这种结束局面。（胜利局面有稍微不同的表示法，用-30000+层数ply来表示） 连线：表示一步着法Move，通过这步着法后，局面发生变化，先后手也要交换。 层：通常的术语是ply，复数形式是plies，也有称为levels，当然与depth也是对应的。这个术语是为了与比赛里常说的回合相区分，一个回合通常包含2步，这个ply就表示某一方走了一步。根节点记为0层，以下的层数递增。 深度depth：要注意是从下到上的，还是从上到下的。（1）通常的算法书中都是从下到上递增的，即根节点为最大搜索深度，走到最底部的叶子结点为0，这种算法只要记住一个depth 值就可以了。（2）而另一种记法是根部结点为0，越向下depth增加，这时在搜索时就要传递2个参数值，depth和maxDepth，稍微有点啰嗦，应该也会影响一点效率。另外在探查置换表中的结点时，用第（1）种记法也方便一些，因为要知道从当前节点迭代的深度值，否则还要在置换表中保存depth和maxDepth两个值。 AlphaBeta剪枝方法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。 这种方法的前提假设与Minimax也是一样的： 1）双方都按自己认为的最佳着法行棋。 2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算法描述） 3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。 但要注意：用Negamax风格来描述的AlphaBeta中的评估函数，对轮到谁走棋是敏感的。 也就是说： 在Minimax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋评估值仍是100。 但在Negamax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋时评估值要为-100。
谈搜索算法的剪枝优化 许晋炫 【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧。首先由回溯法解决迷宫问题展开论述，介绍了什么是剪枝；而后分析剪枝的三个原则棗正确、准确、高效，并分别就剪枝的两种思路：可行性剪枝及最优性剪枝，结合例题作进一步的阐述；最后对剪枝优化方法进行了一些总结。 【关键字】搜索、优化、剪枝、时间复杂度 引论 在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。 所以，对程序进行优化，就成为搜索算法编程中最关键的一环。 本文所要讨论的便是搜索算法中优化程序的一种基本方法棗“剪枝”。 什么是剪枝 相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 1、这个方向有路可走，我没走过 2、往这个方向前进 3、是死胡同，往回走，回到上一个路口 4、重复第一步，直到找着出口 这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。 我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？ 答案是：可以的。 剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。 搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。 剪枝的原则 1、正确性 正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也
启发式搜索——初识A*算法
A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
第三章 搜索策略课后习题及答案 一、选择题： 1. 启发式搜索中，通常OPEN表上的节点按照它们f函数值的_____顺序排列。 （ D ） A平均值 B 递减 C 最小 D递增 2. 按尼尔逊(Nilsson)提出的有序搜索基本算法指出,一个节点的希望程度大，则f值_____。 （ B ） A 不变化 B 小 C 大 D 为0 3. 如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为_____。（ B ） A A*算法 B A算法 C有序搜索 D启发式搜索 4. 在与或树和与或图中，我们把没有任何父辈节点的节点叫做_____。 （ C ） A 叶节点 B端节点 C根节点 D 起始节点 5. 对于八数码问题： 起始棋局 —> 目标局棋 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 取h(n)=W(n)， W(n)用来计算对应于节点n的数据库中错放的棋子个数。请问需要扩展多少个节点才能到达目标？ （ C ） A 20 B 13 C 6 D 11
6. α-β剪枝技术中，一个MIN节点的β值等于其后继节点当前（ ）的最终倒 推值。 （ A ） A 最小 B 最大 C 平均 D α值 7. α-β剪枝技术中，“或”节点n的α值如果不能降低其父节点的β值，则对节点n以下的分枝可停止搜索，并使节点n的倒推值为α。这种剪枝称为_____。 （ A ） A β剪枝 B α剪枝 C α-β剪枝 D极小极大分析法 8. 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的_____途径(如果有路径存在时)。 （ B ） A 可行 B 最短 C 最长 D 解答 9. A*算法是一种_____。 （ ABD ） A 图搜索策略 B 有序搜索算法 C 盲目搜索 D 启发式搜索 10. 应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法的算法就叫做_____。 （ C ） A 盲目搜索 B 深度优先搜索 C 有序搜索算法 D 极小极大分析法 二、 填空题： 1. OPEN表用于存放未扩展的节点，CLOSED表存放_已扩展_的节点。 2. 通常OPEN表记录了节点及其___ 父_节点。
ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2005年第45卷第S1期 2005,V o l.45,N o.S15/39 1748-1752 最大频繁项集挖掘中搜索空间的剪枝策略 马志新, 陈晓云, 王 雪, 李龙杰 (兰州大学信息科学与工程学院,兰州730000) 收稿日期:2005-05-20 基金项目:国家自然科学基金资助项目(60473095)作者简介:马志新(1973-),男(汉),甘肃,副教授。 E-mail:mazhx@lz https://www.doczj.com/doc/a218403450.html, 摘 要:最大频繁项集挖掘可以广泛应用在多种重要的Web 挖掘工作中。为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略。这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝。应用该策略,对M A FI A 算法进行改进优化。实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原M AF IA 算法提高3～5倍。 关键词:W eb 挖掘;最大频繁项集;剪枝策略;搜索空间中图分类号:T P 311文献标识码:A 文章编号:1000-0054(2005)S 1-1748-05 Pruning strategy for mining maximal frequent itemsets MA Zhixin ,CHE N Xiaoyun ,WANG Xue ,LI Lon gjie (School of I nformation Science and Engineering ,Lanzhou University ,Lanzhou 730000,China ) Abstract :M in ing maximal frequent itemsets is a fundamental problem in man y practical w eb m ining ap plications.T his paper presen ts ESEquivPS (exten sion sup por t equivalency pruning strategy),a n ew search space p runing s trategy for mining m axim al frequent itemsets to effectively reduce the s earch s pace.ESE qu ivPS w as based on a depth-first travers al of lexicographic su bset en umer ation tree and uses equivalency of item's ex tension supports to pru ne s earch space.Furthermore,th e M AFIA (m axim al frequen t items et alg or ith m)w as improved by u sing ESEquivPS.T he ex perimental r esu lts show that ES EquivPS can efficiently redu ce the search space.E specially on s pars e dataset w ith longer items ets ,the siz e of search s pace can be trimmed off by 2/3and n ew algorithm runs around three to five times fas ter th an previou s M AFIA algorithm. Key words :w eb m ining; maximal frequent items ets ; pruning strategy;search space 频繁项集挖掘是一类重要的数据挖掘问题,可以广泛应用在客户行为模式分析、网页关联分析、日志分析和网络入侵检测等重要的Web 挖掘工作中。 该问题描述如下:给定事务数据库D ,项目集合I 和用户指定的支持度阈值 ,频繁项集挖掘是在D 中找出支持度大于或等于阈值 的所有项集。 典型的频繁项集挖掘算法是A priori 以及在此基础上的各种改进算法[1],该类算法采用自底向上广度优先的思想,依次计算出所有的频繁1项集,频繁2项集,直到找出所有的频繁项集。当出现大量长的频繁项集时,该类算法代价很高,需要多次扫描数据库并且产生大量的候选项集,对于长度为m 的频繁项集需要枚举出所有可能的2m -2个子集,出现组合问题,导致算法效率低下或无法计算。因此,最大频繁项集挖掘和封闭频繁项集挖掘方法受到该研究领域的重视,先后提出多种重要的最大频繁项集挖掘算法和封闭频繁项集挖掘算法[27]。 如何有效地进行搜索空间剪枝是最大频繁项集挖掘研究工作的一个核心[6]。本文提出了一种新的搜索空间剪枝策略:扩展支持度相等性剪枝策略ESEquivPS (ex tension support equivalency pruning strateg y ),该策略基于词典序子集枚举树,利用树中子节点与父节点的扩展集中相同项的扩展支持度相等的特性,对搜索空间进行削减。该策略可以方便的应用到各种最大频繁项集挖掘算法中,大幅度提高算法的效率。本文结合ESEquivPS 对MA FIA 算法进行了优化改进,并在不同特征的Web 数据集上进行了实验验证。实验结果表明,该剪枝策略可以有效削减搜索空间,改进后的算法效率明显优于原有的MAFIA 算法。 1 最大频繁项集挖掘与搜索空间剪枝策略 最大频繁项集挖掘问题具体描述如下。
启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，
以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型
下面我们举一个例子——Betsy 的旅行(USACO)。 题目简述：一个正方形的小镇被分成N 2个小方格，Betsy 要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N ，计算出Betsy 能采用的所有的旅行路线的数目。 实际上，由于Betsy 的每一次移动，只会影响到附近的格子，所以每次执行剪枝判断时，应当只对她附近的格子进行检查： 对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy 每次移动到一个新位置，都只会使与之相邻的至多4个格子的标志值发生变化，只要检查它们的标志值即可。 而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对Betsy 附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理： 上图给出了可以剪枝的三种情况。由于Betsy 到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。 一、 优性剪枝 下面举一个应用最优性剪枝的典型例题——最少乘法次数。 题目简述：由x 开始，通过最少的乘法次数得出n x ，其中n 为输入数据。（参见参考书目1） 因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列{}i a ，满足 ???><<=+==)1(),1()1(1i i k j a a i a k j i 要求n a t =，并且使t 最小。 我们选择回溯法作为本程序的主体结构：当搜索到第i 层时，i a 的取值范围
搜索中的剪枝优化 在11+-i a 到2*1-i a 之间，为了尽快接近目标n ，应当从2*1-i a 开始从大到小为i a 取值，当然，选取的数都不能大于n 。当搜索到n 出现时，就得到了一个解，与当前保存的解比较取优。最终搜索结束之后，即得到最终的最优解。 如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化： 优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是i a ，即当前搜索深度为i ）： ????? ?=i a n h 2log 然而，这个估价函数的准确性太差，特别是当i a 大于2 n 时，h 只能等于1，根本不能发挥剪枝的作用。因此，无论是深度优先的回溯法还是宽度优先的A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。 下面，我们再讨论一些进一步的优化手段—— 优化之五：当数列中的当前最大数i a 超过2 n 后，原估价函数就难以发挥作用了。但是，此后的最优方案，实际上就等价于从1a 到i a 这i 个数中，选出尽可能少的数（可重复），使它们的和等于n 。这个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。 二、“最少乘法次数”的估价函数的改进： 最初的估价函数的设计思路实际上是在当前数列i a a ,,1 的基础上理想化的构造i p i i a a a 2,,4,2 ，当i p i p a n a 122+<<时，原估价方法认为只需再进行一次加法，即找一个数与i p a 2相加就够了。 然而，这只是保证了能够得到大于等于n 的数，并不一定恰好得到n 。我们可以作如下分析： 首先，任何一个自然数i 都可以表示成),()12(2___-∈+Z m k m k 的形式，我们可以设)(i k 表示一个自然数i 所对应的k 值。显然，对于任何两个自然数a 和b ，都有()()(){}b k a k b a k ,min ≥+（我们由此可以很容易的联想到“奇+奇=偶，偶+偶=偶，奇+偶=奇”的性质）。 然后，我们再研究前述估价时所构造的数列： i p i i i a a a a a a 2,,4,2,,,,21 （其中，i p i p a n a 122+<<） 在应用新的剪枝判断之前，我们应当先检验()()??p a a n i i ≥+-12/log ，这个条件可以保证只有构造上述数列才是最优的。 若存在自然数()p j j ≤≤1，使得() ()n k a k i j >2，由()()(){}b k a k b a k ,min ≥+， 则有()()()()()p t j n k a k a k a a k i j i t i p i t ≤≤>≥≥+2222 n a a i p i t ≠+∴22 （()()b k a k =是b a =的必要条件） 即i p i j a a 2,,2 中的任何一个数与i p a 2相加都不可能得到n 。 所以，如果i j i p a a n 122->-，则在得到i p a 2后，至少还需要再进行两次加法