迷宫搜索算法的比较研究

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

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

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

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

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

迷宫最短路径问题新算法

提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。     

多因素制约的迷宫问题最优解的求解算法

介绍迷宫问题及其最优解,引入多因素制约的迷宫问题。重点讨论多因素制约迷宫问题最优解的含义及基于广度优先搜索的求解算法,并通过两个实例分析如何基于广度优先搜索算法求解这类迷宫问题的最优解,并给出算法的伪代码。最后,进一步讨论和总结这类迷宫问题最优解的求解算法。     

基于单元树结构的广度优先P2P搜索算法

提出基于单元树结构的广度优先搜索算法UTBFS。将单元树结构生成算法与广度优先算法相结合,阐述UTBFS的实现思路,对其时间复杂度、空间复杂度、可行性、优越性进行分析。实验仿真结果显示,相比于传统的广度优先搜索算法和随机广度优先搜索算法,UTBFS减少了需要转发消息的邻居节点个数和冗余消息,因此性能更优。     

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

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

基于广度优先搜索的空间搜索算法

广度优先搜索是图的遍历的一种重要的算法。本文在广度搜索算法的基础上实现空间搜索算法。算法的实现在二维和三维空间同时适用,而且可以根据实际情况及搜索条件在方位和方式上进行调整。该算法还用到了C＋＋标准模板库中的队列。在空间搜索算法实现上本文有较大的参考价值。     

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

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

广度优先搜索的一种实现算法

广度优先搜索是图的一种常用遍历方法,在许多书籍中所提到的广度优先搜索算法均对不带权图的搜索,本文提出利用迪杰斯特拉算法实现广度优先搜索,不仅能对不带权的图实现搜索,而且对带权的图也同样适用。     

基于向心法则的电脑鼠走迷宫算法设计与优化

电脑鼠是一个集自主迷宫搜索、搜索完后最短路冲刺、传感与控制于一体的自主移动机器人系统.具体设计和实现了基于向心法则迷宫搜索算法,并对算法和迷宫搜索流程进行优化,实验证明优化后的算法,在保持原有算法高效的基础上具有更加好的局部效应,相比同类型的算法,优化后的向心法则是一种非常高效的迷宫搜索算法.     

GO-MOKU SOLVED BY NEW SEARCH TECHNIQUES

Many decades ago, Japanese professional Go-Moku players stated that Go-Moku (five-in-a-row on a horizontally placed 15×15 board) is a won game for the player to move first. So far, this claim has never been substantiated by (a tree of) variations or by a computer program. Meanwhile, many variants of Go-Moku with slightly different rules have been developed. This paper shows that for two common variants, the game-theoretical value has been established.
Moreover, the Go-Moku program Victoria is described. It uses two new search techniques: threat-space search and proof-number search. One of the results is that Victoria is bound to win against any (optimal) counterplay if it moves first. Furthermore, it achieves good results as a defender against nonoptimally playing opponents. In this contribution we focus on threat-space search and its advantages compared to conventional search algorithms.     

Coordination of intelligent agents in real-time search

Search is a fundamental problem-solving method in artificial intelligence. Traditional off-line search algorithms attempt to find an optimal solution whereas real-time search algorithms try to find a suboptimal solution more quickly than traditional algorithms to meet real-time constraints. In this work, a new multi-agent real-time search algorithm is developed and its effectiveness is illustrated on a sample domain, namely maze problems. Searching agents can see their environment with a specified visual depth and hence can partially observe their environment. An agent makes use of its partial observation to select a next move, instead of using only one-move-ahead information. Furthermore agents cooperate through a marking mechanism to be able to search different parts of the search space. When an agent selects its next move, it marks its direction of move before executing the move. When another agent comes to this position, it sees this mark and, if possible, moves in a different direction than the previously selected direction. In this way, marking helps agents coordinate their moves with other agents. Although coordination brings an overhead, from experiments we observe that this mechanism is effective in both search time and solution length in maze problems.     

垂直搜索引擎中分词技术的算法研究

为了提高垂直搜索引擎的检索效率,介绍了垂直搜索引擎中的分词技术。文中主要通过研究最大长度匹配算法,提出了改进后的最大长度匹配算法以提高检索效率。改进后的算法显示,分词效果得到了一定的提升,体现了相对于普通最大长度匹配算法的优势。且通过将改进后的方法与普通最大长度匹配算法相比较可知,改进后的算法提高了搜索的正确率,提升了检索的效率,是一种对最大长度匹配算法的有效改进,由此也体现了搜索引擎中算法合理设计可以提升搜索性能。     

面向混合属性数据集的双重聚类方法

面对复杂信息环境下的数据预处理需求,提出了一种可以处理混合属性数据集的双重聚类方法。这种双重聚类方法由双重近邻无向图的构造算法或其改进算法,基于分离集合并的双重近邻图聚类算法、基于宽度优先搜索的双重近邻图聚类算法、或基于深度优先搜索的双重近邻图聚类算法来实现。通过人工数据集和UCI标准数据集的仿真实验,可以验证,尽管这三个聚类算法所采用的搜索策略不同,但最终的结果是一致的。仿真实验结果还表明,对于一些具有明显聚类分布结构且无近邻噪声干扰的数据集,该方法经常能取得比K-means算法和AP算法更好的聚类精度,从而说明这种双重聚类方法具有一定的有效性。为进一步推广并在实际中发掘出该方法的应用价值,最后给出了一点较有价值的研究展望。     

基于粗糙集理论的增量式规则获取

基于粗糙集理论提出了一种新的规则提取算法：基于粗糙集和搜索树的规则提取算法。该算法是以现有规则集中的信息为启发信息,通过对解空间进行宽度优先启发式搜索,产生新规则。以该算法为基础,产生关于新增对象的规则,并对现有规则进行更新。     

An Empirical Comparison of Search Approaches for Moving Agents

This study empirically compares existing search approaches used for path planning of moving agents, namely, incremental and real‐time search approaches. The comparisons are performed in both stationary and moving target search problems separately. In each problem domain, well‐known representatives of both approaches are evaluated in partially observable environments where the agent senses a limited area based on its sensor range. In addition to the available algorithms, we propose two algorithms to be used in each problem. The simulations conducted on random grid and maze structures show that the algorithms behave differently and have advantages over each other especially as the sensor range varies. Therefore, the proposed study enables the agent to determine the most appropriate algorithm depending on its priorities and sensor range.     

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

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

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

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