宽度优先反复加宽及其启发式搜索算法研究

首先针对搜索树中深度固定且目标唯一的寻优问题，指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高，基于此，提出了基于宽度优先反复加宽的启发式搜索算法ＩＷＡ＊，算法ＩＷＡ＊是可采纳的。为了保持算法ＩＷＡ＊的搜索效率高于算法ＩＤＡ＊的搜索效率，同时又使算法ＩＷＡ＊的存贮空间复杂度减低，文中基于分层技术，提出了基于深度优先的ＩＷＡ＊算法──ＩＤＷＡ＊。算法ＩＤＷＡ＊也是一个可采纳的启发式搜索算法。     

游戏地图最短路径搜索设计与实现

最短路径搜索是directx游戏的一项核心技术,文章分析了常用的搜索算法:宽度优先,深度优先和启发式搜索,最后剖析采用搜索树的A*算法来实现大地图与复杂地形的最短路径搜索。     

N皇后问题的启发式算法探讨

搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,并将其与深度优先和宽度优先等搜索策略进行了分析和比较,得出了几点关于设计启发式算法的启示。     

通过八数码问题比较搜索算法的性能

搜索算法的核心在于搜索策略的制定.一般的搜索算法采用无信息指导的搜索策略,如深度优先搜索(DFS)和宽度优先搜索(BFS),还有一些搜索算法采用了启发式信息指导的搜索策略,如A*算法.不同的搜索策略会使得搜索算法的性能有很大的差异.使用以上3种搜索算法实现八教码问题的求解,分析和比较三者所表现出来的性能,同时指出3种搜索算法的特点和应用范围,最后给出分析结论以指导开发和使用更加高效的搜索策略.     

分布式并行宽度优先搜索与15-迷问题的完全解

宽度优先搜索(Breadth-First Search,BFS)是一种基本的最佳优先搜索算法(Best-First Search)。它在模型检查、模式数据库计算以及确定问题状态空间半径等领域中有着重要的应用。宽度优先搜索作为一种系统的图搜索算法,它通常比深度优先搜索(Depth-First Search,DFS)有效得多,后者无法探测出表示同一状态的重复节点并且需要在产生所有路径后才能确定出最优解。但是,宽度优先搜索的适用规模因其空间需求大的特点受到极大限制。近来,利用磁盘作为二级缓存来克服BFS内存限制的相关技术被提出。然而,单台计算机的存储能力总是有限的。因此引入分布式并行宽度优先搜索,结合多台机器的计算能力和存储资源来完成大规模的宽度优先搜索。最后,以15-迷(15-Puzzle)问题为平台,计算其完全解(状态空间规模超过1013)。     

用MFC动态编程实现8数码问题求解

介绍了深度优先算法、宽度优先算法、启发式搜索算法3种方法实现8数码问题,分析了3种算法的可采纳性系统的特点,并用MFC编程实现.     

求解八数码问题的几种搜索算法比较

本文针对八数码问题的求解,给出了深度优先搜索、广度优先搜索和启发式搜索之间的算法比较,并得出结论：在通常情况下,采用启发式搜索算法来进行状态空间的搜索更为方便、快捷。     

迷宫搜索算法的比较研究

研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较.在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度.通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用.     

人工智能中求解八数码问题算法的实现与分析

针对八数码问题的求解,给出了深度优先搜索、广度优先搜索和启发式搜索(譬如A*算法)之间的算法比较,通过实验验证各种算法并得出结论:在通常情况下,采用启发式搜索算法来进行状态空间的搜索更为方便、高效。     

分支限界法在游戏地图寻径中的应用

分析了游戏地图寻径中的宽度优先,深度优先和启发式搜索算法,提出了一种基于宽度优先直接标记路径的分支限界搜索算法,最多使用O(N+L)的时间完成最短路径搜索,能很好地适用游戏地图中复杂地形的寻径要求。     

众核平台上广度优先搜索算法的优化

图算法在多个领域具有重要的应用价值。随着社会信息化程度的提高,需要处理的图数据量越来越大,图算法的性能已成为研究热点。广度优先搜索算法是一种重要的图算法,研究它的性能优化技术可以为其他图算法的性能优化提供借鉴。目前,在新一代Xeon Phi众核处理器上的工作均基于自顶向下算法且没有考虑到非均匀访存(NUMA)对性能的影响。文中以混合广度优先搜索算法为基础,结合NUMA拓扑结构,从任务分配、向量化和数据预处理3个方面展开优化,在Xeon Phi平台上设计并实现了高性能并行广度优先搜索算法。一系列实验结果表明,优化后的算法在不同规模的测试数据上与Graph500官方优化的算法相比取得了50%~145%的性能提升。     

