博弈树启发式搜索的α-β剪枝技术研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。

一种新的博弈树迭代向前剪枝搜索

针对博弈树迭代加深搜索和向前剪枝搜索中误剪最佳分支的弱点,利用向前剪枝搜索与预评估搜索间的双重迭代调用,提出了一种新的博弈树迭代向前剪枝搜索方法.预评估搜索通过节点排序及调整剪枝比率可以更加准确地选取排序在前的最佳分支,进而使迭代向前剪枝搜索实现在预评估所保留的最佳分支方向进行深度搜索,二者迭代相互调用以提高向前剪枝搜索的有效性及效率.定性分析与中国象棋计算机博弈实验结果表明,迭代向前剪枝搜索提高了实时行棋决策的效率和效果,与α-β剪枝搜索相比,提高的搜索效率超过160倍,同时取得了胜负比近7倍的博弈效果.

基于alpha-beta剪枝搜索算法的中国象棋游戏设计

设计一个优秀的中国象棋游戏具有一定的经济与社会价值。但是在该系统的设计过程中,搜索算法的设计异常重要,如何设计合理的人机搜索算法实现高效和合法的行棋规则就成为我们研究的重点。文章通过对常用的人机搜索算法进行介绍,并对其进行了分析和应用。

基于改进RRT算法的移动机器人路径规划

针对快速扩展随机树(rapidly exploring random tree,RRT)算法在移动机器人路径规划过程中存在盲目搜索、内存计算量大和冗余点较多等问题,提出了改进的RRT算法。首先,随机点进行扩展时引入动态目标采样率,引导随机点向目标点方向扩展;其次,融合A*算法中代价函数策略,在加入不同权重因子之后,选取代价值合适的节点作为待扩展节点;然后,针对初始路径过长并存在过多冗余点的问题,提出反向搜索剪枝方法,对裁剪后的路径进行三次样条插值平滑处理来改善路径质量;最后,利用Pycharm对改进的RRT算法进行仿真验证。仿真结果表明,改进的RRT算法相较于传统RRT算法、RRT*算法和基于概率P的RRT算法(P-RRT),在路径的规划长度、规划时间和扩展节点数上都具有明显优势,提高了机器人的路径规划效率。

基于改进的A^(*)算法的移动机器人路径规划

针对移动机器人路径规划中的A^(*)算法存在搜索节点多、规划时间长、转弯角度大等问题,提出一种改进的A^(*)路径规划算法.改进的A^(*)算法通过启发函数权重优化和搜索空间剪枝,在保证最优路径的前提下,减少了搜索时间和计算资源的消耗.同时,使用贝塞尔曲线对规划路径进行平滑处理,使得机器人的转弯更加渐进和连续,减少移动机器人的转角损失.实验结果表明:改进后的A^(*)算法搜索节点少,规划速度快,路径长度短,提高了路径规划的效率,更适合移动机器人路径规划.

智能交通中的高效最短路径搜索算法

文章针对智能交通系统中最短路径问题,提出了一种基于预处理剪枝的最短路径快速搜索算法。该算法在Dijkstra算法的基础上,利用预处理结果进行剪枝。实验证明,与传统算法相比,在保证最优解的情况下,使用该算法平均可使搜索空间平均降低94.8%,计算速度提高26倍。

多Agent联盟结构生成算法的剪枝优化

针对与联盟值有关的联盟结构生成算法,通过归纳总结整数划分数与联盟结构图中各层联盟结构数之间的对应规律,并利用已知联盟值之间的信息对解空间进行充分剪枝,快速获得不同大小的联盟结构局部最优解,从而计算出全局最优解。通过剪枝示例统计验证算法效果,剪枝优化后的搜索空间减少50%。

分布式信息系统的高效不变搜索

在如今的信息管理系统中,存在着大量的数据,快速高效的搜索信息成为研究热点。通过有效地描述和跟踪信息系统将分布式系统中的所有监视数据关联起来,提出利用OW强度这一概念来测量监测数据对不同用户请求量的反应强度,并基于剪枝搜索完整的不变量集并结合聚类算法来提高搜索效率,通过算例证明了所提算法的有效性。

基于FP-tree的支持度计数优化策略

关联规则挖掘过程中,频繁项集的挖掘是最关键的步骤。最大频繁项集是最常用的频繁项集简化表示。基于FPtree的最大频繁项集挖掘算法多数都需要自底向上地搜索FP-tree来计算项集的支持度。而已有的支持度计算方法在计算当前项集的支持度时没有考虑已完成的支持度计算过程所获得的信息,因而造成了不必要的开销。针对该问题,提出了基于FP-tree的支持度计数优化策略(Support Count Optimization Method on FP-tree,SCOM),在付出很小的额外空间代价的条件下,充分利用已完成的支持度计数过程中获取的路径对项集的支持信息和项集之间的关系进行搜索剪枝,并设计实验将该策略应用到DMFIA算法上。实验结果表明,应用该策略的最大频繁项集挖掘算法DMFIA获得了较大的性能提升。SCOM对基于FP-tree的支持度计数进行优化,因此能够应用到所有利用FP-tree进行支持度计数的算法之中。

PASER:加性多维KPI异常根因定位模型

利用多维属性关键性能指标(key performance indicators,KPI)的可加性特征,能够实现对大型互联网服务故障的根因定位.由一项或多项异常根因导致的KPI数据变化,会导致大量相关KPI数据值的变化.提出一种基于异常相似性评估和影响力因子的剪枝搜索异常定位模型(pruning search model based on anomaly similarity and effectiveness factor for root cause location,PASER),该模型以多维KPI异常传播模型为基础,提出了衡量候选集合成为根因可能性的异常潜在分数评估方案;基于影响力的逐层剪枝搜索算法,将异常根因的定位时间降低到了平均约5.3 s.此外,针对异常根因定位中所使用的时间序列预测算法的准确性和时效性也进行了对比实验,PASER模型在所使用的数据集上的定位表现达到了0.99的F-score.

最大覆盖问题研究

最大覆盖问题是运筹学中一个经典组合优化问题。通常是现实生活中邮政服务站点,加油站点,银行选址等问题的数学抽象。最大覆盖问题一般被描述为有被服务点若干,选取若干服务点对被服务点进行服务的最小代价。最大覆盖问题已经被证明是一类NP问题,也就是不能在多项式时间内求得最优值的问题。目前国内外学者对于此问题的研究多是使用遗传,蚁群,退火模拟等启发式搜索求的近似值的方法来进行讨论。本文主要分析了最大覆盖问题的穷举解法,剪枝搜索解法和启发式搜索解法。对这三种解法进行了测试,比较算法的优劣和适用范围。通过提出对于待选边进行性价比的计算,设计出启发式函数来搜索近似最优值,最后的测试将近似最优值保持在平均2的差异值范围内。

基于博弈树搜索算法的中国象棋游戏的设计与实现

针对中国象棋游戏的设计和开发过程,通过软件工程技术的系统设计方法,分析了中国象棋的存储表示数据结构,利用了网络通信等相关方法,借助于VC++平台,采用Winsock标准编程接口完成了基于局域网的中国象棋网络游戏系统。系统主要实现了网络通讯、人机对弈、界面表示和走棋规则约束等模块。其中,核心模块人机对弈由博弈算法中的alpha-beta剪枝搜索和负极大极小算法来实现。结合测试用例及实际游戏对弈对系统进行功能测试,通过测试证明,该系统界面友好,系统的响应速度快,具有较强的应用推广价值。