博弈树搜索算法研究

通过讨论人工智能中用于计算机博奕的一般技术如极大极小搜索、Alpha-Beta剪枝、小窗口搜索,对五子棋博奕的内在规律进行了分析研究,给出解决五子棋博奕的2种优化算法,这2种优化算法大大提高了搜索效率,相比之下引入置换表后的优化算法的搜索效率更高。     

Nearest neighbor search algorithm forGBD tree spatial data structure

： This paper describes the nearest neighbor （NN） search algorithm on the GBD（generalized BD） tree. The GBD tree is a spatial data structure suitable for two- or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its-successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.     

Nearest neighbor search algorithm for GBD tree spatial data structure

This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.     

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

语音识别中基于两层词法树的跨词搜索算法

为了在连续语音识别过程中充分并且高效地使用上下文相关声学模型,提出了一种新颖的基于两层词法树的跨词搜索算法.采用两层词法树来表示搜索空间,解决了现有单层词法树的规模爆炸问题,使其有能力在词边界搜索中高效地使用上下文相关声学模型进行匹配,充分发挥上下文相关声学模型较好地描述协同发音现象的能力.实验结果表明,与词内搜索算法相比误识率平均下降60%,搜索时间达到实时,证明基于两层词法树的跨词搜索算法具有很好的识别性能.     

An efficient algorithm for mining closed itemsets

This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overheads of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.     

iGiST:一个改进的通用搜索树

分析了通用搜索树建树方法的不足以及结点溢出处理和下溢处理策略的缺陷,提出了一个改进的通用搜索树,增加了装树功能,提高了建树速度,同时对结点溢出处理和下溢处理策略作了改进,推迟了结点分裂和合并的时间,改进后的通用搜索树比原结构在系统效率和空间利用率方面有较大提高。最后给出在空间数据库系统上的实验结果。     

一种改进的威胁空间搜索算法

研究了五子棋游戏开发中极大极小搜索框架计算量太大,无用计算太多等问题.在传统经典极大极小搜索和alpha-beta剪枝基础上采用了判重,加入启发式的优化,每次选择最有"前途"的若干个决策搜索以减少搜索量,再加入基于五子棋专业棋手下棋策略,改进威胁空间搜索算法.使得计算机的搜索过程更像人的思考过程,算法复杂度大幅降低.经过测试最终编写的程序具备高响应度和智能性.     

基于权重搜索树改进K近邻的高维分类算法

信息采集技术日益发展导致的高维、大规模数据,给数据挖掘带来了巨大挑战,针对K近邻分类算法在高维数据分类中存在效率低、时间成本高的问题,提出基于权重搜索树改进K近邻(K-nearest neighbor algorithm based on weight search tree,KNN-WST)的高维分类算法,该算法根据...     

An improved Cuckoo search algorithm for multi-objective optimization

The recently proposed Cuckoo search algorithm is an evolutionary algorithm based on probability. It surpasses other algorithms in solving the multi-modal discontinuous and nonlinear problems. Searches made by it are very efficient because it adopts Levy flight to carry out random walks. This paper proposes an improved version of cuckoo search for multi-objective problems (IMOCS). Combined with nondominated sorting, crowding distance and Levy flights, elitism strategy is applied to improve the algorithm. Then numerical studies are conducted to compare the algorithm with DEMO and NSGA-II against some benchmark test functions. Result shows that our improved cuckoo search algorithm convergences rapidly and performs efficienly.     

一种高效的插值算法

通过对一般图像及传统插值算法的分析讨论 ,提出了高低阶结合的插值算法。从而有条件地解决了运算量与插值质量之间的根本矛盾。     

一种有效的性能驱动布图算法

提出了一种有效的性能驱动布局和布线算法。算法自始至终考虑互连线延时对芯片时间性能的影响，以优化芯片时间性能为主要布图目标，并兼顾布线均匀和连线总长最短。算法利用选定的单元、互连线延时计算模型以及关键路径识别算法对整个芯片进行动态的延时分析，并由此得出线网（亦称互连线）权重信息以指导迭代改善布局和布线，达到优化芯片时间性能的目的。运行实例表明本算法是正确、有效的。     

多时隙的二进制搜索防冲突算法

