3第三章搜索策略

基于人工智能的路径查找优化算法【精品毕业设计】(完整版)

毕业设计[论文] 题目：基于人工智能的路径查找优化算法 学生姓名： Weston 学号：090171021XXX 学部（系）：信息科学与技术学部 专业年级：计算机应用技术 指导教师：XXX 职称或学位： XX 2012 年 5 月 18 日

目录 摘要............................................................... II ABSTRACT ........................................................... III KEY WORDS .......................................................... III 1.前言 (1) 2.概述 (2) 2.1遗传算法优缺点 (2) 2.2遗传算法应用领域 (3) 2.3遗传算法基本流程 (3) 3.传统遗传算法解决旅行商问题 (5) 3.1常用概念 (5) 3.2基本过程 (5) 3.3关键步骤 (5) 3.4总结 (8) 4.改进后的遗传算法 (9) 4.1编码、设计遗传算子 (9) 4.2种群初始化 (9) 4.3评价 (10) 4.4选择复制 (10) 4.5交叉 (11) 4.6变异 (12) 4.7终结 (13) 5.系统设计与实现 (14) 5.1系统设计 (14) 5.2系统实现 (17) 5.3结果分析 (20) 6.总结 (21) 参考文献 (22) 致谢 (23)

基于人工智能的路径查找优化算法 摘要 旅行商是一个古老且有趣的问题它可以描述为：给定n个城市以及它们之间的距离（城市i到城市j的距离），求解从其中一个城市出发对每个城市访问，且仅访问一d ij 次，最后回到出发的城市，应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。 旅行商问题已被证明是属优化组合领域的NP难题，而且在现实中的许多问题都可以转化为旅行商问题来加以解决。解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。 解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时，其他一些启发式的搜索算法则依赖于特定的问题域，缺乏通用性，相比较而言遗传算法是一种通用性很好的全局搜索算法。 遗传算法GA( genetic algorithm) 最早由美国密歇根大学的John Holland 提出。具有自组织、自适应、自学习和群体进化功能有很强的解决问题的能，在许多领域都得到了应用。 遗传算法以其广泛的适应性渗透到研究与工程的各个领域，已有专门的遗传算法国际会议，每两年召开一次，如今已开了数次，发表了数千篇论文，对其基本的理论、方法和技巧做了充分的研究。今天，遗传算法的研究已成为国际学术界跨学科的热门话题之一。 关键词：人工智能；遗传算法；TSP；旅行商问题

不确定条件下的交通网络最优路径搜索算法及其应用

不确定条件下的交通网络最优路径搜索算法及其应用 最优路径搜索问题是算法研究领域长期关注的问题,其在交通、通信以及地理信息系统中有着广泛的应用。从不确定性的角度研究最优路径搜索问题,是近年来新的热点研究问题。 本文基于考虑交通网络中通行时间相关性的最优路径搜索算法,重点探讨了在不确定条件下,如何考虑车辆在路口的等待时间模型、不同路网中的电动汽车能耗模型、交通配流模型以及基于车牌识别技术的OD(Origin-Destination)均值和协方差的估计模型。具体如下:第一章绪论部分主要介绍了不确定条件下的可靠路径搜索问题、电动汽车能源消耗问题、交通配流问题以及OD均值和协方差估计问题的研究背景和意义,并且探讨了不确定条件下的可靠路径搜索算法的一些研究历史与现状,论述了部分经典的路径搜索算法和交通配流模型。 第二章研究了在不确定条件下,同时考虑路段的随机通行时间、路段通行时间相关性和路口等待时间三个因素的可靠路径搜索问题,现有的研究中很少有算法能够同时考虑这三个因素。由于本章中所提出的新的有效通行时间模型具有不可加性,因此传统的路径搜索算法并不适用。 据此,本章提出了一个新的基于不等式放缩技巧的算法,通过给出有效通行时间模型的上界和下界,并以最小的有效通行时间的上界为阈值,通过阈值,可以直接判断某条路径是否有可能成为最优的可靠路径,节约了计算量。给出的数值结果表明,若忽略不同路段之间的通行时间相关性或信号交叉口的随机延迟会导致寻找可靠最短路径的结果存在偏差。 最后,我们证明了所得到的可靠最短路径可以避免由于网络不确定性和信号交叉口延迟而导致的意外延迟,从而为通行者提供更好的行程规划支持。第三章

交通网络有效路径的一种搜索算法