Free Pattern Search for global optimization

An efficient algorithm named Pattern search (PS) has been used widely in various scientific and engineering fields. However, even though the global convergence of PS has been proved, it does not perform well on more complex and higher dimension problems nowadays. In order to improve the efficiency of PS and obtain a more powerful algorithm for global optimization, a new algorithm named Free Pattern Search (FPS) based on PS and Free Search (FS) is proposed in this paper. FPS inherits the global search from FS and the local search from PS. Two operators have been designed for accelerating the convergence speed and keeping the diversity of population. The acceleration operator inspired by FS uses a self-regular management to classify the population into two groups and accelerates all individuals in the first group, while the throw operator is designed to avoid the reduplicative search of population and keep the diversity. In order to verify the performance of FPS, two famous benchmark instances are conducted for the comparisons between FPS with Particle Swarm Optimization (PSO) variants and Differential Evolution (DE) variants. The results show that FPS obtains better solutions and achieves the higher convergence speed than other algorithms.     

改进的二分法查找

当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找（binary search）是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为[logn]＋1。在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算法。改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和[logn]＋1之间,明显优于二分查找的[logn]＋1。在实际应用中利用改进的二分法可以极大地提高查找效率。     

基于双向广度优先搜索的魔力方块问题求解

将魔力方块问题与八数码问题进行对比分析,通过讨论魔力方块问题是否有解、解的最少步数、状态表示、状态判重、状态转换关系等相关问题,提出一种基于双向广度优先搜索和状态转换表的求解算法。实验结果表明,与有界深度优先搜索、简单广度优先搜索及A*搜索算法相比,该算法效率较高,稳定性较好,可以实现魔力方块问题的实时求解及演示。     

改进的和声搜索算法在函数优化中的应用

针对函数优化问题,通过分析和声搜索算法的2个关键参数(和声微调概率与和声微调幅度)对算法搜索性能的影响,提出和声微调概率与和声微调幅度随搜索过程的进行而动态适应变化的方法,从而得到9种改进的和声搜索算法。仿真实验表明,所得方法具有较好的优化性能,计算结果优于M_IHS算法。     

Stochastic Modeling of Branch-and-Bound Algorithms with Best-First Search

Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.     

基于平衡搜索策略的多目标粒子群优化算法*

鉴于平衡全局和局部搜索在多目标粒子群优化算法获取完整均匀Pareto最优前沿方面的重要性,设计平衡全局和局部搜索策略,进而提出改进的多目标粒子群优化算法(bsMOPSO).文中策略在局部搜索方面设计归档集自挖掘子策略,通过对归档集中均匀分布的部分粒子进行柯西扰动,使归档集涵盖整个前沿面的局部搜索.在全局搜索方面设计边界最优粒子引导搜索子策略,以边界最优粒子替换部分粒子的全局最优解,引导粒子向各维目标的边界区域搜索.选取4种对比算法在ZDT和DTLZ系列的部分测试函数上进行实验,结果表明bsMOPSO具有更快的Pareto最优前沿收敛效率和更好的分布性.     

具有邻域搜索机制的爆炸搜索算法

受烟花(炸弹)爆炸的启发,提出一种新型的智能优化算法——爆炸搜索算法(ESA)。该算法引入邻域搜索的思想,包含3个重要算子：爆炸搜索算子,迁移算子,变异算子,具有较大的局部-全局搜索能力,且收敛速度快、稳定性好。对benchmark函数集进行仿真并与CPSO等算法进行比较,实验结果证实了ESA的高效性。     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

Search based software testing of object-oriented containers

Automatic software testing tools are still far from ideal for real world object-oriented (OO) software. The use of nature inspired search algorithms for this problem has been investigated recently. Testing complex data structures (e.g., containers) is very challenging since testing software with simple states is already hard. Because containers are used in almost every type of software, their reliability is of utmost importance. Hence, this paper focuses on the difficulties of testing container classes with nature inspired search algorithms. We will first describe how input data can be automatically generated for testing Java containers. Input space reductions and a novel testability transformation are presented to aid the search algorithms. Different search algorithms are then considered and studied in order to understand when and why a search algorithm is effective for a testing problem. In our experiments, these nature inspired search algorithms seem to give better results than the traditional techniques described in literature. Besides, the problem of minimising the length of the test sequences is also addressed. Finally, some open research questions are given.