排序方式: 共有13条查询结果,搜索用时 342 毫秒
1.
根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列。在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升。 相似文献
2.
3.
TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent Dijkstra为核心算法构建索引,存在两个不足:大量的昂贵的出堆操作拖慢了建立索引的效率以及所求得的路径具有较多的换乘次数。针对这两个不足,提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上做查询,提高效率。TAIL并不是基于图结构,而是以旅程为单位存储公交数据。在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点。为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作,也保留了旅程的完整性。在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少。 相似文献
4.
5.
求解最短路径是图研究中的一个经典问题。目前大多数相关研究都假设图中每条边只有一种权值。然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短。当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用。文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解。实验表明,本方法适用于长路径查询。与单向搜索相比,该方法有较高的运行效率。与基于Dijkstra算法的贪心算法相比,该方法有较高的准确率。 相似文献
6.
7.
私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询:给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL(approximate cost constrained time labelling).ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O(|V|·△max·|E|·(log|E|+△max)),其中,|V|表示顶点数,|E|表示边数,△max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素. 相似文献
8.
分析了通用的演示系统缺少互动性和美观性的现状,提出了基于XNA游戏平台的演示系统。该演示系统使用了状态机机制来实现区分阶段,实现游戏平台内的桌面逻辑块,又为页面设计了常用的页面元素及其简单动画,然后内置了40种页面过渡效果,最后实现了一个系统外的内容录入和结构编排系统,再在演示系统内设计了一个控制台,实现页面微调。实践表明,该系统具有一定的通用性和灵活性,可用于多数场合的演示。 相似文献
9.
10.