交通网络有效路径的一种搜索算法 摘要：基于图论中Dijkstra算法的思想，建立了一种搜索交通网络OD对间所有有效路径的方法。当不考虑有效路径的限制时，该方法可按路径长度递增的顺序依次搜索出有向图中的所有通路。针对具有24个节点、77条路段的某交通网络，我们进行了大量仿真，结果表明该算法是十分有效的。本文提出的方法可用于简化交通网络OD估计中监测点定位的算法。 关键词：OD矩阵；路径搜索；仿真 A Search Algorithm for Effective Paths in Traffic Networks LIN Yong, CAI YuanLi, HUANG YongXuan ( School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049,China ) Abstract:Based on the Dijkstra methodology in graph theory, an algorithm to search all the effective paths between OD pairs in traffic networks is proposed. This algorithm is also generalized to determine all the paths in a directional graph in the ascending order of paths length. A lot of simulations have been conducted on a traffic network with 24 nodes and 77 links. It is shown that the search algorithm is effective and efficient. The algorithm can be applied to simplify the surveillance points positioning in the OD matrix estimate of traffic networks. Keywords: OD matrix; path search; simulation 1 引言 OD矩阵，或称OD表，是交通网络中所有起点（Origin）与终点（Destination）之间出行交换数量的表格，其中的每个元素反映了特定OD对间在一定时间段内的出行量。它是交通网络规划和交通管理的重要依据。历史上，OD矩阵是作大量的交通调查得到的，代价十分高昂。1978年，Vdnzuylon 和Wllumsen通过交通网络中一定数量的路段流量观测值来估计OD矩阵，使OD估计的研究有了一个突破口[1]。之后，经过国内外学者的不断努力，建立了各种OD估计模型[2]。然而，几乎所有的OD估计模型均未讨论如何设置交通量观测点，使得任意OD 对间的出行量均能被某个观测点检测到。文献[3~5]对此进行了专门研究，提出观测点设置应当满足的4个规则，并建立0-1整数规划模型进行求解。但上述方法需已知各OD 对间的有效出行路径。文献[6]为避免列举这些有效路径，根据检测点应当满足的规则，建立了关于其分布的非线性规划模型。在已知极点间转移概率的前提下，将检测点的分布问题描述成一个平均报酬Markov决策过程，并通过转化为一个等价的整数线性规划问题求解。为此，本文运用仿真的思想来搜索OD对间的所有有效路径，以简化上述的OD量观测点定位算法。 2 有效路径的搜索算法 2.1 有效路段与有效路径[7] 有效路段) ,(j i定义为路段终点j比路段起点i更靠近出行目的地s的路段，即沿该路段前进能更接近出行终点。因此，有效路段的判别条件为：对于路段) ,(j i，若 ) ,( ) , ( mi n mi n s i L s j L ，则为有效路段。

有关路径搜索的一个算法

有关路径搜索的一个算法 由各个直线组成的路网，求一点到另一点的所有路径： FindRateWay.h文件代码如下： #include #include #include #include "GELNSG3D.h" typedef std::vector vecLineSeg; //死胡同点记录 struct DeadList { AcGePoint3d ptOri; //参照点 AcGePoint3dArray ptDeadAry; //死胡同点（即从参照点出发的不能走的下一点） }; typedef std::vector vecDeadPt; class CFindRateWay { public: CFindRateWay(std::list& lstRate,AcGePoint3d ptStart,AcGePoint3d ptEnd); virtual ~CFindRateWay(); //寻找所有路径（排除回路），没找到返回FALSE BOOL FindWay(std::vector& vecWay); private: //检查路径点是否可继续向下走，如果可走则返回TRUE并返回一个可走的邻接点ptNext BOOL IsValid(AcGePoint3d pt, std::stack& staRatePt,std::vector& vecWay, IN vecDeadPt& vecDead, OUT AcGePoint3d& ptNext); //查找某点的所有邻接点 void FindPtNear(AcGePoint3d pt,AcGePoint3dArray& PtAry); //从栈中寻找指定点，找到返回TRUE BOOL FindPtFromStack(AcGePoint3d pt, IN std::stack& staPt); //通过栈中轨迹记录到路径组中

地图中最短路径的搜索算法研究综述

地图中最短路径的搜索算法研究 学生:李小坤导师：董峦 摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。 关键词:最短路径算法；广度优先算法；深度优先算法；A*算法； The shortest path of map's search algorithm Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic. Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm; 前言： 最短路径问题是地理信息系统（GIS）网络分析的重要内容之一，而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法，广度优先算法和A*算法，对一具体问题进行讨论和分析，比较三种算的的优缺点。 在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:[1] (1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。 (2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。 (3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。 地图中最短路径的搜索算法: 1、广度优先算法 广度优先算法(Breadth-First-Search)，又称作宽度优先搜索，或横向优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