给你看一篇文献：
地图中最短路径的搜索算法研究
学生:李小坤 导师：董峦
摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(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最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
广度优先搜索算法伪代码如下：[2-3]
BFS(v)//广度优先搜索G，从顶点v开始执行
//所有已搜索的顶点i都标记为Visited(i)=1
//Visited的初始分量值全为0
Visited(v)=1;
Q=[];//将Q初始化为只含有一个元素v的队列
while Q not null do
u=DelHead(Q);
for 邻接于u的所有顶点w do
if Visited(w)=0 then
AddQ(w,Q); //将w放于队列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
这里调用了两个函数：AddQ(w,Q)是将w放于队列Q之尾；DelHead(Q)是从队列Q取第一个顶点，并将其从Q中删除。重复DelHead(Q)过程，直到队列Q空为止。
完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
时间复杂度：最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为,其中|V|是节点的数目，而 |E| 是图中边的数目。
空间复杂度：因为所有节点都必须被储存，因此BFS的空间复杂度为，其中|V|是节点的数目，而|E|是图中边的数目。另一种说法称BFS的空间复杂度为O(B),其中B是最大分支系数，而M是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。[4-5]
2、深度优先算法
深度优先搜索算法（Depth First Search）英文缩写为DFS，属于一种回溯算法，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能执行为止。
深度优先搜索算法的伪代码如下：[7]
DFS(v) //访问由v到达的所有顶点
Visited(v)=1;
for邻接于v的每个顶点w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低，在数据规模变大时，这种算法就显得力不从心了。[8]关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝，也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高。
3、A算法
1968年的一篇论文，“P E Hart, N J Nilsson, and B Raphael A formal basis for the heuristic determination of minimum cost paths in graphs IEEE Trans Syst Sci and Cybernetics, SSC-4(2):100-107, 1968”。[9]从此，一种精巧、高效的算法——A算法问世了，并在相关领域得到了广泛的应用。A 算法其实是在宽度优先搜索的基础上引入了一个估价函数,每次并不是把所有可扩展的结点展开,而是利用估价函数对所有未展开的结点进行估价, 从而找出最应该被展开的结点,将其展开,直到找到目标节点为止。
A算法主要搜索过程伪代码如下：[10]
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表;
while(OPEN!=NULL) //从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
endif
for(当前节点n 的每个子节点X)
算X的估价值;
if(X in OPEN)
if(X的估价值小于OPEN表的估价值)
把n设置为X的父亲;
更新OPEN表中的估价值; //取最小路径的估价值;
endif
endif
if(X inCLOSE)
if( X的估价值小于CLOSE表的估价值)
把n设置为X的父亲;
更新CLOSE表中的估价值;
把X节点放入OPEN //取最小路径的估价值
endif
endif
if(X not inboth)
把n设置为X的父亲;
求X的估价值;
并将X插入OPEN表中; //还没有排序
endif
end for
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
end while(OPEN!=NULL)
保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
A 算法分析：
DFS和BFS在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。而A算法与DFS和BFS这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上。[11]A 算法就是利用对问题的了解和对问题求解过程的了解, 寻求某种有利于问题求解的启发信息, 从而利用这些启发信息去搜索最优路径它不用遍历整个地图, 而是每一步搜索都根据启发函数朝着某个方向搜索当地图很大很复杂时, 它的计算复杂度大大优于D ijks tr a算法, 是一种搜索速度非常快、效率非常高的算法但是, 相应的A算法也有它的缺点启发性信息是人为加入的, 有很大的主观性, 直接取决于 *** 作者的经验, 对于不同的情形要用不同的启发信息和启发函数, 且他们的选取难度比较大,很大程度上找不到最优路径。
总结：
本文描述了最短路径算法的一些步骤，总结了每个算法的一些优缺点，以及算法之间的一些关系。对于BFS还是DFS，它们虽然好用，但由于时间和空间的局限性，以至于它们只能解决规模不大的问题，而最短或最少问题应该选用BFS,遍历和求所有问题时候则应该选用DFS。至于A算法，它是一种启发式搜索算法，也是一种最好优先的算法，它适合于小规模、大规模以及超大规模的问题，但启发式搜索算法具有很大的主观性，它的优劣取决于编程者的经验，以及选用的启发式函数，所以用A算法编写一个优秀的程序，难度相应是比较大的。每种算法都有自己的优缺点，对于不同的问题选择合理的算法，才是最好的方法。
参考文献：
[1]陈圣群,滕忠坚,洪亲,陈清华四种最短路径算法实例分析[J]电脑知识与技术(学术交流),2007(16):1030-1032
[2]刘树林,尹玉妹图的最短路径算法及其在网络中的应用[J]软件导刊,2011(07):51-53
[3]刘文海,徐荣聪几种最短路径的算法及比较[J]福建电脑，2008(02）:9-12
[4]邓春燕两种最短路径算法的比较[J]电脑知识与技术，2008（12）：511-513
[5]王苏男,宋伟,姜文生最短路径算法的比较[J]系统工程与电子技术,1994(05)：43-49
[6]徐凤生,李天志所有最短路径的求解算法[J]计算机工程与科学,2006(12)：83-84
[7]李臣波,刘润涛一种基于Dijkstra的最短路径算法[J]哈尔滨理工大学学报,2008(03)：35-37
[8]徐凤生求最短路径的新算法[J]计算机工程与科学,2006(02)
[9] YanchunShen An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亚松VC++实现基于Dijkstra算法的最短路径[J]科技信息(科学教研),2008(18)：36-37
[11] 杨长保,王开义,马生忠一种最短路径分析优化算法的实现[J] 吉林大学学报(信息科学版),2002(02)：70-74传统汽车的驾驶功能已经远远满足不了大众对智能化的渴望和需求，云计算、大数据分析、人工智能、自动驾驶等技术不断发展，为传统汽车的变革提供了很好的基础。汽车已经越来越智能，它会为你推荐喜欢的歌曲，高效的回复每一封邮件，提前为你避让道路故障、躲避拥堵，在下班的途中推荐你心水很久的美食，寒冷的冬天提前打开家中的暖风一切都是根据用户行为习惯，在车内无缝的和任何一个场景联通，驾驶变的更从容和美好。
搭载了互联网服务的汽车 *** 作系统将是用户连接未来一切可能性的窗口，未来地球的每一寸土地都会被计算能力所覆盖，而智能汽车正是一个有无穷想象力的通往未来的入口！在数字化时代下，智能汽车的 *** 作系统该具备哪些特质呢？
未来在人工智能时代下，智能汽车的 *** 作不再是单一的指向性功能，不仅需要满足用户的基本需求，更重要的是在用户还没有充分表达需求的基础上为用户先一步考虑问题，知道用户下一步会做什么，提前应对。基于深度学习用户习惯、研究用户的行为、大量收集用户范本并做深度分析，为每一个用户深度定制需求，提出个性化的解决方案，让汽车的用户体验不再千篇一律。
汽车在特殊的驾驶环境下通过深度学习能力为用户带来场景化解决方案，将汽车变为贴身的私人管家，通过识别用户身份，它知道你今天送孩子上学的途中会喝一杯美式咖啡，去公司的路上有一个重要的视频会议，晚上要和家人聚餐等，汽车会根据你的需求自动同步日历信息，安排最优的导航路线，提前预定一杯咖啡，推荐一家适合家庭聚会的餐厅
汽车复杂的驾驶场景决定了汽车的 *** 作系统有别于其他移动设备，它对安全性和高效反馈有着极高的要求。用户与系统在交互中，所有的 *** 作都意味着驾驶员的视线离开轨道，系统交互的重要性就是要帮助驾驶者能够稳定的行驶而不发生交通问题，这对人与车的交互方式和界面设计产生了极高的要求，用触摸、手势、语音还是眼球追踪，都是设计赋予安全驾驶的意义。语言和肢体是人类最自然的交流方式，用最直接的身体姿态与汽车沟通，深度研发汽车的自然语言能力，并识别面部表情和肢体动态，将人类最舒适的交流方式转化为 *** 作指令。
语音识别涉及到生活的方方面面，如智能家居、家电、运动、医疗、生活服务等，目前国内外都在深度研究AI下的语音人机交互，国外苹果siri、亚马逊Alexa、谷歌Assistent，国内腾讯、阿里等都在研发语音交互技术。机器会学习人类的说话语调、情感表达，通过大数据将搜索结果用自然的语言输出给用户。自然的语音交互大大降低了人车交互的学习成本，让冰冷的汽车变成最懂你的朋友，通过交流不仅可以完成指令，还会识别语义、语调感知用户情绪，做到个性化服务，将人和汽车的交互方式带入到新的数字化时代。
智能化时代，用户对汽车的需求转变为万物互联、智慧出行，汽车不仅可以满足功能需求，更是一个连接万物的入口，通过车实现家车场景下互联互通。坐在家中可以通过智能音箱控制车辆，反之在车内也可以关闭窗帘、打开暖风等智能控制家居；还可以通过手机、可穿戴设备对汽车完成解锁、授权、分享，不再需要钥匙解锁汽车，与朋友共享汽车只需远程授权，还有快递到车服务等；以及车与车之间，可以无缝信息共享、实时社交，车主与车主之间建立兴趣小组，共享POI，道路救援等；车与各终端互相联动、资源共享，实现人、车、生活的万物互联。
通过人工智能，在以车为中心的物联网还将有更多的想象空间，汽车会学习更多人类的行为习惯，更智能、自然的连接万物，更多维度的远程控制。未来的汽车，会让生活变得更简单，万物互联的魅力会让用户腾出更多的时间享受驾驶乐趣。
智能汽车的出现会让用户有更高的驾驶愉悦感，汽车会充当你的司机，而系统就变成了你的贴心管家，优秀的系统界面设计不仅可以提升汽车的品牌价值，创造全新的用户体验，还可以让汽车成为生活的一部分，它学习人类的生活习惯和环境，可以赋予汽车新的灵魂，让汽车品牌变的与众不同。
汽车界面（HMI）设计是由多个设计部件组合而成，包括尺寸、分辨率、文字、颜色、图标、控件、用户体验等，外部因素对界面设计的影响也至关重要，包括屏幕摆放方式、位置、角度、光照等。只有充分考量外部因素，合理有效的组合设计零部件，才能确保内容优先、良好的易读性、精准点击、快速响应以及优秀的用户体验。以下是通用的汽车界面设计原则，以标准化的数据加上创新的设计元素，以确保驾驶安全性的同时发挥与众不同的视觉感受。
大屏 *** 作系统越来越受到车企青睐，更多的功能被聚合在 *** 作系统上，位于驾驶员右侧的大屏在驾驶环境下，手指可触及的区域十分有限。对于设计大屏系统，要充分考虑用户 *** 作舒适度和最优 *** 作范围（如下图所示），本文以常见的屏幕比例（16：9）来分析屏幕交互热区的范围。靠近驾驶员的屏幕右下方是最容易交互到的区域，适合可交互可点击的功能性内容、需要快捷 *** 作的button、盲 *** 作就可以完成的交互，都可以放置在右及右下方区域（绿色区域）；屏幕越靠上，意味着手臂悬停的时间要更长，要完成选择或点击类的 *** 作的时间相对长，适合不常进行互动和交互的内容，优先考虑显示类信息（蓝色区域）；屏幕右上角的区域基本是 *** 作盲区，在此位置放置显示类状态信息更为适宜，避免将重要的 *** 作button放置在交互盲区（红色区域）。以特斯拉为例，将使用频率最高的空调面板常驻在底部最容易触及到的区域，可以快速调节与温度相关的功能；顶部交互盲区是状态栏一类显示信息，不经常点击的功能则安排在右上角区域；中间区域是用户点击屏幕的舒适区，特斯拉将中间区域划分为等分的两部分，上下半屏各显示不同模块，在设计布局上将更频繁 *** 作的button放在屏幕靠左侧位置更易交互。（如下如所示）
车机屏幕的摆放方式决定了在白天强光下是否可以清晰的看到屏幕上的文字和内容，在夜间屏幕是否过亮导致刺眼，这些工作在设计之初进行充分调研是非常有必要的。如果光照很强，在设计上就要避免用和背景相同色系的颜色，适当提高颜色对比度，通过不断调整色彩和布局提高界面的易读性；相反在夜间，又要避免使用纯度太高的颜色，文字的颜色也要考虑不使用纯白或者纯黑，适当的降低彩色明度有利于夜间行车。所以在界面设计的过程中需要设计师在充足光照的白天和照明微弱的夜间多次测试屏幕的显示效果，提高界面的易读性，必要的时候可以考虑通过增加主题换肤的模式缓解矛盾。如下如示例，在没有硬件遮挡的强光照下，屏幕的显示效果是非常差的，基本很难看清屏幕内容，这就需要设计师反复测试实现最佳的显示效果。
汽车界面设计与手机app在设计上有本质的区别，app的设计基本上以信息流为主，在设计布局上也基本上以列表、九宫格、瀑布流等形式表现。但是汽车界面主要以功能 *** 作类为主，除了设置、信息展示需要用到列表等形式展现外，大部分的功能都需要快速完成 *** 作，在内容的布局上相对自由，虽然没有特定的布局样式，但因为汽车的使用场景的特殊性，在页面布局上要更考虑到以下几个原则：
“内容优先”原则。 要选择更直观、更易读的设计样式去表达功能，避免使用识别性差的图表突出核心内容。可以从车内提取设计元素强调功能的展现，例如汽车控制功能，可以提炼“座椅”“方向盘”等实物细节，不仅有效的表达产品功能，还可更直观的看到交互反馈。
”少即是多“原则。 在界面布局上尽量不要使用与功能无关的设计元素，有时候为了刻意强调界面的炫酷的科技感，在界面中加了容易导致信息混淆的“额外”设计，很容易导致界面承载信息过多而失去重心。合理的运用文字大小、颜色来突出界面层次，避免过分使用过重的装饰元素。
“减少层级”原则。 尽管汽车系统类功能和手机趋同，但是避免直接套用手机的布局样式，要牢记在汽车高速驾驶的环境下是没有办法将注意力集中在“找”这个行为上，列表式的布局样式不可完全复制，为了用户可以快速定位完成响应，要尽可能的减少交互层级。避免重点 *** 作“藏”在第二甚至第三层级，把主交互功能放在一级页面，更多 *** 作可二级页面完成，减少用户一直点击“下一页”，结束任务后再一直“back”返回一级导航。
汽车在高速行驶的环境下，如何判断一个界面的好坏，最直观的就是测量用户在点击完成一个事件所需要的时间，时间越短，表明界面的可视化和有效点击率越高，界面的响应速度越快。用户平均单个手指点击区域为10~14mm之间，以1080p分辨率为例，单个手指触摸屏幕的有效分辨率为45px~50px之间，这仅为手指在触摸屏幕时的触摸范围，为了使高速驾驶环境下可以精准的点击到目标，对单个手指点击区域的范围要增加padding值，目标区域相对应向外扩大一倍左右，至少单指触摸区域增至80~100px为宜。这就对智能汽车界面的icon有了设计要求，在用户需要点击icon完成交互任务时，icon的可交互范围要保持在100100px左右，确保用户在触发icon边缘时也同样可以完成响应，大大降低了误 *** 作率。
在界面设计中文字包括：字号、字色、字重、字体、字间距等，有些公司有专门的branding部门设计个性化字体，好的字体设计会结合设计风格和品牌定位，对界面设计是锦上添花。但大部分互联网车机还是使用常见的免费字库，中文常用“思源黑体”，英文则使用“roboto”居多。准确使用字号和字色，有利于提高界面的易读性，增加界面的层次重心。在手机等移动终端的设计中有个误区，认为文字越小越精致，越大越笨拙，这个说法是片面不准确的。尤其在汽车高速驾驶的环境下，文字大小每增加2px，都可能意味着提高界面易读性，降低驾驶风险。以10801920分辨率的界面为例，最小文字建议不低于30px，否则在屏幕上可识别率很低，增加误读的概率。界面中需要着重突出的内容，可以灵活使用字号字色表达，增加主次关系，具体可参考排版设计。在界面设计中，正文一般会使用“regular”这种常规字重，需要额外强调的文案可以酌情使用bold，但慎用，中文的粗体会导致文字糊在一起，不利于阅读。适当的字间距对界面而言是画龙点睛，适当的增加字间距，尤其是英文，可以使界面变得更柔和，更精致，设计师们不妨试试。
每个品牌都会有自己的品牌色，这个颜色和企业形象、产品特征有关，是系统设计的关键色。恰当的运用品牌色能让用户产生强记忆力，一看到这个颜色优先想到该品牌及产品，有利于品牌的推广。例如微信绿、阿里橘、京东红等等，每个品牌色都代表着公司的企业文化和产品气质，品牌色往往应用在系统焦点和核心位置。同理智能车联网的界面设计也需要提炼属于该品牌形象的颜色，将被应用在系统logo、高亮色及核心内容、企业VI等，是家族化特征的延续。其次颜色有信息传达的特质，红色代表警示、绿色代表正常，特定属性的颜色要用到特定的位置。有国际化背景的车联网公司还应该注意销售国家对颜色的偏好和忌讳，在系统设计中要着重注意颜色的使用。
建立详细的设计规范体系，是构成界面完成性重要的步骤之一。包括文字、颜色、控件、对话框、列表、通用icon、布局等，一是规范设计师应用到每一个模块每一个细节，提升一致性设计体验；二是工程师编写控件库，所有模块可以规范调用控件，降低反对沟通成本。在任务量大，项目时间紧的情况下，有一套完整的控件体系对于设计一个庞大的系统而言，可以减少大量的工作时间，避免每个设计师重复用力，更快更准确的制定规范是一个设计团队的重要一环，也是鉴别一个设计团队是否专业的判断依据。当然，建立设计规范也不是越早越好，还需要设计内部反复修改和测试后再定义成体系。通常在确定设计风格后，根据设计经验先拟定文字、颜色等比较基础的规范，上机实测是否有利于点击和观看，达到设计内部统一；随着设计的深入再完善控件、列表等细节规范；后续将控件汇总成一个可编辑的文档，注明版本号、修改时间、修改人、目录等，方便后续查找和修订。创建优秀的控件体系，让开发和设计共享一套规范系统，让设计师实现自我价值的转换，更专注在用户体验和产品创新上，对公司来说也是提升品牌价值的宝贵财富。
在人工智能的大背景下，所有车企都希望通过AI、大数据、云计算、物联网等技术让车变得更聪明，更贴近用户，打造完整的车联网体系，让车成为生活工作场景的延展。未来的汽车战场，除了性能比拼，更多的将是用户体验的比拼！
本文是个人对互联网车机产品的理解和认识，欢迎大家一起讨论研究！(ps微信号：smilesh1030）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）