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

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

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

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

由“汽车问题”浅谈深度优先搜索的对象与策略

本文通过对“汽车问题”的分析,认为对深度搜索题目,一个好的搜索对象和策略是十分重要的,并且根据深度搜索消耗时间公式提出了比较搜索对象和策略的标准:优化剪枝与操作系数。同时,通过对深度搜索消耗时间公式的分析也发现,为了更好的解决问题达到目的,仅仅在微观上进行变动更新是不够的,还要首先为这个目的去创造良好的宏观条件。     

基于宽度优先搜索的路径生成算法

宽度优先搜索和深度优先搜索是图论中常用的两种搜索算法.两者各有优势,但深度优先搜索算法的效率在低连通度图中会大大降低,这时更适合采用宽度优先搜索算法.本文提出了一种基于宽度优先搜索的路径生成算法,具有较好的时间复杂性和空间复杂性.     

迷宫最短路径问题新算法

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

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

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

基于深度优先搜索的Web服务合成算法

本文通过提取Web服务的语义信息,研究了语义Web服务合成问题。Web服务合成的关键是对候选Web服务的输入输出数据关系进行建模,以及有效地利用这些已有的数据依赖关系实现服务合成请求。通过构建Web服务的依赖图,提出了一种基于图论中深度优先搜索的Web服务合成算法,以获取满足特定要求的Web服务。     

DNA计算机中图的深度优先搜索遍历算法

提出DNA计算机中图数据结构的一种设计方法,给出具体的存储结构以及深度优先搜索遍历的算法。该算法实现了在DNA计算机下图元素的遍历。为证明其可行性,给出一个具体的算法实例,描述了DNA计算机上的运行机制。依据分子生物学的理论,证明算法是有效且可行的。     

图的深度优先遍历算法及运用

简要介绍图的深度优先遍历算法,通过对由易到难、层次不一的题目进行分析求解,深化对该算法的理解,理清算法学习的思路,并试着展示数据结构学习过程中的一种模式。     

基于化合物库测试的gSpan算法

gSpan算法是一种基于频繁图的数据挖掘算法。该算法基于无候选人产生的频繁子图，采用深度优先搜索策略挖掘频繁连接子图。由于其设计结构具有连续性以及无候选人产生，算法的性能得以提高，在执行速度上可以达到前人算法如FSG算法的15～100倍。基于化合物库Chemical_340测试发现，该算法能够以卓越性能有效挖掘频繁子图。该算法可以应用在搜索具有相同子结构的化合物研究中，对相关领域研究发展具有重要意义。     

无向连通图中求约束条件下近似最长路算法

在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路。该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路。该算法在绣花打版软件的应用中取得了良好的效果。     

深度优先搜索求解网络单源最短路径算法

提出在深度优先搜索过程中采用标记当前搜索位置离起始点最短距离方法,有效地实现了求解复杂网络的单源最短路径问题.通过对运算效率的分析,表明该算法通过优化改进可以达到理想的运算效率;模拟了不同规模的含障碍网络(182～13770个节点),其单源最短路径的求解运算平均效率为O(kV)(其中k≤18,V为路节点数),等同于用改进后的最优Djkstra算法求解效率O(mlogn).报告了一个具有现实应用价值和更具潜在研究价值的深度优先搜索智能算法.     

基于有向图的进路搜索算法研究与设计

进路搜索是铁路车站计算机联锁系统的基本功能,其运行效率及所得目标进路的安全性对于保证行车安全意义重大。本文通过对铁路车站站场图与有向图的相似性进行研究,建立其网络拓扑结构与节点模型,结合深度优先遍历算法和搜索约束条件,提出一种适用于铁路车站实际情况的进路搜索算法,并给出了完整的描述。     

公交车网络的最短路径算法及实现

最短路径问题是图论研究中的一个经典算法问题．旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性，公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径，即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法，再举例详细说明其过程，最后指出此算法的扩充用途。     

迷宫算法的改进与动态实现

本文在对广度优先迷宫搜索算法和深度优先迷宫搜索算法进行了仔细比较与探讨之后,提出一种新的算法:目标优先法。即每次向下一个位置搜索时,按当前位置的各方向靠近目标点的距离去选择方向。使得搜索过程在较短时间内能够快速从入口向出口目标逼近。然后从数据输入输出,程序设计等方面讲述了这种带优先级的算法的实现。并将此算法用Java语言在JDK上实现其搜索过程的画面,模拟其算法实现过程。最后,将此算法与传统的广度优先和深度优先算法优缺点进行了综合比较。     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems

Effective path finding has been identified as an important requirement for dynamic route guidance in Intelligent Transportation Systems (ITS). Path finding is most efficient if the all-pair (shortest) paths are precomputed because path search requires only simple lookups of the precomputed path views. Such an approach however incurs path view maintenance (computation and update) and storage costs which can be unrealistically high for large ITS networks. To lower these costs, we propose a Hierarchical Path View Model (HPVM) that partitions an ITS road map, and then creates a hierarchical structure based on the road type classification. HPVM includes a map partition algorithm for creating the hierarchy, path view maintenance algorithms, and a heuristic hierarchical path finding algorithm that searches paths by traversing the hierarchy. HPVM captures the dynamicity of traffic change patterns better than the ITS path finding systems that use the hierarchicalA * approach because: (1) during path search, HPVM traverses the hierarchy by dynamically selecting the connection points between two levels based on up-to-date traffic, and (2) HPVM can reroute the high-speed road traffic through local streets if needed. In this paper, we also present experimental results used to benchmark HPVM and to compare HPVM with alternative ITS path finding approaches, using both synthetic and real ITS maps that include a large Detroit map (> 28,000 nodes). The results show that the HPVM incurs much lower costs in path view maintenance and storage than the non-hierarchical path precomputation approach, and is more efficient in path search than the traditional ITS path finding using A* or hierarchical A* algorithms.     

多智能体路径规划综述

多智能体路径规划（multi-agent path finding,MAPF）是为多个智能体规划路径的问题,关键约束是多个智能体同时沿着规划路径行进而不会发生冲突。MAPF在物流、军事、安防等领域有着大量应用。对国内外关于MAPF的主要研究成果进行系统整理和分类,按照规划方式不同,MAPF算法分为集中式规划算法和分布式执行算法。集中式规划算法是最经典和最常用的MAPF算法,主要分为基于[A*]搜索、基于冲突搜索、基于代价增长树和基于规约四种算法。分布式执行算法是人工智能领域兴起的基于强化学习的MAPF算法,按照改进技术不同,分布式执行算法分为专家演示型、改进通信型和任务分解型三种算法。基于上述分类,比较MAPF各种算法的特点和适用性,分析现有算法的优点和不足,指出现有算法面临的挑战并对未来工作进行了展望。     

一种求解最优路径的改进遗传算法

在应用遗传算法进行路径规划时,本文针对遗传算法的＂收敛盲目性＂和＂收敛速度慢＂两个难题,结合模拟退火算法对适应度函数进行改进,结合禁忌搜索对变异算子进行改进,并且在进化过程中使用改进的自适应方法调节交叉概率与变异概率。算法的分析和测试表明,本文算法的改进是有效的。     

基于分块路径缓存的在线路径搜索算法

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法。对路网重采样得到路网密集度图像,提出路网分块算法ISODATA。根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法。实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s以内,降低网络地图服务路径计算服务器负荷。