常用的数据结构和算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,深入,Java,编程,专业教程,理论讲解部分,Ver3.1,1,第,029,课 算法及数据结构,概述：,A*,算法介绍,重点：,难点：,A*,算法,A*,算法,2,8 A*,算法,第,029,课 算法及数据结构,A*,算法是当今比较流行的一种寻路算法,.,它是解决在一个比较复杂的地图中寻找出最短路径的问题,.,例如在这样一副地图中,从绿色的方块移动 到红色方块的最短路径如何求得,.,其中蓝色为不可通行区域,.,3,第,029,课 算法及数据结构,节点,:,这是一副简化了的地图,已经被划分为一个一个的方格,.,这里我们把这些方格称之为节点,.,8.1,基本概念,开启列表,:,开启列表中保存所有可能经过的节点信息,并且这里的节点需要保存其父节点,.,父节点,:,表示当前节点的前继节点,.,8 A*,算法,4,第,029,课 算法及数据结构,关闭列表,:,关闭列表中保存不可以到达的节点,.,路径评分,F:,F = G + H,H =,从网格上那个方格移动到终点,B,的预估移动耗费。,G =,从起点,A,，沿着产生的路径，移动到网格上指定方格的移动耗费。,8.1,基本概念,8 A*,算法,5,第,029,课 算法及数据结构,移动耗费,G:,我们令水平或者垂直移动的耗费为,10,，对角线方向耗费为,14,。,估算,H:,H,值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以,10,。,8.1,基本概念,8 A*,算法,6,第,029,课 算法及数据结构,8.2,搜索过程,首先将起始节点加入开启列表,.,然后,将这个节点周围的节点都加入开启列表,除关闭列表中节点,.,并且将其父节点置为起始点,.,这是将起始点从开启列表中删除,并加入关闭列表,.,8 A*,算法,7,第,029,课 算法及数据结构,计算开启列表中的所有节点的路径评分,.,74,60,74,60,54,60,54,选取评分最低的节点,从开启列表中删除,加入关闭列表,.,我们命名它为当前点,.,40,8.2,搜索过程,8 A*,算法,8,第,029,课 算法及数据结构,将当前点周围的可行节点加入开启列表中,.,74,60,74,60,54,60,54,40,这里分为两种情况,要加入节点没有在开启列表中或者已经在开启列表中,.,若不再开启列表中则将当前点作为其父结点并计算,G,值,.,若已在开启列表中则比较以当前点作为父节点的,G,值与原,G,值,若当前,G,值小则改变其父结点为当前点并修改,G,值,否则什么也不作,.,8.2,搜索过程,8 A*,算法,9,第,029,课 算法及数据结构,此处在,40,点下方的点,原,F,值为,54.,以当前点为父节点计算,F = 20+40 = 60.,所以什么也不作,.,其它节点类似,.,74,60,74,60,54,60,54,40,这时我们重新搜索开启列表,寻找,F,值最小的节点,.,这里有,2,个,54,的节点,.,我们选择左下放的继续,.,此时,该节点作为当前点,.,8.2,搜索过程,8 A*,算法,10,第,029,课 算法及数据结构,88,74,将当前节点相邻的可行节点加入开启列表,.,并将其父节点设置为当前点计算,F,值,74,60,74,60,54,60,54,40,再次搜索开启列表寻找,F,值最低节点,然后重复上述步骤,.,8.2,搜索过程,8 A*,算法,11,74,88,74,第,029,课 算法及数据结构,94,68,68,88,74,102,直到将寻找到目标节点,.,74,60,74,60,54,60,54,40,74,94,80,74,82,82,74,8.2,搜索过程,8 A*,算法,12,第,029,课 算法及数据结构,其最终路径按照目标点的父结点以次寻找其后节点的父节点直到起始点,.,74,88,74,94,68,68,88,74,102,74,60,74,60,54,60,54,40,74,94,80,74,82,82,74,8.2,搜索过程,8 A*,算法,13,第,029,课 算法及数据结构,8.3,算法描述,1.,将起始节点添加到开启列表,.,2.,重复如下内容,:,a.,寻找开启列表中,F,值最低的节点,.,称其当前节点,.,b.,把当前节点从开启列表中删除并加入关闭列表,.,c.,对相邻可行的节点若不在开启列表中,则设置当前点为父结点并计算其,F,值加入开启列表,;,若在开启列表中则比较若当前,F,值小则改变其父节点并更新,F,值,否则不作任何事,.,d.,终止,.,找到目标或者开启列表已经为空仍旧没有找到列表,.,前者查找成功,后者说明路径并不存在,.,8 A*,算法,14,第,029,课 算法及数据结构,3.,保存路径,.,从目标格开始，沿着每一格的父节点移动直到回到起始格。,8.3,算法描述,8 A*,算法,15,小结：,A*,算法介绍,第,029,课 算法及数据结构,16,1,、简述,A*,算法寻找过程,小测验：,第,029,课 算法及数据结构,17,在一个二维表格中,手动实现,A*,算法,模拟程序运行过程,并标出每次每个位置上,H F,值及其父节点,.,课后作业：,第,029,课 算法及数据结构,18,