人工智能基础实践教程 课件 第四讲-状态空间搜索第一次课程实践内容及要求

人工智能基础FUNDAMENTALSOFARTIFICIALINTELLIGENCE第四讲第二章状态空间搜索策略主讲人：刘伟-编程实验1本讲教学目标熟悉Python语言的基本编程方法掌握搜索算法实验分析和实验报告撰写基本方法针对具体问题，具备启发函数设计能力和分析能力1.实验任务通用图搜索的迷宫问题求解程序初始位置目标位置2.实验要求实验任务要求：阅读迷宫的搜索程序代码，了解算法流程；修改GraphRepresention.py文件中的expand函数，根据上移规则，完善其他移动规则；修改GraphRepresention.py文件中的h_function函数，定义可纳的启发函数（至少2种）；统计不同h函数对应的总扩展节点数和重复扩展节点数，并对结果进行对比分析。程序结构13.程序解析map.json地图文件main_Maze.py主程序GraphRepresention.py状态空间问题定义（含启发函数定义）UniversalSearch.py通用图搜索算法实现状态空间表示2有监督学习位置：state(r,c)代价：g，h，fValue指针：father节点描述有监督学习state(sr,sc)初始状态有监督学习state(objr,objc)目标状态3.程序解析操作符表示3有监督学习上、下、左、右移动操作符3.程序解析算法流程33.程序解析开始OPEN为空？失败退出是n为目标节点？成功退出是否把S放入OPEN表否找出节点n的所有子节点{ni}新节点{ni}放入OPEN表从OPEN表中选取某节点n取OPEN表第一个节点n放入CLOSED表找出节点n的所有子节点{ni},记录其父节点为n;计算其f值,判断{ni}是否已在OPEN/CLOSED表中，进行取舍按照f值对OPEN表排序选判扩移排代价优先法——f(n)=g(n)贪婪算法（最佳优先算法）——f(n)=h(n)A算法/A*算法——f(n)=g(n)+h(n)不同算法区别OPEN表按照f(n)值从小到大的顺序排列算法流程33.程序解析开始OPEN为空？失败退出是n为目标节点？成功退出是否把S放入OPEN表否找出节点n的所有子节点{ni}新节点{ni}放入OPEN表从OPEN表中选取某节点n取OPEN表第一个节点n放入CLOSED表找出节点n的所有子节点{ni},记录其父节点为n;计算其f值,判断{ni}是否已在OPEN/CLOSED表中，进行取舍按照f值对OPEN表排序选判扩移排重复节点处理43.程序解析f新≥f旧新节点ni的评估值：f新旧节点ni的评估值：f旧舍弃新的节点nif新<

f旧旧的ni在OPEN表中替换旧的节点ni旧的ni在CLOSED表删除旧的节点ni新节点进OPEN表重复发现重复扩展Sf旧f新niG重复节点处理4不仅要处理OPEN表，还要处理CLOSED表3.程序解析f新f旧启发式函数h(n)设计53.程序解析

曼哈顿距离：h2(n)＝|xG-xn|+|yG-yn|最优路径代价h*(n)SGnh1(n)h2(n)

h3(n)路径回溯6有监督学习从CLOSED表的末尾节点按照指针一直找到起始节点一般思路3.程序解析4.本次课安排基础任务课堂上完成代码修改，课后提交修改后代码以及实验文档。阅读迷宫的搜索程序代码，了解算法流程；修改GraphRepresention.py文件中的expand函数，根据上移规则，完善其他移动规则，将四方向移动修改为八方向移动；修改GraphRepresention.py文件中的h_function函数，定义可纳的启发函数（至少2种）；统计不同h函数对应的总扩展节点数和重复扩展节点数，并对结果进行对比分析。4.本次课安排进阶任务可视化已扩展（CLOSED）节点和待扩展（OPEN）节点；结合军事对抗复杂环境，修改迷宫地图，实现复杂环境下的搜索算法分析；统计不同算法（深度优先、宽度优先、贪婪法）对应的总扩展节点数和重复扩展节点数，并对结果进行对比分析。4.本次课安排代价优先搜索草地沙地河流平地树/墙