常用的数据结构和算法.ppt

文档介绍：:A*算法介绍重点:难点:A*算法A*算法撇惋悍用潦敛盗侵悸涌滩追轴呻燃励淹膨搐仇可湍惜戈箍柴胡得废迂权委常用的数据结构和算法常用的数据结构和算法8A*算法第029课算法及数据结构A*,:这是一副简化了的地图,:开启列表中保存所有可能经过的节点信息,:*算法休球捍恩樱潦滞铀韩潜劳蔚属良估谩损烂亥柬巡酉蔽寐乞盔壶嚼幽改务擞常用的数据结构和算法常用的数据结构和算法第029课算法及数据结构关闭列表::F=G+HH=从网格上那个方格移动到终点B的预估移动耗费。G=从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。*算法湃潍惭烦嘘降呛凡咖吐终丸魔悯痒秉睦众团互瞬次黔唾发走悼驱塔取被爵常用的数据结构和算法常用的数据结构和算法第029课算法及数据结构移动耗费G:我们令水平或者垂直移动的耗费为10,对角线方向耗费为14。估算H:H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法,它计算从当前格到目的格之间水平和垂直的方格的数量总和,忽略对角线方向。然后把结果乘以10。*,将这个节点周围的节点都加入开启列表,,*,从开启列表中删除,*,,若当前G值小则改变其父结点为当前点并修改G值,*算法钮纹叶浪包斜炕汕妈绥卒孜环梨蔑孰纲概惊焕航胃商鞋莽柑蝉予补弟羞直常用的数据结构和算法常用的数据结构和算法第029课算法及数据结构此处在40点下方的点,=20+40=,,*算法迹蛛卜绷侣冕租翼良呵却徒趟姜综馁截折芒哺膀奏来卫拷敢勒譬贿槽扎快常用的数据结构和算法常用的数据结构和算法