针对RFID系统的标签冲突问题,文章在二进制搜索树算法和Aloha算法的基础上,提出了一种新颖的算法,在二进制树的每个节点处动态地估计标签的数量,根据标签的数量使用相应的时隙数;进一步对算法的性能进行了理论分析,并且通过仿真比较了该算法与二进制搜索树算法的性能,结果证明该算法能够有效地节约能量。     

小变化量数据的高效传输算法 ——转置矩阵位压缩算法

在许多网络数据传输中,数据的变化量是很小的.目前普遍使用的算法是传输变化了的数据项,而忽略未变化的数据项.当数据变化量不大时,传输的冗余位很多,这导致传输速度慢.作者提出的转置矩阵位压缩算法,可以将变化位和非变化位清晰地分开,在以位为单位的水平上进行压缩,这样即使使用极为简单的行程编码压缩算法也可以取得极高的压缩率.试验结果表明该算法的对小变化量数据的压缩效果很好;用于处理工业控制系统状态参数、证券交易中的行情数据等时,可缓解系统的网络负荷压力,提高网络的传输效率.     

基于博弈论的背包问题优化算法

基于博弈粤论提出了一种背包问题优化算法。将背包问题的搜索空间映射为博弈的策略组合空间,背包问题的目标函数映射为博弈的效用函数,通过理性博弈主体的最优反应动态与均衡的扰动恢复过程达到优化目标。给出了算法的形式定义及描述,证明了算法的全局收敛性。仿真运算及与遗传算法的比较结果验证了算法的有效性。     

An Tentative Taboo Search Algorithm for Job Shop Scheduling

0 IntroductionThmeo juosb sschhoepduslcinhged uplrionbgl epmrosbl wehmic(hJS aSrPe) oifs oconem obfi ntahteorfiaa-lopti mization and which have proved to be NP-hard[1]. ForJSSP, Many heuristic procedures has been developed,such asprocedures based on dispatching rules for choosing the nextjobto be“dispatched”,Shifting Bottleneck Procedures basedon repeatedly opti mizing the sequence on each individual ma-chine[2],local search procedures which use neighborhood de-fined by reversing some s…     

空间网络数据库关键字查询的高效空中索引

研究无线广播环境下空间网络数据库关键字查询问题,提出一种包含路网加权四叉树、各关键字四叉树和路网距离矩阵的空中索引结构(KSSN).讨论了kNN查询处理问题,提出了高效的查询处理算法.所提出的算法能综合利用路网距离信息和关键字信息高效地消减不存在查询结果对象的路网空间,提高查询处理的效率.KSSN索引结构可推广至其他类型的查询,比如范围查询、Rank查询.在一个真实路网上进行了仿真实验,验证了基于KSSN索引结构的查询处理算法的性能.实验结果表明:所提出算法的访问时间和调谐时间分别为参照的IRRDA算法的25.13%和12.31%.     

基于GPU的多维树搜索算法在管道流体仿真中的应用

为提高邻近粒子搜索速度,使水力压裂过程中注入管道内的水流现象更好地满足实时性要求,在图形处理器(GPU)上基于光滑粒子流体动力学(SPH)算法,将结合GPU的并行操作能力和多维树搜索算法优点的多维树搜索算法应用在水力压裂管道流体模拟中。首先,给出了流体粒子的受力分析及更新颗粒位置的方法;然后,给出了该算法在管道流体模拟中的具体实现过程。最后,通过实验近似模拟水力压裂过程中管道与水流交互过程,并与其他算法进行对比分析。结果表明将本文算法应用于大规模管道流体模拟中,执行速度快了几倍,实现了水流模拟在管道中的实时性。     

一种高效的安全数据包过滤算法

基于网络编码技术,通过计算收到的数据包的线性相关性来判断其是否为非创新包,并检测它们是否为污染包,以阻止恶意节点的攻击行为,提出一个抗熵攻击和污染攻击的数据包过滤算法.分析和实验结果表明,给出的数据包过滤算法安全,并且能有效减少网络负载、提高传输效率.     

一种高效的频集挖掘算法

频集挖掘是关联规则挖掘的关键步骤,它对强规则、相关分析和时间序列有着重要的意义.常用的频集算法包括Apriori和FP-G rowth.为了提高算法效率,提出了一种基于D iffset的混合算法———D iffsetHybrid,该算法根据数据集的稀疏程度决定采用D iffset的某种形式来挖掘频集,减少了存储空间,提高了算法效率.试验表明,该算法对于稀疏数据集和稠密数据集都有良好的计算性能.